二叉树

摘要：完全二叉树深度为有个结点的二叉树，其每个结点的编号与深度为的满二叉树中编号从的结点一一对应叶子结点只可能在层数最大的两层上出现。

二叉树的性质
(1) 在二叉树的第 i 层最多有 2^i-1 个结点 (i>=1).
(2) 深度为 k 的二叉树最多有 2^k - 1 个结点 (k>=1).
(3) 对任何一棵二叉树，如果其叶子结点数为 n0, 度为 2 的结点数为 n2, 则 n0 = n2 + 1. 原因：设度为 1 的结点数为 n1, 则结点总数 n = n0 + n1 + n2; 设分支数为 B, 由于只有根结点没有分支进入, 因此 n = B + 1; 由于分支都是从度为 1 或 2 的结点引出的, 因此 B = n1 + 2 * n2; 联立上述等式可得 n0 = n2 + 1.

满二叉树
深度为 k 且有 2^k - 1 个结点的二叉树。

完全二叉树
(1) 深度为 k、有 n 个结点的二叉树，其每个结点的编号与深度为 k 的满二叉树中编号从 1~n 的结点一一对应.
(2) 叶子结点只可能在层数最大的两层上出现。
(3) 对任意结点，若其右下分支下的子孙的最大层次为 lv, 则其左下分支下的子孙的最大层次必为 lv / lv + 1
(4) 结点数为 n 的完全二叉树，其深度为 logn + 1.
(5) 结点数为 n 的完全二叉树，结点按层编号，则对编号为 i 的结点 (1 <= i <= n):

     若 i==1, 则结点 i 为二叉树的根, 无双亲;
     若 i>1 , 则结点 i 的双亲是 i/2;
     若 2i>n, 则结点 i 无左孩子, 否则其左孩子是结点 2i;
     若 2i+1>n, 则结点 i 无右孩子, 否则其右孩子是结点 2i+1.

存储结构
二叉链表的存储表示

class BiTNode {
    int data;
    BiTNode lchild, rchild;
}

先序遍历: 根-左-右
(1) 递归

    void preOrderRecursive(BiTNode tree) {
        if(tree!=null) {
            visit(tree);
            preOrderRecursive(tree.lchild);
            preOrderRecursive(tree.rchild);
        }
    }

(2) 非递归
栈：初始化栈，并且树的根结点进栈；每次循环都将栈顶结点出栈并打印，然后先后将该结点的右子结点和左子结点进栈，直到栈为空。

    void preOrder(BiTNode tree) {
        if(tree==null) {
            return;
        }
        LinkedList stack = new LinkedList();
        stack.push(tree);
        while(stack.size()>0) {
            BiTNode node = stack.pop();
            visit(node);
            if(node.rchild!=null) {
                stack.push(node.rchild);
            }
            if(node.lchild!=null) {
                stack.push(node.lchild);
            }
        }
    }

中序遍历: 左-根-右
(1) 递归

    void inOrderRecursive(BiTNode tree) {
        if(tree!=null) {
            inOrderRecursive(tree.lchild);
            visit(tree);
            inOrderRecursive(tree.rchild);
        }
    }

(2) 非递归
栈：初始化栈，并且树的根结点进栈。每次循环中，首先向左走到尽头并将访问到的每个结点进栈，此时栈顶存在空指针，需要将其出栈，然后将栈顶结点出栈，并访问该结点，同时将该结点的右孩子进栈；直到栈为空。

    void inOrder(BiTNode tree) {
        if(tree==null) {
            return;
        }
        LinkedList stack = new LinkedList();
        stack.push(tree);
        while(stack.size()>0) {
            BiTNode node = stack.peek();
            while(node!=null) {
                stack.push(node.lchild);
                node = stack.peek();
            }
            stack.pop();
            if(stack.size()>0) {
                node = stack.pop();
                visit(node);
                stack.push(node.rchild);
            }
        }
    }

栈：初始化栈。每次循环中，若当前结点不空时将该结点进栈，并遍历其左子树；否则将该结点出栈并访问该结点，同时将该结点的右孩子进栈；直到当前结点为空并且栈为空。

    void inOrder(BiTNode tree) {
        if(tree==null) {
            return;
        }
        LinkedList stack = new LinkedList();
        BiTNode node = tree;
        while(node!=null || stack.size()>0) {
            if(node!=null) {
                stack.push(node);
                node = node.lchild;
            } else {
                node = stack.pop();
                visit(node);
                node = node.rchild;
            }
        }
    }

后序遍历: 左-右-根
(1) 递归

    void postOrderRecursive(BiTNode tree) {
        if(tree!=null) {
            postOrderRecursive(tree.lchild);
            postOrderRecursive(tree.rchild);
            visit(tree);
        }
    }

(2) 非递归
栈：为每个结点增加一个访问标志位 visited; 初始化栈。每次循环中，首先将根结点及其左子树进栈，并将每个结点的访问标志位置为 true，使得栈顶为最左边的左孩子，栈底为根结点；然后将栈顶结点出栈，若该结点的访问标志位为 true, 即该结点被访问了一次，要将该结点重新进栈, 并置其访问标志位为 false, 再访问该结点的右孩子；若该结点的访问标志位为 false, 即该结点被访问了两次, 要输出该结点的值，并将当前结点置为空；直到当前结点为空而且栈为空。

    void postOrder(BiTNode tree) {
        if(tree==null) {
            return;
        }
        List stack = new LinkedList();
        BiTNode node = tree;
        while(node!=null || stack.size()>0) {
            while(node!=null) {
                node.visited = true;
                stack.push(node);
                node = node.lchild;
            }
            if(stack.size()>0) {
                BiTNode temp = stack.pop();
                if(temp.visited) {
                    temp.visited = false;
                    stack.push(temp);
                    node = temp.rchild;
                } else {
                    visit(temp);
                    node = null;
                }
            }
        }
    }

层次遍历

    void levelOrder(BiTNode tree) {
        if(tree==null) {
            return;
        }
        LinkedList queue = new LinkedList();
        queue.add(tree);
        while(queue.size()>0) {
            BiTNode node = queue.remove();
            visit(node);
            if(node.lchild!=null) {
                queue.add(node.lchild);
            }
            if(node.rchild!=null) {
                queue.add(node.rchild);
            }
        }
    }