摘要：完全二叉樹深度為有個結(jié)點的二叉樹，其每個結(jié)點的編號與深度為的滿二叉樹中編號從的結(jié)點一一對應(yīng)葉子結(jié)點只可能在層數(shù)最大的兩層上出現(xiàn)。

二叉樹的性質(zhì)
(1) 在二叉樹的第 i 層最多有 2^i-1 個結(jié)點 (i>=1).
(2) 深度為 k 的二叉樹最多有 2^k - 1 個結(jié)點 (k>=1).
(3) 對任何一棵二叉樹，如果其葉子結(jié)點數(shù)為 n0, 度為 2 的結(jié)點數(shù)為 n2, 則 n0 = n2 + 1. 原因：設(shè)度為 1 的結(jié)點數(shù)為 n1, 則結(jié)點總數(shù) n = n0 + n1 + n2; 設(shè)分支數(shù)為 B, 由于只有根結(jié)點沒有分支進入, 因此 n = B + 1; 由于分支都是從度為 1 或 2 的結(jié)點引出的, 因此 B = n1 + 2 * n2; 聯(lián)立上述等式可得 n0 = n2 + 1.

滿二叉樹
深度為 k 且有 2^k - 1 個結(jié)點的二叉樹。

完全二叉樹
(1) 深度為 k、有 n 個結(jié)點的二叉樹，其每個結(jié)點的編號與深度為 k 的滿二叉樹中編號從 1~n 的結(jié)點一一對應(yīng).
(2) 葉子結(jié)點只可能在層數(shù)最大的兩層上出現(xiàn)。
(3) 對任意結(jié)點，若其右下分支下的子孫的最大層次為 lv, 則其左下分支下的子孫的最大層次必為 lv / lv + 1
(4) 結(jié)點數(shù)為 n 的完全二叉樹，其深度為 logn + 1.
(5) 結(jié)點數(shù)為 n 的完全二叉樹，結(jié)點按層編號，則對編號為 i 的結(jié)點 (1 <= i <= n):

     若 i==1, 則結(jié)點 i 為二叉樹的根, 無雙親;
     若 i>1 , 則結(jié)點 i 的雙親是 i/2;
     若 2i>n, 則結(jié)點 i 無左孩子, 否則其左孩子是結(jié)點 2i;
     若 2i+1>n, 則結(jié)點 i 無右孩子, 否則其右孩子是結(jié)點 2i+1.

存儲結(jié)構(gòu)
二叉鏈表的存儲表示

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

先序遍歷: 根-左-右
(1) 遞歸

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

(2) 非遞歸
棧：初始化棧，并且樹的根結(jié)點進棧；每次循環(huán)都將棧頂結(jié)點出棧并打印，然后先后將該結(jié)點的右子結(jié)點和左子結(jié)點進棧，直到棧為空。

    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) 非遞歸
棧：初始化棧，并且樹的根結(jié)點進棧。每次循環(huán)中，首先向左走到盡頭并將訪問到的每個結(jié)點進棧，此時棧頂存在空指針，需要將其出棧，然后將棧頂結(jié)點出棧，并訪問該結(jié)點，同時將該結(jié)點的右孩子進棧；直到棧為空。

    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);
            }
        }
    }

棧：初始化棧。每次循環(huán)中，若當(dāng)前結(jié)點不空時將該結(jié)點進棧，并遍歷其左子樹；否則將該結(jié)點出棧并訪問該結(jié)點，同時將該結(jié)點的右孩子進棧；直到當(dāng)前結(jié)點為空并且棧為空。

    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) 非遞歸
棧：為每個結(jié)點增加一個訪問標(biāo)志位 visited; 初始化棧。每次循環(huán)中，首先將根結(jié)點及其左子樹進棧，并將每個結(jié)點的訪問標(biāo)志位置為 true，使得棧頂為最左邊的左孩子，棧底為根結(jié)點；然后將棧頂結(jié)點出棧，若該結(jié)點的訪問標(biāo)志位為 true, 即該結(jié)點被訪問了一次，要將該結(jié)點重新進棧, 并置其訪問標(biāo)志位為 false, 再訪問該結(jié)點的右孩子；若該結(jié)點的訪問標(biāo)志位為 false, 即該結(jié)點被訪問了兩次, 要輸出該結(jié)點的值，并將當(dāng)前結(jié)點置為空；直到當(dāng)前結(jié)點為空而且棧為空。

    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);
            }
        }
    }