樹和樹的算法

RaoMeng 發(fā)布于2019-08-19 11:08 / 742人閱讀

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

樹和樹的算法 一、樹 1.1 樹的概念

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

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

沒有父節(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è)不相交的子樹；

1.2 樹的術(shù)語

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

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

葉節(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)含有的子樹的根節(jié)點(diǎn)稱為該節(jié)點(diǎn)的子節(jié)點(diǎn)；

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

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

樹的高度或深度：樹中節(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)為根的子樹中任一節(jié)點(diǎn)都稱為該節(jié)點(diǎn)的子孫。

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

1.3 樹的種類 1.3.1

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

1.3.2 有序樹

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

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

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

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

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

1.4 樹的存儲(chǔ)與表示

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

1.5 常見的一些樹的應(yīng)用場(chǎng)景

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

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

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

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

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

二、二叉樹 2.1 二叉樹的基本概念

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

2.2 二叉樹的性質(zhì)(特性)

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

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

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

2.3 二叉樹的節(jié)點(diǎn)表示以及樹的創(chuàng)建 2.3.1 Python 建樹

通過使用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
樹的創(chuàng)建,創(chuàng)建一個(gè)樹的類，并給一個(gè)root根節(jié)點(diǎn)，一開始為空，隨后添加節(jié)點(diǎn)

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

    def add(self, elem):
        """為樹添加節(jié)點(diǎn)"""
        node = Node(elem)
        #如果樹是空的，則對(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:
                    #如果左右子樹都不為空，加入隊(duì)列繼續(xù)判斷
                    queue.append(cur.lchild)
                    queue.append(cur.rchild)

2.3.2 Java的建樹

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;
    }
    //樹中通過廣度優(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);
            }

        }
    }
}

三、二叉樹的遍歷

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

3.1 深度優(yōu)先遍歷

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

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

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

3.1.1 先序遍歷

在先序遍歷中，我們先訪問根節(jié)點(diǎn)，然后遞歸使用先序遍歷訪問左子樹，再遞歸使用先序遍歷訪問右子樹
根節(jié)點(diǎn)->左子樹->右子樹
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){
        //利用棧來實(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);
            }
        }
    }
}

3.1.2 中序遍歷

在中序遍歷中，我們遞歸使用中序遍歷訪問左子樹，然后訪問根節(jié)點(diǎn)，最后再遞歸使用中序遍歷訪問右子樹
左子樹->根節(jié)點(diǎn)->右子樹
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;
            }
        }
    }
}

3.1.3 后序遍歷

在后序遍歷中，我們先遞歸使用后序遍歷訪問左子樹和右子樹，最后訪問根節(jié)點(diǎn)
左子樹->右子樹->根節(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ǔ)起來
            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 + " ");
        }
    }
}

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

3.2 廣度優(yōu)先遍歷(層次遍歷)

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

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

def breadth_travel(self, root):
        """利用隊(duì)列實(shí)現(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)

3.3 Morris 遍歷

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

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

Morris 遍歷規(guī)則：

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

如果cur有左孩子：找到左子樹上最右節(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){ //有左孩子，找到左子樹的最右節(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)有左子樹，morris能回到節(jié)點(diǎn)兩次。如果沒有左子樹，只到節(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沒有回到節(jié)點(diǎn)第三次的。
怎么做？
先去關(guān)注能回到節(jié)點(diǎn)兩次的節(jié)點(diǎn)，逆序打印它左子樹的右邊界。退出函數(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)整回來，這樣就沒有引入額外空間復(fù)雜度

四、樹的題目 4.1 如何畫出一棵樹

先序 + 中序
思想：

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

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

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

中序+后序也可以

4.2 二叉樹中找到一個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)

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

解決思路：如果一個(gè)節(jié)點(diǎn)有右子樹，那么右子樹的左邊界(整個(gè)樹最左下角)節(jié)點(diǎn)一定是它的后繼節(jié)點(diǎn)；如果沒有右子樹，通過這個(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)建特殊的樹類：

public class FatherPointTree {

    public FatherPointNode root;
    //根節(jié)點(diǎn)初始化
    public FatherPointTree(FatherPointNode node){
        root = node;
    }
    //樹中通過廣度優(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; //與原來的樹不同地方：添加父節(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); //找右子樹的左邊界節(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)有左子樹，那么左子樹的右節(jié)點(diǎn)一定是它的前驅(qū)。如果沒有左子樹，往上找，如果一個(gè)節(jié)點(diǎn)是父節(jié)點(diǎn)的右孩子，那么這個(gè)父節(jié)點(diǎn)就是前驅(qū)節(jié)點(diǎn)

4.3 二叉樹的序列化與反序列化

序列化：

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

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

public class SerialTree {
    //通過先序遍歷改編成序列化，原來打印處改為添加到字符串
    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;
    }
    //采用先序遍歷打印來驗(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)證反序列化樹(先序遍歷結(jié)果):");
        preOrder(head);
    }

}

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

4.4 判斷二叉樹是否是平衡二叉樹

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

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

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

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

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

右樹是否平衡？

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

因此遞歸函數(shù)需要返回兩個(gè)信息(通過一個(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("是否是平衡樹？：" + result);
    }
}

4.5 如何判斷一棵樹是二叉搜索樹

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

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

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

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

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

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

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

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

補(bǔ)充知識(shí)點(diǎn)：如果一棵樹是一棵滿二叉樹，高度是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:樹的深度， level：當(dāng)前層數(shù)
    public static int bs(Node node, int level, int h){
        //如果level==h，說明當(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("左子樹滿");
            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é)點(diǎn)數(shù)目：" + result);
    }
}
結(jié)果：算法的時(shí)間復(fù)雜度 O(logn)平方

GPU云服務(wù)器云服務(wù)器樹的存儲(chǔ) python樹的繪制二叉樹的遍歷二叉樹的存儲(chǔ)

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/77052.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

RaoMeng

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

tensorflow

閱讀 1860·2023-04-26 02:51
手把手教你用echarts和SovitChart開發(fā)帶漸變色的柱狀圖

閱讀 2901·2021-09-10 10:50
Windows Server 2022 正式版發(fā)布(英文版、簡(jiǎn)體中文版鏡像文件下載)

閱讀 3132·2021-09-01 10:48
CSS3中的box-sizing

閱讀 3691·2019-08-30 15:53
滑動(dòng)穿透(鎖body)終極探索

閱讀 1857·2019-08-29 18:40
PWA 時(shí)代的移動(dòng)端圖片優(yōu)化新思路

閱讀 433·2019-08-29 16:16
前端每周清單半年盤點(diǎn)之 CSS 篇

閱讀 2057·2019-08-29 13:21
惡心的兼容問題：完美解決IE(IE6/IE7/IE8)不兼容HTML5標(biāo)簽的問題

閱讀 1841·2019-08-29 11:07

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來選購！

樹和樹的算法

相關(guān)文章