樹

樹的定義

樹（Tree）是n（n≥0）個結點的有限集，它或為空樹（n = 0）；或為非空樹，對于非空樹T：
- 有且僅有一個稱之為根的結點；
- 除根結點以外的其餘結點可分為m（m＞0）個互不相交的有限集T1, T2, …, Tm, 其中每一個集合本身又是一棵樹，并且稱為根的子樹（SubTree）。
樹是n個結點的有限集

樹的其他表示方式

樹的概念

每個節點有零個或多個子節點；
沒有父節點的節點稱為根節點；
每一個非根節點有且隻有一個父節點；
除了根節點外，每個子節點可以分為多個不相交的子樹；

樹的基本術語

根：即根結點(沒有前驅)
葉子：即終端結點(沒有後繼)
節點：即樹的資料元素
節點的度：一個節點含有的子樹的個數稱為該節點的度；
樹的度：一棵樹中，最大的節點的度稱為樹的度；
葉節點或終端節點：度為零的節點；
分支節點：即度不為0的結點（也稱為内部結點）
父親節點或父節點：若一個節點含有子節點，則這個節點稱為其子節點的父節點；
孩子節點或子節點：一個節點含有的子樹的根節點稱為該節點的子節點；
兄弟節點：具有相同父節點的節點互稱為兄弟節點；
節點的層次：從根開始定義起，根為第1層，根的子節點為第2層，以此類推；
樹的高度或深度：樹中節點的最大層次；
堂兄弟節點：父節點在同一層的節點互為堂兄弟；
節點的祖先：從根到該節點所經分支上的所有節點；
子孫：以某節點為根的子樹中任一節點都稱為該節點的子孫。
森林：由m（m>=0）棵互不相交的樹的集合稱為森林；

樹的種類

無序樹：樹中任意節點的子節點之間沒有順序關系，這種樹稱為無序樹，也稱為自由樹；
有序樹：樹中任意節點的子節點之間有順序關系，這種樹稱為有序樹；
二叉樹：每個節點最多含有兩個子樹的樹稱為二叉樹；
完全二叉樹：對于一顆二叉樹，假設其深度為d(d>1)。除了第d層外，其它各層的節點數目均

已達最大值，且第d層所有節點從左向右連續地緊密排列，這樣的二叉樹被稱為完全二叉樹，其中滿二叉樹的定義是所有葉節點都在最底層的完全二叉樹;

平衡二叉樹（AVL樹）：當且僅當任何節點的兩棵子樹的高度差不大于1的二叉樹；
排序二叉樹（二叉查找樹（英語：Binary Search Tree），也稱二叉搜尋樹、有序二叉

樹）；

霍夫曼樹（用于資訊編碼）：帶權路徑最短的二叉樹稱為哈夫曼樹或最優二叉樹；
B樹：一種對讀寫操作進行優化的自平衡的二叉查找樹，能夠保持資料有序，擁有多餘兩個子樹。

常見應用場景

xml，html等，那麼編寫這些東西的解析器的時候，不可避免用到樹
路由協定就是使用了樹的算法
mysql資料庫索引
檔案系統的目錄結構
是以很多經典的AI算法其實都是樹搜尋，此外機器學習中的decision tree也是樹結構

二叉樹

二叉樹是每個節點最多有兩個子樹的樹結構。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）
- 除根結點以外的其餘結點分為兩個互不相交的子集T1和T2，分别稱為T的左子樹和右子樹，且T1和T2本身又都是二叉樹。
基本特點
- 結點的度小于等于2
- 有序樹（子樹有序，不能颠倒）

二叉樹的性質

在二叉樹的第i層上至多有2^(i-1)個結點
深度為k的二叉樹至多有2^(k-1)個結點
對于任何一棵二叉樹，若2度的結點數有n2個，則葉子數n0必定為n2＋1 （即n0=n2+1）
具有n個結點的完全二叉樹的深度必為[log2n]＋1
對完全二叉樹，若從上至下、從左至右編号，則編号為i 的結點，其左孩子編号必為2i，其右孩子編号必為2i＋1；其雙親的編号必為i/2。

二叉樹節點表示

案例ly01.py

二叉樹周遊

深度優先，一般用遞歸
- 先序(Preorder)
- 中序(Inorder)
- 後序(Postorder)
廣度優先，一般用隊列

滿二叉樹

滿二叉樹_百度百科
除最後一層無任何子節點外，每一層上的所有結點都有兩個子結點的二叉樹。
國内教程定義：一個二叉樹，如果每一個層的結點數都達到最大值，則這個二叉樹就是滿二叉樹。也就是說，如果一個二叉樹的層數為K，且結點總數是(2^k) -1 ，則它就是滿二叉樹。
- 滿足等比數列公式，具有如下性質
  - 滿二叉樹的結點數一定是奇數個
  - 第i層上的結點數為：2^i-1
  - 層數為k的滿二叉樹的葉子結點個數（最後一層）: 2^k-1
國外（國際）定義：a binary tree T is full if each node is either a leaf or possesses exactly two childnodes.（如果一棵二叉樹的結點要麼是葉子結點，要麼它有兩個子結點，這樣的樹就是滿二叉樹。(一棵滿二叉樹的每一個結點要麼是葉子結點，要麼它有兩個子結點，但是反過來不成立，因為完全二叉樹也滿足這個要求，但不是滿二叉樹)）
- 度為0或者2，不存在度為1的結點

滿二叉樹和完全二叉樹的差別

滿二叉樹是葉子一個也不少的樹，而完全二叉樹雖然前n-1層是滿的，但最底層卻允許在右邊缺少連續若幹個結點。滿二叉樹是完全二叉樹的一個特例。

C++代碼實作

#include<iostream>
#include<queue>
using namespace std;

#define OVERFLOW -2 
#define OK 1
#define NULL 0
#define ERROR -1

#define MAXSIZE 100

typedef int Status;

typedef char TelemType;

/*------------------二叉樹順序存儲----------------*/
/*
适于存滿二叉樹和完全二叉樹
*/
// typedef TelemType SqBiTree[MAXSIZE];

// SqBiTree bt;  // 包含100存放TelemType類型資料的數組

/*-----------------二叉樹鍊式存儲------------------*/

/*
二叉連結清單
*/
typedef struct BiTNode {
    TelemType data;  // 結點資料域
    struct BiTNode* lchild, * rchild;  // 左右子樹指針 
    int flag;  // 後序周遊标志位
}BiTNode, * BiTree;

typedef BiTree SElemType;

typedef struct {
    BiTNode* link;
    int tag;  // 後序周遊标志位
}BElemType;


// 順序棧結構體
typedef struct {
    SElemType* base;
    SElemType* top;
    int stacksize;
}SqStack;

// 順序棧初始化
Status InitStack(SqStack& S) {
    S.base = new SElemType[MAXSIZE];
    if (!S.base) return OVERFLOW;
    S.top = S.base;
    S.stacksize = MAXSIZE;
    return OK;
}

// 判斷順序棧是否為空
bool StackEmpty(SqStack S) {
    if (S.top == S.base) return true;
    else return false;
}

// 判斷是否為滿棧
bool StackFull(SqStack S) {
    if (S.top - S.base >= S.stacksize)
        return true;
    else return false;
}

// 入棧
Status Push(SqStack& S, BiTree e) {
    if (StackFull(S))  // 滿棧 
        return ERROR;
    *S.top++ = e;
    // *S.top = e;
    // S.top ++;
    return OK;
}

// 出棧
Status Pop(SqStack& S, BiTree& e) {
    if (StackEmpty(S))  // 棧空
        return ERROR;
    e = *--S.top;
    // S.top --;
    // e = *S.top;
    return OK;
}

/*
# 周遊規則
- 若二叉樹為空樹，則空操作
- DLR-先序周遊，先根再左再右
- LDR-中序周遊，先左再根再右
- LRD-後序周遊，先左再右再根
*/


/*--------先序(根)周遊---------*/
// 遞歸算法
/*
若二叉樹為空，則空操作
否則:
    通路根結點 (D)
    中序周遊左子樹 (L)
    中序周遊右子樹 (R)
*/
void PreOrder(BiTree T) {
    if (T) {
        cout << T->data;
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

// 非遞歸算法
void PreOrder_1(BiTree T) {
    SqStack S;
    InitStack(S);
    BiTree p = T;
    while (p || !StackEmpty(S)) {
        // p非空且棧非空
        if (p) {
            /*
            輸出元素
            儲存入棧
            p = p->lchild
            */
            cout << p->data;
            Push(S, p);
            p = p->lchild;
        }
        else {
            /*
            出棧到p
            p = p->rchild
            */
            Pop(S, p);
            p = p->rchild;
        }
    }
}


/*--------中序(根)周遊---------*/
// 遞歸算法
/*
若二叉樹為空，則空操作
否則:
    中序周遊左子樹 (L)
    通路根結點 (D)
    中序周遊右子樹 (R)
*/
void InOrder(BiTree T) {
    if (T) {
        InOrder(T->lchild);
        cout << T->data;
        InOrder(T->rchild);
    }
}

// 非遞歸算法
void InOrder_1(BiTree T) {
    BiTree p = T;
    SqStack S;
    InitStack(S);
    while (p || !StackEmpty(S)) {
        if (p) {
            /*
            儲存--入棧
            p = p->lchild
            */
            Push(S, p);
            p = p->lchild;
        }
        else {
            /*
            出棧到p
            輸出p->data
            p = p->rchild
            */
            Pop(S, p);
            cout << p->data;
            p = p->rchild;
        }
    }
}




/*
/*--------後序(根)周遊---------*/
// 遞歸算法
/*
若二叉樹為空，則空操作
否則:
    中序周遊左子樹 (L)
    中序周遊右子樹 (R)
    通路根結點 (D)
*/
void PostOrder(BiTree T) {
    if (T) {
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        cout << T->data;
    }
}

// 非遞歸算法
void PostOrder_1(BiTree T) {
    /*
    此函數應将資料類型改為"結點+标志位"，即上面代碼中BElemType類型
    但由于修改類型後，需重新改寫棧相關函數，故将标志位作為結構體BiTNode參數
    */
    BiTree p = T;
    SqStack S;
    // BElemType w;
    InitStack(S);
    while (p || !StackEmpty(S)) {
        if (p) {
            /*
            儲存--入棧 flag = 1（結構體 p,flag）
            p = p->lchild
            */
            // w.link = p;
            // Push(S,w);
            Push(S, p);
            p->flag = 1;
            // w.tag = 1;
            p = p->lchild;
        }
        else {
            /*
            出棧到p
            switch(flag){
                case '1':
                    入棧 flag = 2
                    p = p->rchild
                case '2'
                    輸出 p->data
                    p = NULL
            }
            儲存--入棧
            p = p->rchild;
            */
            // Pop(S, w);
            Pop(S, p);
            // p = w.link;
            switch (p->flag) {
            case 1:
                p->flag = 2;
                // w.tag = 2;
                Push(S, p);
                p = p->rchild;
                break;
            case 2:
                cout << p->data;
                // 強制置空
                p = NULL;
                break;
            }
        }
    }
}


// 求二叉樹葉子結點的個數
int CountLeaf(BiTree T) {
    // 先序周遊
    // 此處必須為static類型，遞歸會調用自身，隻賦一次值
    static int count = 0;
    if (T) {
        if (!T->lchild && !T->rchild)
            count++;
        CountLeaf(T->lchild);
        CountLeaf(T->rchild);
    }
    return count;
}

// 求二叉樹深度
/*
1. 求左二叉樹深度
2. 求右二叉樹深度
3. 取最大值加1
*/
int Depth(BiTree T) {
    // 後序周遊
    int dl, dr, d;
    if (!T)
        d = 0;
    else {
        dl = Depth(T->lchild);
        dr = Depth(T->rchild);
        d = 1 + (dl > dr ? dl : dr);
    }
    return d;
}

// 複制二叉樹
BiTree Copy(BiTree T) {
    BiTree t, newl, newr;
    if (!T) {
        t = NULL;
        return t;
    }
    else {
        if (!T->lchild)
            newl = NULL;
        else
            newl = Copy(T->lchild);
        if (!T->rchild)
            newr = NULL;
        else
            newr = Copy(T->rchild);
        t = new BiTNode;
        t->data = T->data;
        t->lchild = newl;
        t->rchild = newr;
    }
    return t;
}

// 先序建立二叉樹
Status CreateBiTree(BiTree& T) {
    char ch;
    cin >> ch;
    if (ch == '#') T = NULL;
    else {
        if (!(T = new BiTNode)) exit(OVERFLOW);
        T->data = ch;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
    return OK;
}

int main() {
    // 測試
    BiTree T, t;
    int n;
    CreateBiTree(T);

    
    // 遞歸周遊
    cout << "先序周遊為：" << endl;
    PreOrder(T);
    cout << endl << "中序周遊為：" << endl;
    InOrder(T);
    cout << endl << "後序周遊為： " << endl;
    PostOrder(T);
    cout << endl;

    // 葉子結點個數測試
    cout << "葉子結點個數為: " << CountLeaf(T) << endl;

    // 求樹深度測試
    cout << "樹的深度為：" << Depth(T) << endl;

    // 複制測試
    t = Copy(T);
    cout << "t 的先序周遊為： " << endl;
    PreOrder(t);
    cout << endl;
    


    /*
    // 非遞歸周遊
    cout << "先序周遊為：" << endl;
    PreOrder_1(T);
    cout << endl;

    cout << "中序周遊為：" << endl;
    InOrder_1(T);
    cout << endl;

    cout << "後序周遊為：" << endl;
    PostOrder_1(T);
    cout << endl;
    */

    return 0;
}

ab##c##
先序周遊為：
abc
中序周遊為：
bac
後序周遊為：
bca
葉子結點個數為: 2
樹的深度為：2
t 的先序周遊為：
abc

python代碼實作

'''案例ly01.py'''

class Node(object):
    '''節點類'''
    def __init__(self, elem=-1, lchild=None, rchild=None):
        self.elem = elem;
        self.lchild = lchild
        self.rchild = rchild

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

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


    def preorder(self, root):
        '''遞歸實作先序周遊'''
        if root == None:
            return
        print(root.elem)
        self.preorder(root.lchild)
        self.preorder(root.rchild)

    def inorder(self, root):
        '''遞歸實作中序周遊'''
        if root == None:
            return
        self.inorder(root.lchild)
        print(root.elem)
        self.inorder(root.rchild)

    def postorder(self, root):
        '''遞歸實作後序周遊'''
        if root == None:
            return
        self.postorder(root.lchild)
        self.postorder(root.rchild)
        print(root.elem)

    def breadth_travel(self, root):
        '''利用隊列實作樹的層次周遊'''
        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)

if __name__ == '__main__':
    t = Tree()

    for i in range(10):
        t.add(i)

    t.preorder(t.root)
    print('*' * 20)
    t.inorder(t.root)
    print('*' * 20)
    t.postorder(t.root)
    print('*' * 20)
    t.breadth_travel(t.root)

0
1
3
7
8
4
9
2
5
6
********************
7
3
8
1
9
4
0
5
2
6
********************
7
8
3
9
4
1
5
6
2
0
********************
0
1
2
3
4
5
6
7
8
9
[Finished in 0.1s]

線索二叉樹

對一個非線性結構進行線性化操作，使每個結點（除第一個和最後一個外）在這些線性序列中有且僅有一個直接前驅和直接後繼。
n 個結點的二叉連結清單中必定存在 n+1 個空鍊域，是以可利用這些空鍊域來存放結點的前驅和後繼資訊。
二叉連結清單加一頭結點，lchild 域的指針指向二叉樹的根結點，rchild 域的指針指向中序周遊時通路的最後一個結點。
二叉樹中序序列中第一個結點的lchild 域的指針和最後一個結點rchild 域的指針均指向頭結點。

/*---------二叉樹的二叉線索存儲表示---------*/
typedef int ElemType;
typedef enum PointerTag {Link, Thread};  // Link==0:指針，Thread==1:線索

typedef struct BiThrNode {
    ElemType data;  // 資料域
    struct BiThrNode* lchild, * rchild;  // 左右孩子指針
    PointerTag LTag, Rtag;  // 左右标志
}BiThrNode, * BiThrTree;

線索二叉樹的術語

線索：指向結點前驅和後繼的指針
線索連結清單：加上線索二叉連結清單
線索二叉樹：加上線索的二叉樹（圖形式樣）
線索化：對二叉樹以某種次序周遊使其變為線索二叉樹的過程

/*----------以結點p為根的子樹中序線索化---------*/
void InThreading(BiThrTree p, BiThrNode *&pre) {
    if (p) {
        InThreading(p->lchild, pre);  // 遞歸線索化左子樹
        if (!p->lchild) {
            p->LTag = Thread;  // 前驅線索化
            p->lchild = pre;  // p的左孩子指針指向pre(前驅)
        }
        if (!pre->rchild) {
            // 前驅無右孩子
            pre->RTag = Thread;  // 後繼線索
            pre->rchild = p;  // 前驅右孩子指向後繼
        }
        pre = p;
        InThreading(p->rchild, pre);  // 遞歸線索化右子樹
    }
}

樹和森林

樹的存儲結構

雙親表示法
- 以一組連續空間存儲樹的結點，同時在結點中附設一個指針，存放雙親結點在連結清單中的位置。
- 特點：找雙親容易，找孩子難
孩子連結清單表示法
- 每個結點有多個指針域，分别指向其子樹的根。

樹的二叉連結清單(孩子-兄弟）存儲表示法

/*----樹的存儲結構->二叉連結清單表示法----*/
typedef struct CSNode {
    ElemType data;
    struct CSNode* firstchild, * nextsibling;
}CSNode, * CSTree;

将樹轉化為二叉樹

加線：在兄弟之間加一連線
抹線：對每個結點，除了其左孩子外，去除其與其餘孩子之間的連線
旋轉：以樹的根結點為軸心，将整棵樹順時針轉45°

樹轉換成的二叉樹其右子樹一定為空

将二叉樹轉換成樹

加線：若p結點是雙親結點的左孩子，則将p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都與p的雙親用線連起來
抹線：抹掉原二叉樹中雙親與右孩子之間的連線
調整：将結點按層次排列,形成樹結構

樹的先序周遊與二叉樹先序周遊相同

樹的後序周遊相當于對應二叉樹的中序周遊

資料結構——樹和二叉樹樹二叉樹線索二叉樹樹和森林

樹

樹的定義

樹的概念

樹的基本術語

樹的種類

常見應用場景

二叉樹

二叉樹的性質

二叉樹節點表示

二叉樹周遊

滿二叉樹

滿二叉樹和完全二叉樹的差別

線索二叉樹

線索二叉樹的術語

樹和森林

樹的存儲結構

将樹轉化為二叉樹

将二叉樹轉換成樹

繼續閱讀

無人機--飛控科普

neo4j之cypher使用文檔

Dijkstra--簡易版（最短路徑）

C經典書籍筆記——C陷阱與缺陷②(文法陷阱之優先級)一、錯誤案列二、優先級規律

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Cloud Studio初體驗

使用 ctypes 進行 Python 和 C 的混合程式設計

【python】【資料處理】畫多元資料分布圖

mysql使用source指令導入.sql檔案

線性表之順序表的實作

C++判斷素數、求最大公約數代碼判斷一個數是否為素數求兩個數的最大公約數

SequoiaDB巨杉資料庫C++驅動概述

【python】netconf協定對接管理裝置

「Python 網絡自動化」NETCONF —— Python 使用 NETCONF 管理配置 H3C 網絡裝置

在python中建立excel并寫入

hdu7108哈希