資料結構基礎—樹和二叉樹
一、樹、二叉樹型別定義
1.樹的定義
a.定義
樹是一種非線性結構，是具有相同特征的資料元素的集合(同質/類)
| 資料物件D：D是具有相同特征的資料元素的集合(同質/類) |
|---|
| 資料關系R： 若D為空樹，則就角空樹 否則 1. n = 1(一個元素)，有且僅有一個根節點 2. n > 1，其余節點可分為m顆不相交的有限子集(小樹)(遞回定義)，每一個子 集也叫一顆子樹符合... |
| 基本操作：查找類，插入類(初始化,節點插入子樹...)，洗掉類(銷毀.洗掉結點...) |
根是樹的第一層，子樹依次類推++
深度：最大的層數 = max（子樹深度）+1(遞回啦)
b.分類
- 有向樹：有確定的根，自頂向下（一般）
- 有序樹：子樹之間存在有次序關系
- 無序樹：子樹之間不存在次序關系
c.對比樹型結構和線性
- 線性：第一元素無前驅，最后一個元素無后繼；其他元素一個前驅，一個后繼
- 樹型：根結點無前驅，多個葉子結點無后繼；其他元素，一個前驅，多個后繼
d.屬性
結點：資料元素+若干指向子樹的分支(結點關系)
結點的度：分支個數(子樹棵樹..)
樹的度：樹中所有結點的度的最大值
葉子結點：度為零的結點
分支結點：度>0的結點
路徑：從根到某個結點的路線
同一層的都是堂兄弟，若父結點相同：兄弟結點
祖先結點：> 父結點的結點的統稱
e.森林
m > 0棵不相交的樹的集合（可以看成去了頭結點...）
2.二叉樹型別定義：
a.定義
空樹 / 一個根結點+兩顆子樹(還是二叉樹)
是有序樹，分左右子樹
b.二叉樹的5中形態
b.特殊的二叉樹
-
滿二叉樹，深度為k的樹有2的k-1次方個結點
-
完全二叉樹，滿二叉樹去掉右邊的葉子不能跳的去，樹中所含n個結點和滿二叉樹中編號1-n的結點一一一對應
c.完全二叉樹性質
1.二叉樹第i層最多2的n-1次方的結點(i >= 1)
2.若深度為i，則最多有多少個結點(等比求和)，2的i次方 - 1
3.若深度為i,則，第i層最少1個結點，整個樹最少有i個結點
4.結點和邊(分支)的關系，n個結點,n-1個分支(n = e + 1)
5.葉子結點和度為2的關系：n0 = n2 +1(n=n0 + n1 + n2 = e(n1+n2) + 1)
6.完全二叉樹有n個結點,則，深度為log2n取整數(向下取)+1
7.結點編號：結點為i，若i = 1是根結點,i/2是雙親，i >1且 2i <= n,左子2i；i >1且 2i+1 <= n,右2i+1
二、二叉樹的存盤結構
1.順序
#define MaxSize 100
typefef TElemType SqbItREE[maxSzie];//零號單元存盤根節點
SqBiTree bt;
只適用于完全二叉樹好
2.鏈式
a.二叉鏈表
typedef struct BiTNode{
TElemType data;//資料
struct BiTNode *lchild,*rchild;//左右指標
}BiTNode,*BiTree;
n個結點的二叉鏈表中，有 n+1個空指標域(2n個指標域，除了根結點，每個結點對應一個，n-1個，2n- (n-1))
b.三叉鏈表
浪費一些空間
typedef struct TrTNode{
TElemType data;//資料
struct TrTNode *lchild,*rchild;//左右指標
struct TrTNode *parent;//雙親指標
}TrTNode,*TrTree;
typedef struct BPTNode{//結點結構
TElemType data;//資料
int *parent;//指向雙親的指標
char *LRTag;//左右孩子的標志
}BPTNode;
typedef structBPTree{
BPTNode nodes[MaxSize];
int mum;結點數目
int root;跟結點的位置
}BPTree;
d.靜態鏈表
三、二叉樹的遍歷
1.演算法遞回的描述
滿足條件：
- 每一次呼叫更接近解
- 必須有一個終止處理或計算
遞回一定可以改成堆疊
分治法，后置遞回法，回溯法(與分治本本質相同)
尾遞回(提倡簡單，設計，效率高)
2.二叉樹的遍歷
a.遍歷路徑
對于二叉樹，有三種遍歷路徑
先上后下的層次遍歷，先左后右(正序)，先右后左(逆序)
b.先左后右的遍歷（正序）
分為三種：根左右(先)，左根右(中)，左右根(后)
先序描述
//遞回
void Preorder(BiTree T,void(*visit)(TElemType& e)){//先序遍歷
//對該結點的操作
if(T){
visit(T->data);//訪問
Preorder(T->lchild,vist);//遍歷左子樹
// visit(T->data);中序
Preorder(T->lchild,vist);//遍歷右子樹
// visit(T->data);后序
}
}
其實，三種訪問演算法的實質是一樣的，是指訪問時機不同（沿著樹畫出線畫出空結點）
- 先：第一次經過就訪問
- 中：第二次經過就訪問
- 后：第三次經過就訪問
c.第一個結點和最后一個結點
第一個結點：
- 先序：根結點
- 中序：從根結點出發，沿左鏈走，第一個沒有左孩子的結點
- 后序：在左鏈，沿著左鏈一直走，找到沒有左孩子的結點；若該結點沒有右孩子該結點就是最后一個結點；如果有右孩子則重復上述操作
最后一個結點：
- 先序：在右鏈，沿著右鏈一直走，找到沒有右孩子的結點；若該結點沒有左孩子該結點就是最后一個結點；如果有左孩子則重復上述操作
- 中序：從根結點出發，沿右鏈走，第一個沒有右孩子的結點
- 后序：根結點
d.非遞回遍歷
代碼放在下一篇啦(要不有點多)
總是先將樹的左子入堆疊
用堆疊或者模擬堆疊均可
第一種
先獲取第一個左鏈結點，并將其所有的根結點入堆疊(左結點全部入堆疊，除了獲取的結點)
訪問該結點，查詢是否有右結點，如果有，重復上述；
如果沒有，則判斷堆疊(該結點的根結點是堆疊頂)是否空，不空：則退堆疊，獲取該堆疊頂為新的"第一個結點"，重復上述；空(遍歷結束)
第二種
若堆疊或樹不空時
- 樹不空：樹進堆疊，沿左鏈下移
- 堆疊不空：退一個堆疊到T，并獲取T，T沿右鏈下移
四、二叉樹的一些基本操作
和遍歷一樣放在下一篇了
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/536009.html
標籤：其他
上一篇：二維碼的秘密（生成原理）