数据结构树和二叉树知识点和递归序列

一.树的概念

树是一种非线性数据结构，它是由n个或大于n个的结点来组成具有层次关系的一个集合（一个树及n个子树的关系集合） 把这个数据结构称之为树因为它很像一棵倒挂着的树 树的特点： 每一个结点都有零个或者n个结点组成 没有父亲结点的称为根结点 除根结点以外每一个节点都有一个父亲结点 结点之间互不相交

1.1关于树的名词解释

结点的度：一个结点含有的子树的个数称之为度。 树的度：在一棵树中，所有结点的度的最大值称之为树的度。 叶子结点或者终端结点：度为0的结点称为叶子结点/终端结点（不含有子树的结点）。 双亲结点或者父亲结点：若该结点含有子结点，则这个结点称为子结点的父亲结点。 子结点或者孩子结点：一个结点中含有子树的根结点称为该结点的子结点。 根结点：树中没有父亲结点称为根节点 结点的层次：从根开始定义为第一层，根的子结点为第二层…直到遇到所有终端结点。 树的高度：树中最大结点的层级，为树高。 一棵N个结点的树会产生n-1条边

二.二叉树的概念

二叉树是指每个节点最多有两个子树的树结构，共有五种形态 二叉树中树的度都是小于或者等于2的，不存在大于2的树

1. 二叉树性质：

性质1：二叉树第i层上的结点数最多为 2的i-1次方(i≥1)。 性质2：深度为k的二叉树至多有2的k-1次方个结点（k>=0）。 性质3：具有n个结点的二叉树的深度为log2 (n+1)。 性质4：在任意的二叉树中，若叶子结点的个数为n0，度为1的结点数为n1，度为2的结点数为n2。 表达式1:N=n0+n1+n2; 表达式2:N=n1+2*n2+1 则n0=n2+1。

三.满二叉树与完全二叉树

满二叉树：二叉树中每一个结点的度为2，为满二叉树。

非满二叉树

完全二叉树：在二叉树中，只有最下面两层结点的度可以小于2，并且最下层的叶子结点集中在左子树的位置上，如果没有集中在左树则不是一个非完全二叉树 一颗满二叉树必定是一颗完全二叉树，而完全而二叉树不一定是满二叉树。

递归前序遍历

 public void preOrder(BinaryNode cur){
       if(cur ==null){
           return;
       }
            System.out.print(cur.val+" ");
            preOrder(cur.left);
            preOrder(cur.right);
    }

递归中序遍历

 public void inOrder(BinaryNode cur){
        if(cur==null){
            return;
        }
        inOrder(cur.left);
        System.out.print(cur.val+" ");
        inOrder(cur.right);
    }

递归后续遍历

 public void lastOrder(BinaryNode cur){
        if(cur==null){
            return;
        }
        inOrder(cur.left);
        inOrder(cur.right);
        System.out.print(cur.val+" ");

    }