摘要：樹和樹的算法一樹樹的概念樹英語是一種抽象數(shù)據(jù)類型或是實作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)，用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。一種時間復(fù)雜度額外空間復(fù)雜度的二叉樹的遍歷方式，為二叉樹的節(jié)點個數(shù)。

樹（英語：tree）是一種抽象數(shù)據(jù)類型（ADT）或是實作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)，用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。它是由n（n>=1）個有限節(jié)點組成一個具有層次關(guān)系的集合。把它叫做“樹”是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。它具有以下的特點：

每個節(jié)點有零個或多個子節(jié)點；

沒有父節(jié)點的節(jié)點稱為根節(jié)點；

每一個非根節(jié)點有且只有一個父節(jié)點；

除了根節(jié)點外，每個子節(jié)點可以分為多個不相交的子樹；

節(jié)點的度：一個節(jié)點含有的子樹的個數(shù)稱為該節(jié)點的度；

樹的度：一棵樹中，最大的節(jié)點的度稱為樹的度；

葉節(jié)點或終端節(jié)點：度為零的節(jié)點；

父親節(jié)點或父節(jié)點：若一個節(jié)點含有子節(jié)點，則這個節(jié)點稱為其子節(jié)點的父節(jié)點；

孩子節(jié)點或子節(jié)點：一個節(jié)點含有的子樹的根節(jié)點稱為該節(jié)點的子節(jié)點；

兄弟節(jié)點：具有相同父節(jié)點的節(jié)點互稱為兄弟節(jié)點；

節(jié)點的層次：從根開始定義起，根為第1層，根的子節(jié)點為第2層，以此類推；

樹的高度或深度：樹中節(jié)點的最大層次；

堂兄弟節(jié)點：父節(jié)點在同一層的節(jié)點互為堂兄弟；

節(jié)點的祖先：從根到該節(jié)點所經(jīng)分支上的所有節(jié)點；

子孫：以某節(jié)點為根的子樹中任一節(jié)點都稱為該節(jié)點的子孫。

森林：由m（m>=0）棵互不相交的樹的集合稱為森林；

無序樹：樹中任意節(jié)點的子節(jié)點之間沒有順序關(guān)系，這種樹稱為無序樹，也稱為自由樹；

樹中任意節(jié)點的子節(jié)點之間有順序關(guān)系，這種樹稱為有序樹；
二叉樹：每個節(jié)點最多含有兩個子樹的樹稱為二叉樹；

完全二叉樹：對于一顆二叉樹，假設(shè)其深度為d(d>1)。除了第d層外，其它各層的節(jié)點數(shù)目均已達(dá)最大值，且第d層所有節(jié)點從左向右連續(xù)地緊密排列，這樣的二叉樹被稱為完全二叉樹，其中滿二叉樹的定義是所有葉節(jié)點都在最底層的完全二叉樹;

平衡二叉樹（AVL樹）：當(dāng)且僅當(dāng)任何節(jié)點的兩棵子樹的高度差不大于1的二叉樹；

排序二叉樹（二叉查找樹（英語：Binary Search Tree），也稱二叉搜索樹、有序二叉樹)

霍夫曼樹（用于信息編碼）：帶權(quán)路徑最短的二叉樹稱為哈夫曼樹或最優(yōu)二叉樹；
B樹：一種對讀寫操作進(jìn)行優(yōu)化的自平衡的二叉查找樹，能夠保持?jǐn)?shù)據(jù)有序，擁有多余兩個子樹。

順序存儲：將數(shù)據(jù)結(jié)構(gòu)存儲在固定的數(shù)組中，然在遍歷速度上有一定的優(yōu)勢，但因所占空間比較大，是非主流二叉樹。二叉樹通常以鏈?zhǔn)酱鎯Α?/p> 1.5 常見的一些樹的應(yīng)用場景

xml，html等，那么編寫這些東西的解析器的時候，不可避免用到樹

路由協(xié)議就是使用了樹的算法

mysql數(shù)據(jù)庫索引

文件系統(tǒng)的目錄結(jié)構(gòu)

所以很多經(jīng)典的AI算法其實都是樹搜索，此外機器學(xué)習(xí)中的decision tree也是樹結(jié)構(gòu)

二叉樹是每個節(jié)點最多有兩個子樹的樹結(jié)構(gòu)。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）

性質(zhì)1: 在二叉樹的第i層上至多有2^(i-1)個結(jié)點（i>0）
性質(zhì)2: 深度為k的二叉樹至多有2^k - 1個結(jié)點（k>0）
性質(zhì)3: 對于任意一棵二叉樹，如果其葉結(jié)點數(shù)為N0，而度數(shù)為2的結(jié)點總數(shù)為N2，則N0=N2+1;
性質(zhì)4:具有n個結(jié)點的完全二叉樹的深度必為 log2(n+1)
性質(zhì)5:對完全二叉樹，若從上至下、從左至右編號，則編號為i 的結(jié)點，其左孩子編號必為2i，其右孩子編號必為2i＋1；其雙親的編號必為i/2（i＝1 時為根,除外）

(1)完全二叉樹——若設(shè)二叉樹的高度為h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點數(shù)都達(dá)到最大個數(shù)，第h層有葉子結(jié)點，并且葉子結(jié)點都是從左到右依次排布，這就是完全二叉樹。

(2)滿二叉樹——除了葉結(jié)點外每一個結(jié)點都有左右子葉且葉子結(jié)點都處在最底層的二叉樹。

通過使用Node類中定義三個屬性，分別為elem本身的值，還有l(wèi)child左孩子和rchild右孩子

class Node(object):
    """節(jié)點類"""
    def __init__(self, elem=-1, lchild=None, rchild=None):
        self.elem = elem
        self.lchild = lchild
        self.rchild = rchild
樹的創(chuàng)建,創(chuàng)建一個樹的類，并給一個root根節(jié)點，一開始為空，隨后添加節(jié)點

class Tree(object):
    """樹類"""
    def __init__(self, root=None):
        self.root = root

    def add(self, elem):
        """為樹添加節(jié)點"""
        node = Node(elem)
        #如果樹是空的，則對根節(jié)點賦值
        if self.root == None:
            self.root = node
        else:
            queue = []
            queue.append(self.root)
            #對已有的節(jié)點進(jìn)行層次遍歷
            while queue:
                #彈出隊列的第一個元素
                cur = queue.pop(0)
                if cur.lchild == None:
                    cur.lchild = node
                    return
                elif cur.rchild == None:
                    cur.rchild = node
                    return
                else:
                    #如果左右子樹都不為空，加入隊列繼續(xù)判斷
                    queue.append(cur.lchild)
                    queue.append(cur.rchild)

Node節(jié)點類：

class Node{
    public int value;
    public Node lChild;
    public Node rChild;
    public Node(int value){
        this.value = value;
    }
}

Tree類：

class Tree{
    public Node root;
    //根節(jié)點初始化
    public Tree(Node node){
        root = node;
    }
    //樹中通過廣度優(yōu)先遍歷的方式尋找空位置加新節(jié)點
    public void add(int value){
        Node temp = new Node(value);
        if(root==null){
            root = temp;
        }
        Queue queue = new LinkedList();
        queue.add(root);
        while(!queue.isEmpty()) {
            Node curNode = queue.poll();
            if (curNode.lChild == null) {
                curNode.lChild = temp;
                return;
            } else if (curNode.rChild == null) {
                curNode.rChild = temp;
                return;
            } else {
                queue.add(curNode.lChild);
                queue.add(curNode.rChild);
            }

        }
    }
}

樹的遍歷是樹的一種重要的運算。所謂遍歷是指對樹中所有結(jié)點的信息的訪問，即依次對樹中每個結(jié)點訪問一次且僅訪問一次，我們把這種對所有節(jié)點的訪問稱為遍歷（traversal）。那么樹的兩種重要的遍歷模式是深度優(yōu)先遍歷和廣度優(yōu)先遍歷,深度優(yōu)先一般用遞歸，廣度優(yōu)先一般用隊列。一般情況下能用遞歸實現(xiàn)的算法大部分也能用堆棧來實現(xiàn)(掌握先序、中序、后序的非遞歸方式)。

對于一顆二叉樹，深度優(yōu)先搜索(Depth First Search)是沿著樹的深度遍歷樹的節(jié)點，盡可能深的搜索樹的分支。
那么深度遍歷有重要的三種方法。這三種方式常被用于訪問樹的節(jié)點，它們之間的不同在于訪問每個節(jié)點的次序不同。這三種遍歷分別叫做先序遍歷（preorder），中序遍歷（inorder）和后序遍歷（postorder）。我們來給出它們的詳細(xì)定義，然后舉例看看它們的應(yīng)用。

遞歸實現(xiàn)先序、中序、后序非常強大的地方是每個都會訪問同一個節(jié)點三次，所以三個遍歷方式只是調(diào)換一下函數(shù)執(zhí)行順序。

無論是否是遞歸方式都用到了棧(函數(shù)棧也是棧)：因為樹的結(jié)構(gòu)是從上到下訪問，如果要返回去訪問另一處的節(jié)點，那么必須要有棧來“記憶”。

在先序遍歷中，我們先訪問根節(jié)點，然后遞歸使用先序遍歷訪問左子樹，再遞歸使用先序遍歷訪問右子樹
根節(jié)點->左子樹->右子樹
Python代碼實現(xiàn)：

def preorder(self, root):
      """遞歸實現(xiàn)先序遍歷"""
      if root == None:
          return
      print root.elem
      self.preorder(root.lchild)
      self.preorder(root.rchild)

Java代碼實現(xiàn)(遞歸方式)：

public class PreOrder {

    private void preOrder(Node node){
        if(node == null){
            return;
        }
        System.out.println(node.value);
        preOrder(node.lChild);
        preOrder(node.rChild);
    }

    public static void main(String[] args){
        PreOrder sort = new PreOrder();
        Tree tree = new Tree(new Node(0));
        tree.add(1);
        tree.add(2);
        tree.add(3);
        tree.add(4);
        sort.preOrder(tree.root);
    }
}

Java 代碼實現(xiàn)(非遞歸方式)：

public void preOrderUnRecur(Node head){
    System.out.print("preOrder:");
    if(head!=null){
        //利用棧來實現(xiàn)
        Stack stack = new Stack();
        stack.push(head);
        while(!stack.isEmpty()){
            Node node = stack.pop();
            System.out.print(node.value + " ");
            //先壓進(jìn)右孩子，利用先進(jìn)后出原則
            if(node.rChild!=null){
                stack.push(node.rChild);
            }
            if(node.lChild!=null){
                stack.push(node.lChild);
            }
        }
    }
}

在中序遍歷中，我們遞歸使用中序遍歷訪問左子樹，然后訪問根節(jié)點，最后再遞歸使用中序遍歷訪問右子樹
左子樹->根節(jié)點->右子樹
Python代碼實現(xiàn)：

def inorder(self, root):
      """遞歸實現(xiàn)中序遍歷"""
      if root == None:
          return
      self.inorder(root.lchild)
      print root.elem
      self.inorder(root.rchild)

Java代碼實現(xiàn)(遞歸方式)：

public class InOrder {

    public void inOrder(Node node){
        if(node==null){
            return;
        }
        inOrder(node.lChild);
        System.out.println(node.value);
        inOrder(node.rChild);
    }

    public static void main(String[] args){
        Tree tree = new Tree(new Node(0));
        tree.add(1);
        tree.add(2);
        tree.add(3);
        tree.add(4);
        InOrder sort = new InOrder();
        sort.inOrder(tree.root);
    }
}

Java實現(xiàn)(非遞歸方式)：

public void inOrderUnRecur(Node head){
    System.out.print("InOrder:");
    if(head!=null){
        Stack stack = new Stack<>();
        while(!stack.isEmpty() || head!=null){
            if(head != null){
                stack.push(head);
                head = head.lChild;
            }else{
                head = stack.pop();
                System.out.print(head.value + " ");
                head = head.rChild;
            }
        }
    }
}

在后序遍歷中，我們先遞歸使用后序遍歷訪問左子樹和右子樹，最后訪問根節(jié)點
左子樹->右子樹->根節(jié)點
Python代碼實現(xiàn)：

def postorder(self, root):
      """遞歸實現(xiàn)后續(xù)遍歷"""
      if root == None:
          return
      self.postorder(root.lchild)
      self.postorder(root.rchild)
      print root.elem

Java代碼實現(xiàn)(遞歸方式)：

public class PostOrder {

    public void postOrder(Node node){
        if(node==null){
            return;
        }
        postOrder(node.lChild);
        postOrder(node.rChild);
        System.out.println(node.value);
    }

    public static void main(String[] args) {
        Tree tree = new Tree(new Node(0));
        tree.add(1);
        tree.add(2);
        tree.add(3);
        tree.add(4);
        PostOrder sort = new PostOrder();
        sort.postOrder(tree.root);
    }
}

Java代碼實現(xiàn)(非遞歸方式：采用輔助空間方式,把先序(中右左)存儲到輔助棧，然后根據(jù)先進(jìn)后出打印出結(jié)果就是后序遍歷結(jié)果(左右中)):

public void postOrderUnRecur(Node head){
    System.out.print("postOrder:");
    if(head!=null){
        Stack stack1 = new Stack();
        Stack stack2 = new Stack();
        stack1.push(head);
        while(!stack1.isEmpty()){
            head = stack1.pop();
            stack2.push(head);  //與先序的不同：先序打印，后序存儲起來
            if(head.lChild!=null){
                stack1.push(head.lChild);
            }
            if(head.rChild!=null){
                stack1.push(head.rChild);
            }
        }
        //利用棧先進(jìn)后出原則輸出后序遍歷結(jié)果
        while(!stack2.isEmpty()){
            head = stack2.pop();
            System.out.print(head.value + " ");
        }
    }
}

思考：哪兩種遍歷方式能夠唯一的確定一顆樹？？？

通過一個隊列的方法來實現(xiàn)

從樹的root開始，從上到下從從左到右遍歷整個樹的節(jié)點

def breadth_travel(self, root):
        """利用隊列實現(xiàn)樹的層次遍歷"""
        if root == None:
            return
        queue = []
        queue.append(root)
        while queue:
            node = queue.pop(0)
            print node.elem,
            if node.lchild != None:
                queue.append(node.lchild)
            if node.rchild != None:
                queue.append(node.rchild)

二叉樹的遍歷一般額外空間復(fù)雜度為O(logn)，根據(jù)高度來的(節(jié)點回到自身需要保存到棧中)，要回到上一個很難(通過棧解決)。

一種時間復(fù)雜度O(n),額外空間復(fù)雜度O(1)的二叉樹的遍歷方式，N為二叉樹的節(jié)點個數(shù)。

Morris 遍歷規(guī)則：

來到當(dāng)前節(jié)點，記為cur，如果cur無左孩子，cur向右移動cur = cur.right

如果cur有左孩子：找到左子樹上最右節(jié)點，記為mostright,①如果mostright的right指針指向空，讓其指向cur,然后cur向左移動cur = cur.left ②如果mostright指向cur，讓其指向空，cur向右移動。

public static void morrisIn(Node head){
    if(head == null){
        return;
    }
    Node cur = head;
    Node mostRight = null;
    while(cur!=null){
        mostRight = cur.left;
        if(mostRight!=null){ //有左孩子，找到左子樹的最右節(jié)點
            while(mostRight.right!=null && mostRight.right!=cur){
                mostRight = mostRight.right;
            }
            if(mostRight.right == null){
                mostRight.right = cur;
                cur = cur.left;
                continue;
            }else{
                mostRight.right = null;
            }
        }
        System.out.print(cur.value + " ");//要往右節(jié)點走了，就是中序遍歷
        cur = cur.right;
    }
}

如果一個節(jié)點有左子樹，morris能回到節(jié)點兩次。如果沒有左子樹，只到節(jié)點一次。

morris改先序遍歷

public static void morrisPre(Node head){
    if(head == null){
        return;
    }
    Node cur = head;
    Node mostRight = null;
    while(cur!=null){
        mostRight = cur.left;
        if(mostRight!=null){
            while(mostRight.right!=null && mostRight.right!=cur){
                mostRight = mostRight.right;
            }
            if(mostRight.right == null){
                mostRight.right = cur;
                System.out.print(cur.value + " ")
                cur = cur.left;
                continue;
            }else{
                mostRight.right = null;
            }
        }else{
            System.out.print(cur.value + " ");
        }
        cur = cur.right;
    }
    System.out.println();
}

后序遍歷是第三次回到節(jié)點時候打印的，但是morris沒有回到節(jié)點第三次的。
怎么做？
先去關(guān)注能回到節(jié)點兩次的節(jié)點，逆序打印它左子樹的右邊界。退出函數(shù)時多帶帶打印整棵樹的右邊界

public static void morrisPos(Node head){
    if(head == null){
        return;
    }
    Node cur1 = head;
    Node cur2 = head;
    while(cur1 !=null) {
        cur2 = cur1.left;
        if(cur2!=null){
            while(cur2.right!=null && cur2.right!=cur1){
                cur2 = cur2.right;
            }  
            if(cur2.right==null){
                cur2.right = cur1;
                cur1 = cur1.left;
                continue;
            }else{
                cur2.right = null;
                printEdge(cur1.left);
            }
        }
        cur1 = cur1.right;
    }
    printEdge(head);
    System.out.println();
}

怎么實現(xiàn)逆序打印？
采用鏈表逆序的方法，打印完再調(diào)整回來，這樣就沒有引入額外空間復(fù)雜度

先序 + 中序
思想：

先序取第一位即是根，然后根據(jù)這個元素找到中序的左子樹和右子樹

先判斷左子樹，先序除了第一位后是連續(xù)的一塊左子樹的元素和連續(xù)的一塊右子樹元素，去先序連續(xù)一塊左子樹的第一位，再到中序去分割新的左子樹和右子樹

通過重復(fù)2，可以畫出一個樹

中序+后序也可以

題目：現(xiàn)有一種新的二叉樹節(jié)點類型如下

public class Node{
    public int value;
    public Node left;
    public Node right;
    public Node parent;
    public Node(int value){
        this.value = value;
    }
}

這個結(jié)構(gòu)只比普通二叉樹節(jié)點結(jié)構(gòu)多了一個指向父節(jié)點的parent指針。假設(shè)一棵Node類型的節(jié)點組成的二叉樹，樹中每個節(jié)點的parent指針都正確地指向父節(jié)點，頭節(jié)點的parent指向Null，只給一個在二叉樹中的某個節(jié)點Node，請實現(xiàn)返回node的后繼節(jié)點的函數(shù)。在二叉樹的中序遍歷的序列中，node的下一個節(jié)點叫作node的后繼節(jié)點。

解決思路：如果一個節(jié)點有右子樹，那么右子樹的左邊界(整個樹最左下角)節(jié)點一定是它的后繼節(jié)點；如果沒有右子樹，通過這個節(jié)點的父指針parent指向父節(jié)點，如果發(fā)現(xiàn)這個節(jié)點是父節(jié)點的右孩子，就繼續(xù)往上，一直到某個節(jié)點是它父節(jié)點的左孩子，那么這個最初節(jié)點的后繼就是這個父節(jié)點。

Java 代碼創(chuàng)建特殊的節(jié)點類：

public class FatherPointNode {
    public int value;
    public FatherPointNode lChild;
    public FatherPointNode rChild;
    public FatherPointNode parent;
    public FatherPointNode(int value){
        this.value = value;
    }
}

Java 代碼創(chuàng)建特殊的樹類：

public class FatherPointTree {

    public FatherPointNode root;
    //根節(jié)點初始化
    public FatherPointTree(FatherPointNode node){
        root = node;
    }
    //樹中通過廣度優(yōu)先遍歷的方式尋找空位置加新節(jié)點
    public void add(int value){
        FatherPointNode temp = new FatherPointNode(value);
        if(root==null){
            root = temp;
        }
        Queue queue = new LinkedList();
        queue.add(root);
        while(!queue.isEmpty()) {
            FatherPointNode curNode = queue.poll();
            if (curNode.lChild == null) {
                curNode.lChild = temp;
                temp.parent = curNode; //與原來的樹不同地方：添加父節(jié)點
                return;
            } else if (curNode.rChild == null) {
                curNode.rChild = temp;
                temp.parent = curNode;
                return;
            } else {
                queue.add(curNode.lChild);
                queue.add(curNode.rChild);
            }

        }
    }

}

Java 代碼找后繼節(jié)點：

public class SuccessorNode {

    public FatherPointNode successorNode(FatherPointNode node){
        if(node==null){
            return null;
        }
        if(node.rChild!=null){
            return getLeftMost(node); //找右子樹的左邊界節(jié)點
        }else{
            while(node.parent!=null && node.parent.lChild!=node){
                node = node.parent;
            }
            return node.parent;
        }
    }

    public FatherPointNode getLeftMost(FatherPointNode node){
        if(node!=null){
            while(node.lChild!=null){
                node = node.lChild;
            }
            return node;
        }
        return null;
    }

    public static void main(String[] args) {
        FatherPointTree tree = new FatherPointTree(new FatherPointNode(0));
        tree.add(1);
        tree.add(2);
        tree.add(3);
        tree.add(4);
        SuccessorNode sn = new SuccessorNode();
        FatherPointNode result = sn.successorNode(tree.root.lChild.rChild);//節(jié)點4，后序節(jié)點應(yīng)該是為0;
        System.out.println(tree.root.lChild.rChild.value + " 后續(xù)節(jié)點：" + result.value);
        result = sn.successorNode(tree.root.lChild);//節(jié)點3，后序節(jié)點應(yīng)該是為1;
        System.out.println(tree.root.lChild.value + " 后續(xù)節(jié)點：" + result.value);
    }

}

先驅(qū)節(jié)點：節(jié)點有左子樹，那么左子樹的右節(jié)點一定是它的前驅(qū)。如果沒有左子樹，往上找，如果一個節(jié)點是父節(jié)點的右孩子，那么這個父節(jié)點就是前驅(qū)節(jié)點

序列化：

eg: 
   1
2     3
  4  5   6  7
先先序遍歷變成字符串：1_2_4_#_#_5_#_#_3_6_#_#_7_#_#_
用“#”來占住位置，用_可以區(qū)分節(jié)點，否則124，都在一起無法區(qū)分了

Java代碼實現(xiàn)：

public class SerialTree {
    //通過先序遍歷改編成序列化，原來打印處改為添加到字符串
    public static String  serialTree(Node curNode){
        if(curNode==null){
            return "#_"; //子節(jié)點為null用#占住
        }
        String res = "";
        res += curNode.value+"_"; 
        res += serialTree(curNode.lChild);
        res += serialTree(curNode.rChild);
        return res;
    }

    public static void main(String[] args) {
        Tree tree = new Tree(new Node(0));
        tree.add(1);
        tree.add(2);
        tree.add(3);
        tree.add(4);

        String result = serialTree(tree.root);
        System.out.println(result);
    }

}

序列化+反序列化完整代碼：

import java.util.LinkedList;
import java.util.Queue;

public class SerialTree {
    public static String  serialTree(Node curNode){
        if(curNode==null){
            return "#_";
        }
        String res = "";
        res += curNode.value+"_";
        res += serialTree(curNode.lChild);
        res += serialTree(curNode.rChild);
        return res;
    }
    //解析字符串，將節(jié)點信息存入到隊列中
    public static Node reconByPreString(String preString){
        String[] value = preString.split("_");
        Queue queue = new LinkedList();
        for (int i = 0; i < value.length; i++) {
            queue.offer(value[i]);
        }
        return reconPreOrder(queue);
    }
    //根據(jù)隊列的信息遞歸生成節(jié)點
    public static Node reconPreOrder(Queue queue){
        String value = queue.poll();
        if(value.equals("#")){
            return null;
        }
        Node head = new Node(Integer.valueOf(value));
        head.lChild = reconPreOrder(queue);
        head.rChild = reconPreOrder(queue);
        return head;
    }
    //采用先序遍歷打印來驗證反序列化結(jié)果是否正確
    public static void preOrder(Node node){
        if(node == null){
            return;
        }
        System.out.print(node.value + " ");
        preOrder(node.lChild);
        preOrder(node.rChild);
    }

    public static void main(String[] args) {
        Tree tree = new Tree(new Node(0));
        tree.add(1);
        tree.add(2);
        tree.add(3);
        tree.add(4);

        String result = serialTree(tree.root);
        System.out.println(result);
        Node head = reconByPreString(result);
        System.out.println("驗證反序列化樹(先序遍歷結(jié)果):");
        preOrder(head);
    }

}

同理可以學(xué)習(xí)中序、后序，層次化的序列化和反序列化

平衡二叉樹：一個樹的任一節(jié)點的左子樹和右子樹的高度差不超過1。

套路：遞歸函數(shù)
有什么特點？到達(dá)一個節(jié)點三次！

第一次來到這個節(jié)點，左子樹轉(zhuǎn)一圈完回到這個節(jié)點，右子樹轉(zhuǎn)一圈完回到這個節(jié)點

解題思路：以每個節(jié)點為頭的子樹判斷是否平衡，如果都平衡那么這個樹就是平衡的。
對于每個節(jié)點的判斷：

左樹是否平衡？如果不平衡后續(xù)就不用判斷了

右樹是否平衡？

左樹平衡和右樹平衡的情況下，需要左樹和右樹高度信息

因此遞歸函數(shù)需要返回兩個信息(通過一個對象返回，成員變量為 ①是否平衡 ②高度）

Java 代碼實現(xiàn):

//創(chuàng)建返回數(shù)據(jù)類：攜帶是否平衡信息和高度信息
class ReturnData{
    public boolean isB;
    public int high;
    public ReturnData(boolean isB, int high){
        this.isB = isB;
        this.high = high;
    }
}
public class IsBalanceTree {

    public static ReturnData processData(Node head){
        if(head==null){
            return new ReturnData(true, 0);
        }
        ReturnData leftData = processData(head.lChild);
        if(!leftData.isB){
            return new ReturnData(false,0);
        }
        ReturnData rightData = processData(head.rChild);
        if(!rightData.isB){
            return new ReturnData(false,0);
        }
        if(Math.abs(leftData.high-rightData.high)>1){
            return new ReturnData(false,0);
        }
        return new ReturnData(true,Math.max(leftData.high,rightData.high)+1);
    }

    public static boolean isBalance(Node head){
        return processData(head).isB;
    }

    public static void main(String[] args) {
        Tree tree = new Tree(new Node(0));
        tree.add(1);
        tree.add(2);
        tree.add(3);
        tree.add(4);
        Boolean result = isBalance(tree.root);
        System.out.println("是否是平衡樹？：" + result);
    }
}

二叉搜索樹：任何一個節(jié)點，左子樹都比它小，右子樹都比它大。

解題思路：二叉樹的中序遍歷節(jié)點是依次升序的就是搜索二叉樹。用非遞歸版本的中序遍歷中與前一個值進(jìn)行比較:一旦產(chǎn)生前一個節(jié)點比后一個節(jié)點要大，說明不是二叉搜索樹。

通常搜索二叉樹是不出現(xiàn)重復(fù)節(jié)點的，一般重復(fù)的節(jié)點的信息都是壓到一個節(jié)點內(nèi)的(如前綴樹)。

Java代碼實現(xiàn)：

import java.util.Stack;

public class IsBST {
    public static boolean isBST(Node head){
        if(head==null){
            return false;
        }
        Stack stack = new Stack<>();
        int value = Integer.MIN_VALUE;
        while(!stack.isEmpty() || head!=null){
            if(head!=null){   //注意判斷條件不要寫成了head.lChild!=null
                stack.push(head);
                head = head.lChild;
            }else{
                head = stack.pop();
                if(head.value
4.6 怎么判斷一棵樹是否是完全二叉樹
判斷方式：二叉樹按層遍歷
判斷依據(jù)：

一個節(jié)點有右孩子但是沒有左孩子 ，一定不是完全二叉樹
如果一個節(jié)點不是左右孩子都全，在1的條件下，后面遇到的所有節(jié)點都必須是葉節(jié)點，否則就不是完全二叉樹

Java 代碼實現(xiàn)：
import java.util.LinkedList;
import java.util.Queue;

public class IsCBT {

    public static boolean isCBT(Node head){
        if(head==null){
            return false;
        }
        Queue queue = new LinkedList();
        queue.offer(head);
        Node lChild = null;
        Node rChild = null;
        boolean leaf = false;
        while(!queue.isEmpty()){
            head = queue.poll();
            lChild = head.lChild;
            rChild = head.rChild;
            //判斷第一種情況：右孩子不為null，左孩子為null
            if((leaf && (lChild!=null && rChild!=null)) || (lChild==null && rChild!=null)){
                return false;
            }
            if(lChild!=null){
                queue.offer(lChild);
            }else{
                leaf = true; //出現(xiàn)情況：左孩子不為Null，右孩子為Null 或者 左右孩子都為Null，之后為葉節(jié)點。
            }
        }
        return true;
    }
}

補充知識：使用二叉樹實現(xiàn)堆比數(shù)組的節(jié)省了擴容代價
4.7 已知一棵完全二叉樹，求節(jié)點的個數(shù)
題目要求：時間復(fù)雜度低于O(n),n為這棵樹的節(jié)點個數(shù)
時間復(fù)雜度低于O(n)，說明無法采用廣度優(yōu)先遍歷的方式獲取
解題思路：

先遍歷左子樹的左邊界，記錄層數(shù)(完全二叉樹性質(zhì)，這個就是樹的層數(shù))，時間復(fù)雜度為O(logn)

遍歷右子樹的左邊界，是不是到了最后一層，如果到達(dá)最后一層那么左子樹就是滿二叉樹，如果不是，那么左子樹可能滿可能不滿。
如果右子樹的左邊界不是到最后一層(右子樹少一層：右子樹節(jié)點總數(shù)=1<<(h-level-1))，那么節(jié)點總數(shù)等于 1<<(h-level-1)+左樹遞歸求總數(shù)

補充知識點：如果一棵樹是一棵滿二叉樹，高度是l，那么節(jié)點個數(shù)是2^l -1
Java 代碼實現(xiàn)：
public class TreeNodeNum {
    public static int treeNodeNum(Node head){
        if(head==null){
            return 0;
        }
        return bs(head,1, mostLeftLevel(head,1));
    }

    //h:樹的深度， level：當(dāng)前層數(shù)
    public static int bs(Node node, int level, int h){
        //如果level==h，說明當(dāng)前節(jié)點是葉節(jié)點，節(jié)點個數(shù)為1
        if(level == h){
            return 1;
        }
        if(mostLeftLevel(node.rChild,level + 1) == h){
            System.out.println("左子樹滿");
            return (1<<(h-level)) + bs(node.rChild,level+1, h);
        }else{
            System.out.println("左子樹不一定滿");
            return (1 << (h-level-1)) + bs(node.lChild, level+1, h);
        }

    }

    public static  int mostLeftLevel(Node node,int level){
        while(node!=null){
            level++;
            node = node.lChild;
        }
        return level-1;
    }

    public static void main(String[] args) {
        Tree tree = new Tree(new Node(0));
        tree.add(1);
        tree.add(2);
        tree.add(3);
        tree.add(4);
        int result = treeNodeNum(tree.root);
        System.out.println("完全二叉樹的節(jié)點數(shù)目：" + result);
    }
}
結(jié)果：算法的時間復(fù)雜度 O(logn)平方