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

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

每個(gè)節(jié)點(diǎn)有零個(gè)或多個(gè)子節(jié)點(diǎn)；

沒(méi)有父節(jié)點(diǎn)的節(jié)點(diǎn)稱為根節(jié)點(diǎn)；

每一個(gè)非根節(jié)點(diǎn)有且只有一個(gè)父節(jié)點(diǎn)；

除了根節(jié)點(diǎn)外，每個(gè)子節(jié)點(diǎn)可以分為多個(gè)不相交的子樹(shù)；

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

樹(shù)的度：一棵樹(shù)中，最大的節(jié)點(diǎn)的度稱為樹(shù)的度；

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

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

孩子節(jié)點(diǎn)或子節(jié)點(diǎn)：一個(gè)節(jié)點(diǎn)含有的子樹(shù)的根節(jié)點(diǎn)稱為該節(jié)點(diǎn)的子節(jié)點(diǎn)；

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

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

樹(shù)的高度或深度：樹(shù)中節(jié)點(diǎn)的最大層次；

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

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

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

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

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

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

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

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

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

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

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

xml，html等，那么編寫(xiě)這些東西的解析器的時(shí)候，不可避免用到樹(shù)

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

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

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

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

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

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

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

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

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

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

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

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

Node節(jié)點(diǎn)類：

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é)點(diǎn)初始化
    public Tree(Node node){
        root = node;
    }
    //樹(shù)中通過(guò)廣度優(yōu)先遍歷的方式尋找空位置加新節(jié)點(diǎn)
    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);
            }

        }
    }
}

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

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

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

無(wú)論是否是遞歸方式都用到了棧(函數(shù)棧也是棧)：因?yàn)闃?shù)的結(jié)構(gòu)是從上到下訪問(wèn)，如果要返回去訪問(wèn)另一處的節(jié)點(diǎn)，那么必須要有棧來(lái)“記憶”。

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

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

Java代碼實(shí)現(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 代碼實(shí)現(xiàn)(非遞歸方式)：

public void preOrderUnRecur(Node head){
    System.out.print("preOrder:");
    if(head!=null){
        //利用棧來(lái)實(shí)現(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);
            }
        }
    }
}

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

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

Java代碼實(shí)現(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實(shí)現(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;
            }
        }
    }
}

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

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

Java代碼實(shí)現(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代碼實(shí)現(xiàn)(非遞歸方式：采用輔助空間方式,把先序(中右左)存儲(chǔ)到輔助棧，然后根據(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);  //與先序的不同：先序打印，后序存儲(chǔ)起來(lái)
            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 + " ");
        }
    }
}

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

通過(guò)一個(gè)隊(duì)列的方法來(lái)實(shí)現(xiàn)

從樹(shù)的root開(kāi)始，從上到下從從左到右遍歷整個(gè)樹(shù)的節(jié)點(diǎn)

def breadth_travel(self, root):
        """利用隊(duì)列實(shí)現(xiàn)樹(shù)的層次遍歷"""
        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)

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

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

Morris 遍歷規(guī)則：

來(lái)到當(dāng)前節(jié)點(diǎn)，記為cur，如果cur無(wú)左孩子，cur向右移動(dòng)cur = cur.right

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

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){ //有左孩子，找到左子樹(shù)的最右節(jié)點(diǎn)
            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é)點(diǎn)走了，就是中序遍歷
        cur = cur.right;
    }
}

如果一個(gè)節(jié)點(diǎn)有左子樹(shù)，morris能回到節(jié)點(diǎn)兩次。如果沒(méi)有左子樹(shù)，只到節(jié)點(diǎn)一次。

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é)點(diǎn)時(shí)候打印的，但是morris沒(méi)有回到節(jié)點(diǎn)第三次的。
怎么做？
先去關(guān)注能回到節(jié)點(diǎn)兩次的節(jié)點(diǎn)，逆序打印它左子樹(shù)的右邊界。退出函數(shù)時(shí)多帶帶打印整棵樹(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();
}

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

先序 + 中序
思想：

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

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

通過(guò)重復(fù)2，可以畫(huà)出一個(gè)樹(shù)

中序+后序也可以

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

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

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

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

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

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)建特殊的樹(shù)類：

public class FatherPointTree {

    public FatherPointNode root;
    //根節(jié)點(diǎn)初始化
    public FatherPointTree(FatherPointNode node){
        root = node;
    }
    //樹(shù)中通過(guò)廣度優(yōu)先遍歷的方式尋找空位置加新節(jié)點(diǎn)
    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; //與原來(lái)的樹(shù)不同地方：添加父節(jié)點(diǎn)
                return;
            } else if (curNode.rChild == null) {
                curNode.rChild = temp;
                temp.parent = curNode;
                return;
            } else {
                queue.add(curNode.lChild);
                queue.add(curNode.rChild);
            }

        }
    }

}

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

public class SuccessorNode {

    public FatherPointNode successorNode(FatherPointNode node){
        if(node==null){
            return null;
        }
        if(node.rChild!=null){
            return getLeftMost(node); //找右子樹(shù)的左邊界節(jié)點(diǎn)
        }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é)點(diǎn)4，后序節(jié)點(diǎn)應(yīng)該是為0;
        System.out.println(tree.root.lChild.rChild.value + " 后續(xù)節(jié)點(diǎn)：" + result.value);
        result = sn.successorNode(tree.root.lChild);//節(jié)點(diǎn)3，后序節(jié)點(diǎn)應(yīng)該是為1;
        System.out.println(tree.root.lChild.value + " 后續(xù)節(jié)點(diǎn)：" + result.value);
    }

}

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

序列化：

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

Java代碼實(shí)現(xiàn)：

public class SerialTree {
    //通過(guò)先序遍歷改編成序列化，原來(lái)打印處改為添加到字符串
    public static String  serialTree(Node curNode){
        if(curNode==null){
            return "#_"; //子節(jié)點(diǎn)為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é)點(diǎn)信息存入到隊(duì)列中
    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ù)隊(duì)列的信息遞歸生成節(jié)點(diǎn)
    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;
    }
    //采用先序遍歷打印來(lái)驗(yàn)證反序列化結(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("驗(yàn)證反序列化樹(shù)(先序遍歷結(jié)果):");
        preOrder(head);
    }

}

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

平衡二叉樹(shù)：一個(gè)樹(shù)的任一節(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的高度差不超過(guò)1。

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

第一次來(lái)到這個(gè)節(jié)點(diǎn)，左子樹(shù)轉(zhuǎn)一圈完回到這個(gè)節(jié)點(diǎn)，右子樹(shù)轉(zhuǎn)一圈完回到這個(gè)節(jié)點(diǎn)

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

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

右樹(shù)是否平衡？

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

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

Java 代碼實(shí)現(xiàn):

//創(chuàng)建返回?cái)?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("是否是平衡樹(shù)？：" + result);
    }
}

二叉搜索樹(shù)：任何一個(gè)節(jié)點(diǎn)，左子樹(shù)都比它小，右子樹(shù)都比它大。

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

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

Java代碼實(shí)現(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){   //注意判斷條件不要寫(xiě)成了head.lChild!=null
                stack.push(head);
                head = head.lChild;
            }else{
                head = stack.pop();
                if(head.value
4.6 怎么判斷一棵樹(shù)是否是完全二叉樹(shù)
判斷方式：二叉樹(shù)按層遍歷
判斷依據(jù)：

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

Java 代碼實(shí)現(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é)點(diǎn)。
            }
        }
        return true;
    }
}

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

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

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

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

    //h:樹(shù)的深度， level：當(dāng)前層數(shù)
    public static int bs(Node node, int level, int h){
        //如果level==h，說(shuō)明當(dāng)前節(jié)點(diǎn)是葉節(jié)點(diǎn)，節(jié)點(diǎn)個(gè)數(shù)為1
        if(level == h){
            return 1;
        }
        if(mostLeftLevel(node.rChild,level + 1) == h){
            System.out.println("左子樹(shù)滿");
            return (1<<(h-level)) + bs(node.rChild,level+1, h);
        }else{
            System.out.println("左子樹(shù)不一定滿");
            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("完全二叉樹(shù)的節(jié)點(diǎn)數(shù)目：" + result);
    }
}
結(jié)果：算法的時(shí)間復(fù)雜度 O(logn)平方