自由樹：
一棵自由樹 $\color{red}{Tf}$ 可定義為一個二元組
$\color{red}{Tf = (V, E) }$
其中 V = {v1, ..., vn} 是由 n (n＞0) 個元素組成的有限非空集合，稱為頂點集合。 $\color{red}{E = {(vi, vj) | vi, vj ∈V, 1≤i, j≤n} }$ 是n-1個序對的集合，稱為邊集合，E 中的元素 (vi, vj）稱為邊或分支。

image.png

有根數(shù)

樹（Tree）是n（n>=0）個結點的有限集。
1、當n=0 時，稱該樹為空樹；

2、在任意一棵非空樹中：

（1）有且僅有一個特定的稱為根（Root）的結點；

（2）當n>1時，其余結點可分為m（m>0）個互不相交的有限集T1，T2，...，Tn，其中每個集合本身又是一棵樹，并稱為根的子樹（SubTree）
有根數(shù)記做：

image.png

注： $\color{red}{r}$ 是一個特定的稱為根(root)的結點，它只有直接后繼，但沒有直接前驅；

根以外的其他結點劃分為 m (m ≥ 0) 個互不相交的有限集合 $\color{red}{T1, T2, …, Tm}$ ，每個集合又是一棵樹，并且稱之為根的子樹。

每棵子樹的根結點有且僅有一個直接前驅，但可以有0個或多個直接后繼。

image.png

1、基本術語：

$\color{red}{根：}$
樹頂端的節(jié)點稱為根，一棵樹只有一個根
$\color{red}{結點：}$
樹中的獨立單元。包含一個數(shù)據(jù)元素和若干指向其子樹的分支
$\color{red}{父節(jié)點：}$
每個節(jié)點（除了根）都恰好有一條邊向上連接到另外一個節(jié)點，上面的這個節(jié)點就成為下面結點的父節(jié)點
$\color{red}{子節(jié)點：}$
每個節(jié)點都可能有一條或多條邊向下連接其它節(jié)點，下面這些節(jié)點就稱為它的子節(jié)點
$\color{red}{葉結點：}$
沒有子節(jié)點的節(jié)點稱為葉子節(jié)點或簡稱葉節(jié)點（度為0的結點即為葉結點，亦稱為終端結點）。
$\color{red}{子樹：}$ 。
每個節(jié)點都可以作為子樹的根。
$\color{red}{子女：}$
若結點的子樹非空，結點子樹的根即為該結點的子女
$\color{red}{雙親：}$
若結點有子女，該結點是子女雙親
$\color{red}{兄弟：}$
同一結點的子女互稱為兄弟。
$\color{red}{堂兄弟：}$
雙親在同一層次的結點，互為堂兄弟

image.png

$\color{red}{祖先：}$
從根結點到該結點的路徑上的所有結點都是該結點的祖先。
$\color{red}{子孫：}$
某結點的所有下屬結點，都是該結點的子孫。
$\color{red}{分支結點：}$
度不為0的結點即為分支結點，亦稱為非終端結點。
$\color{red}{度：}$
有兩種度“結點的度”與“樹的度”。結點的度指的是一個結點子樹的個數(shù)；樹的度是指樹中結點度的最大值。*

樹的度

$\color{red}{結點的層次：}$
規(guī)定根結點在第一層，其子女結點的層次等于它的層次加一。以下類推。
$\color{red}{深度：}$
結點的深度即為結點的層次；離根最遠結點的層次即為樹的深度（樹中結點的最大層數(shù)）。

image.png

$\color{red}{高度：}$
規(guī)定葉結點的高度為1，其雙親結點的高度等于它的高度加一。
$\color{red}{有序樹：}$
樹中結點的各棵子樹 T0, T1, …是有次序的，即為有序樹。
$\color{red}{無序樹：}$
樹中結點的各棵子樹之間的次序是不重要的，可以互相交換位置。

image.png

$\color{red}{森林：}$
n棵互不相交的樹

樹的存儲方式

$\color{red}{雙親表示法}$ ：以雙親作為索引的關鍵詞的一種存儲方式。

// 雙親表示法
#define MAX_TREE_SIZE 100
typedef int ElemType;
typedef struct PNode{
    ElemType data;//結點數(shù)據(jù)
    int parent;//雙親下標
}PTNode;
typedef struct{
    PTNode nodes[MAX_TREE_SIZE];
    int root;//根位置
    int num;//結點數(shù)目
}PTree;

特點：
根據(jù)parent指針可以找到他的雙親，時間復雜度為O(1),當parent索引為-1時，該結點即為根結點
但是要找到某結點的孩子是什么，則需要遍歷這個樹結構。
改進方法

兄弟之間的關系：

$\color{red}{孩子表示法：}$ 樹中每個結點可能有多個子樹，考慮用多重鏈表來實現(xiàn)
方案一：根據(jù)樹的度聲明足夠空間，存放子樹指針的節(jié)點，缺點：空間浪費

方案二：

$\color{red}{雙親孩子表示法：}$

// 雙親孩子表示法
#define MAX_TREE_SIZE 100
typedef int ElemType;
//孩子節(jié)點
typedef struct CNode{
    int child;//孩子節(jié)點的下標
    struct CNode *next;//指向下一個節(jié)點的指針
}*PChild;
//表頭結構
typedef struct PNode{
    ElemType data;//結點數(shù)據(jù)
    int parent;//雙親下標
    PChild firstChilder;//指向該節(jié)點的第一個孩子結點指針
}PTNode;
//樹結構
typedef struct{
    PTNode nodes[MAX_TREE_SIZE];
    int root;//根位置
    int num;//結點數(shù)目
}PTree;

$\color{red}{孩子兄弟表示法：}$

二叉樹

一棵二叉樹是結點的n（n>=）個結點有限集合，該集合或者為空，或者是由一個根結點加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成。

image.png

\color{red}{二叉樹特點：}

1、每個結點最多有兩顆子樹（沒有子樹或者一顆子樹也可以）。
2、左子樹、右子樹是有順序的，次序不能顛倒。
3、即使某一結點只有一顆子樹，也要區(qū)分左右。

二叉樹基本術語

$\color{red}{斜樹：}$

$\color{red}{滿二叉樹：}$
若一棵二叉樹中的結點,或者為 $\color{red}{葉結點}$ ，或者 $\color{red}{具有兩棵非空子樹}$ ,并且葉結點都集中在二叉樹的 $\color{red}{最下面一層}$ .這樣的二叉樹為滿二叉樹.
特點：
1、葉子結點只能出現(xiàn)在最下一層
2、非葉子節(jié)點的度一定為2
3、在深度相同的二叉樹中，滿二叉樹的節(jié)點個數(shù)一定最多，同時葉子也是最多

$\color{red}{完全二叉樹：}$
若一棵二叉樹中只有最下面兩層的結點的度 $\color{red}{可以小于2}$ ,并且最下面一層的結點(葉結點)都依次排列在該層從左至右的位置上。這樣的二叉樹為完全二叉樹.
（釋義2：對一顆具有n個結點的二叉樹按層序編號，如果編號為i（1<i<n）的節(jié)點與同樣深度的滿二叉樹中編號為i的節(jié)點位置完全相同，則這棵稱為完全二叉樹）
特點：
1、葉子結點只能出現(xiàn)在最下兩層
2、最下層葉子一定集中在左邊連續(xù)位置。
3、倒數(shù)第二層，若有葉子節(jié)點，一定都在右部連續(xù)位置。
4、如果節(jié)點度為1，則該結點只有左孩子。
5、同樣結點的二叉樹，完全二叉樹的深度最小。
注意：滿二叉樹一定是完全二叉樹，但完全二叉樹不一定是滿二叉樹。

image.png

二叉樹的性質

性質1：二叉樹的第i層至多有 $\color{red}{2^{i -1}}$ 個結點（i≥1）
性質2：深度為k的二叉樹至多有 $\color{red}{2^k-1}$ 個結點（k>1）
$\color{green}{因為每一層最少要有1個結點，因此，最少結點數(shù)為 k。最多結點個數(shù)借助性質1：用求等比級數(shù)前k項和的公式}$
$\color{green}{2^0+2^1 +2^2 +...+2^{k-1} =2^k-1 }$

性質3：對任何一棵二叉樹，如果其葉結點有 $\color{red}{ n_{0}}$ 個, 度為 2 的非葉結點有 $\color{red}{ n_{2}}$ 個, 則有
$\color{red}{ n_{0}=n_{2}+1}$
推導：若設度為 1 的結點有 $\color{red}{ n_{1}}$ 個，總結點數(shù)為 $\color{red}{ n}$ ，總邊數(shù)為 $\color{red}{e}$ ，則根據(jù)二叉樹的定義，
$\color{green}{n= n_{0}+n_{1}+n_{2}}$
$\color{green}{e= 2n_{2}+n_{1}}$ = $\color{red}{ n-1}$ （總邊樹總是等于總結點樹-1）
因此，有 $\color{green}{2 n_{2}+n_{1}=n_{0}+n_{1}+n_{2}-1}$ 即： $\color{green}{2n_{2}=n_{0}-1}$
所以： $\color{red}{ n_{0}=n_{2}+1}$

二叉樹存儲結構

$\color{red}{順序存儲結構}$
二叉樹的嚴格定義，在數(shù)組中能直接表現(xiàn)出邏輯結構

使用^表示不存在的結點

斜樹

會比較浪費空間，考慮使用鏈式結構

image.png

$\color{red}{鏈式存儲結構}$

typedef int ElemType;
//孩子節(jié)點
typedef struct BTNode{
    ElemType data;//數(shù)據(jù)
    struct BTNode *LChild,*RChild;//左右孩子結點
}BTNode,*BTree;

$\color{red}{二叉樹的遍歷：}$ 是指從根結點出發(fā)，按照某種 $\color{red}{次序}$ 依次訪問二叉樹中的所有結點

1、前序遍歷（Preorder Traversal）：
若二叉樹為空，則空操作返回，
否則
訪問根結點 (V)；
前序遍歷左子樹 (L)；
前序遍歷右子樹 (R)。

2、中序遍歷：
若二叉樹為空，則空操作返回，
否則
從根結點開始；
中序遍歷根結點的左子樹 (L)；
訪問根結點 (V)；
中序遍歷根結點的右子樹 (R)。

3、后序遍歷：
若二叉樹為空，則空操作返回，
否則
后序遍歷左子樹 (L)；
后序遍歷右子樹 (R)。
訪問根結點 (V)；

4、層序遍歷：
若二叉樹為空，則空操作返回，
否則
從樹的第一層開始，從上而下逐層遍歷，在同一層中，按從左到右順序逐個訪問；

代碼實現(xiàn)：

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
typedef char ElemType;
//孩子節(jié)點
typedef struct BTNode{
    ElemType data;//數(shù)據(jù)
    struct BTNode *LChild,*RChild;//左右孩子結點
}BTNode,*BTree;


//創(chuàng)建一顆二叉樹 使用前序遍歷的方式輸入數(shù)據(jù)
void CreateBitTree(BTree *T){
    char c;
    scanf("%c",&c);
    printf("創(chuàng)建");
    if(' ' == c){
        *T=NULL;

    }else{
    *T=(BTNode*)malloc(sizeof(BTNode));//根節(jié)點
    (*T)->data=c;
    CreateBitTree(&(*T)->LChild);//左節(jié)點
    CreateBitTree(&(*T)->RChild);//右節(jié)點

    }
}
void visit(ElemType data,int level){
    printf("%c位于第%d層",data,level);
}
//前序遍歷二叉樹
void PreOrderTraverse(BTree T,int level){
    if(T){
        visit(T->data,level);
        PreOrderTraverse(T->LChild,level+1);//遍歷左子樹
         PreOrderTraverse(T->RChild,level+1);//遍歷右子樹
    }
}


int main (){
    int level=1;
    BTree T=NULL;
    CreateBitTree(&T);
   // PreOrderTraverse(T,level);
    return 0;
  }

線索二叉樹

查看下圖，可看到會存在^ 浪費空間。可利用^記錄前驅后繼

下圖中使用中序遍歷，沒隔一個可以結點可以記錄前驅后繼

下面黃色表示只有一個空余，紅色有兩個空余

定義如下結構：

LeftTag為0時LeftChild指向該結點的左孩子，為1時指向改結點的前驅。
RigthTag為0時RightChild指向該結點的右孩子，為1時指向改結點的后繼。

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
typedef char ElemType;
typedef enum {Link,Thread} PointTag;//線索存儲枚舉，為0時指向左右孩子，為1時指向前驅后繼
//孩子節(jié)點
typedef struct BTNode{
    ElemType data;//數(shù)據(jù)
    struct BTNode *leftChild,*rightChild;//左右孩子結點
    PointTag leftTag;
    PointTag rightTag;

}BTNode,*BTree;
//全局變量，記錄剛剛訪問的前驅結點
BTree pre;

//創(chuàng)建一顆二叉樹 使用前序遍歷的方式輸入數(shù)據(jù)
void CreateBitTree(BTree *T){
    char c;
    scanf("%c",&c);
    if(' ' == c){
        *T=NULL;

    }else{
    *T=(BTNode*)malloc(sizeof(BTNode));//根節(jié)點
    (*T)->data=c;
    (*T)->leftTag=Link;
    (*T)->rightTag=Link;
    CreateBitTree(&(*T)->leftChild);//左節(jié)點
    CreateBitTree(&(*T)->rightChild);//右節(jié)點

    }
}
//中序遍歷線索化
void InThreading(BTree T){
    if(T){
       InThreading(T->leftChild);//線索化左子樹
       if(!T->leftChild){//無左孩子，修改tag,空指針作為線索指針指向前驅節(jié)點
         T->leftTag=Thread;
         T->leftChild=pre;
       }
/*由于后繼結點還沒有訪問到，將當前訪問的結點作為pre的后繼結點*/
       if(!pre->rightChild){//無右孩子，修改tag
            pre->rightTag=Thread;
            pre->rightChild=T;
       };
       pre=T;//  更新pre
       InThreading(T->rightChild);//線索化右子樹
    }
}
//將樹線索化，加上頭結點，確保pre初始化
void InOrderThreading(BTree *p,BTree T){
    *p=(BTNode*)malloc(sizeof(BTNode)); //  生成頭結點
    (*p)->leftTag=Link;//  頭結點左孩子即是樹的根結點，所以左標記為Link
    (*p)->rightTag=Thread;// 頭結點右孩子指向中序遍歷的最后一個元素，是線索指針
    (*p)->rightChild=*p;//  初始化將p的右孩子回指
    if(!T){
        (*p)->leftChild=T; //如果樹為空，頭結點左孩子也回指
    }else{
        (*p)->leftChild=T;//根結點掛載到頭結點的左子樹
        pre=*p; //  pre先指向p，這樣中序遍歷的第一個結點原本指向空，現(xiàn)在可以指向頭結點
        InThreading(T);//將樹線索化
        pre->rightChild=*p; //  線索化后pre指向中序遍歷的最后一個結點，所以該結點的右孩子原本指空，現(xiàn)在作為線索結點指向頭結點
        pre->rightTag=Thread;
        (*p)->rightChild=pre; // 頭結點的有孩子指向中序遍歷的最后結點pre
    }
}
//中序遍歷二叉樹
void InOrderTraverse(BTree T){
    BTree p;
    p=T->leftChild;//  頭結點的左孩子為樹的根結點
    while(p!=T){//如果p不等于T,循環(huán) 當p==T時，樹為空樹或者遍歷完畢
        while(p->leftTag == Link){//  如果左標記為Link，則一路指向左孩子
            p=p->leftChild;
        }
        printf("%c\n",p->data);// 訪問到中序遍歷的第一個元素
        while(p->rightTag == Thread && p->rightChild != T){//  結點為線索結點且結點右孩子不等于頭結點
            p=p->rightChild; /*遍歷線索路線*/
            printf("%c\n",p->data);
        }
/*p的右標記是孩子標記，轉到右孩子繼續(xù)遍歷 或者 p的右孩子指向頭結點，p指向頭結點，遍歷結束*/
        p=p->rightChild;
    }

}

int main (){
    BTree p,T=NULL;
    CreateBitTree(&T);
    InOrderThreading(&p,T);
    InOrderTraverse(p);
    return 0;
  }

哈夫曼（huffman）樹和哈夫曼編碼

結點的路徑長度：從根結點到該結點的路徑上的連接數(shù)。
數(shù)的路徑長度：樹中每個葉子節(jié)點的路徑長度之和。
結點帶權路徑長度：結點的路徑長度與結點權值的乘積。
樹的帶權路徑長度：WPL(Weight Path Length)是樹中所有葉子結點帶權路徑長度之和。

定長編碼：ASCII編碼
變長編碼：單個編碼的長度不一致，可以根據(jù)整體頻率來調節(jié)。
前綴碼：沒有任何碼字是其他碼字的前綴。

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

樹

樹

1、基本術語：

樹的存儲方式

二叉樹

二叉樹基本術語

二叉樹的性質

二叉樹存儲結構

線索二叉樹

哈夫曼（huffman）樹和哈夫曼編碼

友情鏈接更多精彩內容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

樹

1、基本術語：

樹的存儲方式

二叉樹

二叉樹基本術語

二叉樹的性質

二叉樹存儲結構

線索二叉樹

哈夫曼（huffman）樹和哈夫曼編碼

友情鏈接更多精彩內容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

1、基本術語：