1 樹的定義

樹(Tree) 是 n(n>=0) 個結點的有限集, n=0 時稱為空樹, 在任意一顆非空樹當中,
(1) 有且只有一個特定的稱為根(Root) 的結點
(2) 當n>1時, 其余結點可分為 m(m>0) 個互不相交的優(yōu)先集 T1 T2 ...... Tm, 其余每一個集合本身又是一棵樹, 并且稱為根的子樹 (SubTree)

image.png

特別強調(diào)兩點 :
1 n>0時, 根節(jié)點是位移的, 不可能存在多個根節(jié)點
2 當m>0時, 子樹的個數(shù)并沒有限制, 但他們一定是互不相交的, 像下圖的兩個結構就不符合樹的定義, 因為他們都有相交的子樹

image.png

樹的結點包含一個暑假元素以及若干個指向其子樹的分支. 結點所擁有的子樹的個數(shù), 稱為結點的度(Degree)
度為0的結點稱為葉節(jié)點 或者終端結點, 度不為0的結點稱為非終端結點或者分支結點, 除根節(jié)點以外, 分支結點也稱為內(nèi)部結點, 數(shù)的度是樹內(nèi)部各結點的度的最大值。

2 樹的其他相關概念

結點的層級（level), 根為第一層, 根的孩子為第二層, 同一個父節(jié)點的結點互為堂兄弟結點。

image.png

森林（Forest） 是 m(m>=0) 棵互不相交的數(shù)的集合, 對數(shù)中每個節(jié)點而言, 其子樹的集合即為森林,
對于下圖1 來說, 兩個子樹就可以理解為森林

圖1

image.png

圖2

image.png

二叉樹

1 每個節(jié)點最多有兩棵子樹, 沒有子樹或者只有一顆子樹也是可以的
2 左子樹和右子樹是有順序的, 次序不能任意顛倒
3 即使樹中某結點只有一顆數(shù), 也要區(qū)分是右樹還是左樹

特殊二叉樹

1 斜樹
所有的結點都只有左子樹的二叉樹, 叫左斜樹, 所有結點都只有右子樹的, 叫右斜樹
2 滿二叉樹
在一顆二叉樹中, 如果所有分支結點都存在左子樹和右子樹, 并且所有葉子都在同一層上, 這樣的二叉樹稱為滿二叉樹

image.png

3 完全二叉樹
對于一棵具有n個結點的二叉樹, 如果編號為 i (1<= i <= n)的結點與同樣深度的二叉樹中編號為i的結點在二叉樹中完全相同, 則這棵二叉樹稱為完全二叉樹

image.png

二叉樹的遍歷

二叉樹的遍歷 : 從根節(jié)點出發(fā), 按照某種次序, 一次訪問二叉樹的所有結點, 使得每個節(jié)點被訪問一次 且 只被訪問一次

二叉樹的遍歷方法 :
1 前序遍歷 : 若二叉樹為空,則空操作返回, 否則先訪問跟結點, 然后前序遍歷左子樹, 再前序遍歷右子樹
如下圖, 遍歷順序為 ABDGHCEIF

image.png

2 中序遍歷: 若樹為空, 則空操作返回, 否則從根節(jié)點開始, 中序遍歷結點的左子樹, 然后訪問根節(jié)點, 最后中序遍歷右子樹 遍歷順序為 GDHBAEICF

image.png

3 后序遍歷:
規(guī)則是, 若樹為空, 則空操作返回, 否則從左到右先葉子后結點的方式遍歷訪問左右子樹, 最后訪問跟結點 , 如下圖, 遍歷順序是 GHDBIEFCA

image.png

4 層序遍歷:
規(guī)則: 若樹為空, 則空操作返回, 否則從數(shù)的第一層, 也就是根節(jié)點開始, 在同一層中, 按照從左到右的順序逐個訪問, 如下圖, 遍歷順序是 ABCDEFGHI

image.png

go 語言代碼

代碼參考地址:
https://gitee.com/babyb/data_srtuct/tree/master/010tree

數(shù)據(jù)結構

type Object interface{}

type node struct{
    data Object
    lchild *node 
    rchild *node
}

初始化二叉樹

    var a = &node{
        data : "A",
    }
    var b = &node{
        data : "B",
    }
    var c = &node{
        data : "C",
    }
    a.lchild = b;
    a.rchild = c;

    var d = &node{
        data : "D",
    }
    b.lchild=  d

    var e = &node{
        data : "E",
    }
    c.lchild = e 


    var f = &node{
        data : "F",
    }
    c.rchild = f 

    var g = &node{
        data : "G",
    }
    d.lchild = g

    var h = &node{
        data : "H",
    }
    d.rchild = h 

    var i = &node{
        data : "I",
    }
    e.lchild = i 

前序遍歷

//PreOrder 前序遍歷
func PreOrder(BiTree *node)  {
    if BiTree.data == nil{
        fmt.Println("二叉樹為空, 無法遍歷");
        return ;
    }
    // 先展示當前結點的元素
    fmt.Print(BiTree.data)

    ///再遍歷左子樹
    if BiTree.lchild != nil {
        PreOrder(BiTree.lchild)
    }

    //最后遍歷右子樹
    if BiTree.rchild != nil{
        PreOrder(BiTree.rchild)
    }
}

//PreOrder 中序遍歷
func midOrder(BiTree *node)  {
    //先遍歷左子樹
    if BiTree.lchild != nil {
        midOrder(BiTree.lchild)
    }

    if BiTree.data != nil {
        fmt.Print(BiTree.data)
    }
    //再遍歷右子樹
    if BiTree.rchild != nil {
        midOrder(BiTree.rchild)
    }
}

func afterOrder(BiTree *node){
    //后序遍歷左子樹

    if BiTree.lchild != nil {
        afterOrder(BiTree.lchild)
    }

    //后序遍歷右子樹
    if BiTree.rchild != nil {
        afterOrder(BiTree.rchild)
    }

    //最后是自己
    if BiTree.data != nil {
        fmt.Print(BiTree.data)
    }
}

層序遍歷

//層序遍歷
func layerOrder(BiTree *node){
    // 借助隊列實現(xiàn): 1 把根節(jié)點入隊,   a 
    //2 彈出根節(jié)點 a , 并把 a結點的子結點 bc 入隊
    //3彈出結點b , 把他的子節(jié)點加入隊列,  
    // 如此操作, 直到隊列為空
    q := queue.InitQueue();
    if BiTree.data != nil {
        //BiTree 前面加上* , 對 指針取值
        q.Push(*BiTree)
    }

    for !q.Empty(){
        n,_ := q.Pop();
        //強制轉換一下類型
        node := n.(node);
        fmt.Print(node.data);
        if node.lchild != nil {
            q.Push(*node.lchild)
        }
        if node.rchild != nil {
            q.Push(*node.rchild)
        }
    }
}