一、树

定义

树（tree）是包含n（n>=0）个结点的有穷集，其中：
（1）每个元素称为结点（node）；
（2）有一个特定的结点被称为根结点或树根（root）。
（3）除根结点之外的其余数据元素被分为m（m≥0）个互不相交的集合T1，T2，……Tm-1，其中每一个集合Ti（1<=i<=m）本身也是一棵树，被称作原树的子树（subtree）。

特点：

每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树；

相关术语

• 结点的度：一个结点含有的子结点的个数称为该结点的度；
• 叶结点或终端结点：度为0的结点称为叶结点；
• 非终端结点或分支结点：度不为0的结点；
• 双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点；
• 孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点；
• 兄弟结点：具有相同父结点的结点互称为兄弟结点；
• 树的度：一棵树中，最大的结点的度称为树的度；
• 结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推；
• 树的高度或深度：树中结点的最大层次；
• 堂兄弟结点：双亲在同一层的结点互为堂兄弟；
• 结点的祖先：从根到该结点所经分支上的所有结点；
• 子孙：以某结点为根的子树中任一结点都称为该结点的子孙。
• 森林：由m（m>=0）棵互不相交的树的集合称为森林；

二、二叉树

在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。
二叉树的结构：
二叉树由节点（node）和边组成。节点分为根节点、父节点、子节点。如下图所示：

红色是根节点（root）。蓝色是子节点也是父节点，绿色的是子节点。其余的线是边。节点和链表中的节点一样都可以存放数据信息。树中的边可以用自引用表示，这种引用就是C/C++里面的指针。通常来说树是顶部小，底部大，且树呈分层结构。root节点时第0层，以此类推。二叉树最多有两个节点。

二叉树的优势

在实际使用时会根据链表和有序数组等数据结构的不同优势进行选择。有序数组的优势在于二分查找，链表的优势在于数据项的插入和数据项的删除。但是在有序数组中插入数据就会很慢，同样在链表中查找数据项效率就很低。综合以上情况，二叉树可以利用链表和有序数组的优势，同时可以合并有序数组和链表的优势，二叉树也是一种常用的数据结构。

二叉树的性质

(1) 在非空二叉树中，第i层的结点总数不超过 , i>=1；
(2) 深度为h的二叉树最多有 个结点(h>=1)，最少有h个结点；
(3) 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；
(4) 具有n个结点的完全二叉树的深度为 （注：[ ]表示向下取整）
(5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：
若I为结点编号则 如果I>1，则其父结点的编号为I/2；
如果2I<=N，则其左孩子（即左子树的根结点）的编号为2I；若2I>N，则无左孩子；
如果2I+1<=N，则其右孩子的结点编号为2I+1；若2I+1>N，则无右孩子。
(6)给定N个结点，能构成h(N)种不同的二叉树。
h(N)为卡特兰数的第N项。h(n)=C(2*n，n)/(n+1)。
(7)设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i

满二叉树

除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。
一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。

满二叉树

完全二叉树

若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

完全二叉树

三、二叉树的存储结构

顺序存储方式

二叉树的顺序存储结构是用一个数组来存储二叉树中的结点，根据二叉树的特性，结点的存储位置可以反映结点之间的逻辑关系。
我们先来看完全二叉树的顺序存储结构：

顺序存储-完全二叉树

如上图，将这棵二叉树存入在一维数组中，相应的下标对应其同样的位置。

那么对于不是完全二叉树的表示方法呢？我们再来看一般二叉树的顺序存储结构：

顺序存储-非完全二叉树

其实对于一般二叉树来说，还是按照层序遍历把结点存储在一维数组中，只是在没有结点的位置用一个特殊的占位符来标识，图中用的"∧"，实际编码中也可以直接用null。注意图中没有结点的位置用了空心的结点来填充，便于理解。

链表存储方式

既然顺序存储不能满足二叉树的存储需求，那么考虑采用链式存储。由二叉树定义可知，二叉树的每个结点最多有两个孩子。
所以我们可以这么设计：

定义结点代码：

public class BiNode {
    public String data;
    public BiNode leftChild;
    public BiNode rightChild;
}

链式存储的优点是节省空间，遍历方便。而当我们需要查找某一个结点时，就会比较繁琐，因为有可能需要遍历整个二叉树的结构，才能完成查找。
对此，如果我们能在顺序存储和链式存储之间转换的话，就可以解决大多数的问题了。

顺序存储转链式存储算法如下：

public class Test{
    public void convertFromArray(String[] nodes) {
        TreeNode root = new TreeNode();
        root.data = nodes[0];
        TreeNode bigTree = createBiTreeNode(root, nodes, 1);
        System.out.println(bigTree);
    }


    private static TreeNode createBiTreeNode(TreeNode root, String[] nodes, int position) {
        if (position * 2 > nodes.length) {
            return root;
        }

        if ((position * 2 - 1) < nodes.length && null != nodes[position * 2 - 1]) {
            TreeNode leftChild = new TreeNode();
            leftChild.data = nodes[position * 2 - 1];
            root.leftChild = leftChild;
            createBiTreeNode(root.leftChild, nodes, position * 2);
        }

        if ((position * 2) < nodes.length && null != nodes[position * 2]) {
            TreeNode rightChild = new TreeNode();
            rightChild.data = nodes[position * 2];
            root.rightChild = rightChild;
            createBiTreeNode(root.rightChild, nodes, position * 2 + 1);
        }
        return root;
    }

    public static void main(String[] args) {
        Test test = new Test();
        String[] array = {"A","B","C",null,"E","F","G",null,null,"J"};
        test.convertFromArray(array);
    }
}

class TreeNode {
    public String data;
    public TreeNode leftChild;
    public TreeNode rightChild;
}

存储方式总结：
顺序存储可能会浪费空间(在非完全二叉树的时候); 但是读取某个指定的节点的时候效率比较高O(0)。
链式存储相对二叉树比较大的时候浪费空间较少，但是读取某个指定节点的时候效率偏低O(nlogn)。

四、二叉树遍历

二叉树的遍历是指从二叉树的根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次，且仅被访问一次。
二叉树的访问次序可以分为四种：

• 前序遍历
• 中序遍历
• 后序遍历
• 层序遍历

前序遍历

先访问根节点——左子树——右子树。

如图所示二叉树的前序遍历输出为：ABDHIEJCFG

//递归实现
    public static void preOrderRe(TreeNode biTree) {
        System.out.println(biTree.data);
        TreeNode leftTree = biTree.leftChild;
        if (leftTree != null) {
            preOrderRe(leftTree);
        }
        TreeNode rightTree = biTree.rightChild;
        if (rightTree != null) {
            preOrderRe(rightTree);
        }
    }

    //非递归实现
    public static void preOrder(TreeNode biTree) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        while (biTree != null || !stack.isEmpty()) {
            while (biTree != null) {
                System.out.println(biTree.data);
                stack.push(biTree);
                biTree = biTree.leftChild;
            }
            if (!stack.isEmpty()) {
                biTree = stack.pop();
                biTree = biTree.rightChild;
            }
        }
    }

中序遍历

先访问左子树——根节点——右子树。
则如上图所示二叉树的中序遍历输出为：HDIBJEAFCG

//中序遍历递归实现
    public static void midOrderRe(TreeNode biTree) {
        if (biTree == null)
            return;
        else {
            midOrderRe(biTree.leftChild);
            System.out.println(biTree.data);
            midOrderRe(biTree.rightChild);
        }
    }

    //中序遍历费递归实现
    public static void midOrder(TreeNode biTree) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        while (biTree != null || !stack.isEmpty()) {
            while (biTree != null) {
                stack.push(biTree);
                biTree = biTree.leftChild;
            }
            if (!stack.isEmpty()) {
                biTree = stack.pop();
                System.out.println(biTree.data);
                biTree = biTree.rightChild;
            }
        }
    }

后序遍历

先访问树的左子树——右子树——根节点。
则如上图所示二叉树的中序遍历输出为：HIDJEBFGCA

//后序遍历递归实现
    public static void postOrderRe(TreeNode biTree) {
        if (biTree == null)
            return;
        else {
            postOrderRe(biTree.leftChild);
            postOrderRe(biTree.rightChild);
            System.out.println(biTree.data);
        }
    }

    //后序遍历非递归实现
    public static void postOrder(TreeNode biTree) {
        int left = 1;//在辅助栈里表示左节点
        int right = 2;//在辅助栈里表示右节点
        Stack<TreeNode> stack = new Stack<TreeNode>();
        //辅助栈，用来判断子节点返回父节点时处于左节点还是右节点。
        Stack<Integer> stack2 = new Stack<Integer>();

        while (biTree != null || !stack.empty()) {
            //将节点压入栈1，并在栈2将节点标记为左节点
            while (biTree != null) {
                stack.push(biTree);
                stack2.push(left);
                biTree = biTree.leftChild;
            }

            //如果是从右子节点返回父节点，则任务完成，将两个栈的栈顶弹出
            while (!stack.empty() && stack2.peek() == right) {
                stack2.pop();
                System.out.println(stack.pop().data);
            }

            //如果是从左子节点返回父节点，则将标记改为右子节点
            if (!stack.empty() && stack2.peek() == left) {
                stack2.pop();
                stack2.push(right);
                biTree = stack.peek().rightChild;
            }

        }
    }

层序遍历

层序遍历理解起来最简单：把一棵树从上到下，从左到右依次写出来。
则如上图所示二叉树的中序遍历输出为：ABCDEFGHIJ

     //层序遍历
    public static void levelOrder(TreeNode biTree) {
        if(biTree == null)
            return;
        LinkedList<TreeNode> list = new LinkedList<TreeNode>();
        list.add(biTree);
        TreeNode currentNode;
        while(!list.isEmpty())
        {
            currentNode = list.poll();
            System.out.println(currentNode.data);
            if(currentNode.leftChild != null)
                list.add(currentNode.leftChild);
            if(currentNode.rightChild != null)
                list.add(currentNode.rightChild);
        }
    }