摘要：完全二叉樹深度為有個結點的二叉樹，其每個結點的編號與深度為的滿二叉樹中編號從的結點一一對應葉子結點只可能在層數最大的兩層上出現。

二叉樹的性質
(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);
            }
        }
    }