一细卧、樹的基本概念
1.結(jié)點(diǎn)的度: 結(jié)點(diǎn)子結(jié)點(diǎn)的個(gè)數(shù).
A結(jié)點(diǎn)姨伤，也就是根節(jié)點(diǎn)的度為3分別是BCD
K上真，L節(jié)點(diǎn)的度為0
2.樹的度: 樹中最大的節(jié)點(diǎn)的度為樹的度.
栗子樹的度為3
3.結(jié)點(diǎn)的高度和深度：
高度是自下向上累計(jì)
深度是自上向下累計(jì)
A節(jié)點(diǎn)的高度為4劳秋，深度為1
K節(jié)點(diǎn)的高度為1悦穿，深度為4
4.樹的高度和深度：
☆樹中結(jié)點(diǎn)最大的層數(shù)栗子樹的高度和深度為4攻礼，同時(shí)層數(shù)也為4
5.路徑：
自上而下的有向的，A和E的路徑為A->B->E,E和F這樣的兄弟結(jié)點(diǎn)是不存在路徑的栗柒。
6.路徑長度：
路徑上所經(jīng)歷邊的個(gè)數(shù)礁扮，A->B->E的路徑長度為2
二、樹的性質(zhì).
1.樹中的結(jié)點(diǎn)數(shù) = 所有結(jié)點(diǎn)度數(shù) + 1
解釋：結(jié)點(diǎn)度的含義指的就是瞬沦，結(jié)點(diǎn)有幾個(gè)孩子太伊，那么，每個(gè)節(jié)點(diǎn)的度都可以和相應(yīng)的結(jié)點(diǎn)對(duì)應(yīng)逛钻，因?yàn)楦Y(jié)點(diǎn)是最頂層僚焦，然沒有父結(jié)點(diǎn)，所以曙痘，所有結(jié)點(diǎn)的度 + 根節(jié)點(diǎn) = 樹中的結(jié)點(diǎn)數(shù)
2.度為M的樹的芳悲，任意結(jié)點(diǎn)的度數(shù)小于等于M立肘，結(jié)點(diǎn)最多M個(gè)孩子
3.度為M的樹，至少有一個(gè)結(jié)點(diǎn)的度為M
4.度為M的樹名扛，一定是非空樹谅年，至少有M+1個(gè)節(jié)點(diǎn)
5.N叉樹，任意結(jié)點(diǎn)的度小于等于N
6.N叉樹肮韧，允許所有結(jié)點(diǎn)的度小于N
7.N叉樹融蹂，可以是空樹
8.度為M的樹，第i層最多有M^(i-1)個(gè)節(jié)點(diǎn)惹苗，其中i>=1
解析:最多結(jié)點(diǎn)樹殿较，我們可以假設(shè)每個(gè)節(jié)點(diǎn)的度都為M，i>=1桩蓉，說明了層數(shù)從第一層開始計(jì)數(shù)淋纲，一共層，第一層M0個(gè)院究，第二層M1洽瞬，第三層就是M2...第i層就是M(i-1)次方個(gè)。
9.高度為H的M叉樹最多有1-M^H/1-M
解析:高度為H說明了一共有H層业汰，M叉樹最多伙窃，可以假設(shè)，是滿M叉二叉樹样漆，那么第一層有M^0 第二層有M1...第H層有M(h-1),因?yàn)槭菑牧汩_始計(jì)數(shù)的0~H-1剛好H項(xiàng)为障，等比數(shù)列求和
1*(1-M^H)/(1-M) = 1-M^H/1-M
10.具有N個(gè)結(jié)點(diǎn)的M叉樹最小高度為logM^(1-N(1-M))
解析：最小高度就是當(dāng)M叉樹為滿M叉樹的時(shí)候，具有N個(gè)結(jié)點(diǎn)
1-M^H/1-M = N => H = logM^(1-N(1-M))
三放祟、二叉樹
基本概念
1.由一個(gè)根節(jié)點(diǎn)和兩個(gè)互不相交的左子樹和右子樹組成鳍怨，同是左右子樹也是一個(gè)二叉樹，利用遞歸進(jìn)行定義的數(shù)據(jù)結(jié)構(gòu).
2.二叉樹有五種狀態(tài)：空二叉樹跪妥、只有左子樹鞋喇，只有右子樹，只有根節(jié)點(diǎn)眉撵，左右子樹都有侦香。邏輯結(jié)構(gòu)
幾種特殊的二叉樹：
1.滿二叉樹
①高度為h的滿二叉樹，有2^h -1個(gè)結(jié)點(diǎn).
②只有最后一層含有葉子節(jié)點(diǎn)纽疟，不存在度為1的節(jié)點(diǎn)
③按照層序從1開始編號(hào)罐韩，i節(jié)點(diǎn)的左孩子為2i,i節(jié)點(diǎn)的右孩子為2i+1,父節(jié)點(diǎn)為i/2
④i<=n/2為分支節(jié)點(diǎn)，i>n/2為葉子節(jié)點(diǎn).
2.完全二叉樹
①當(dāng)且僅當(dāng)每個(gè)結(jié)點(diǎn)都與高度為h的滿二叉樹中編號(hào)為1~n的節(jié)點(diǎn)一一對(duì)應(yīng)時(shí)污朽，稱為完全二叉樹
②只有最后兩層可能出現(xiàn)葉子節(jié)點(diǎn)
③最多只有一個(gè)度為1的節(jié)點(diǎn)
④結(jié)點(diǎn)i的左孩子為2i右孩子為2i+1伴逸，父親節(jié)點(diǎn)i/2
⑤i<=n/2為分支節(jié)點(diǎn)，i>n/2為葉子節(jié)點(diǎn).
3.二叉排序樹
①左子樹所有的節(jié)點(diǎn)關(guān)鍵字小于根節(jié)點(diǎn)小于右子樹關(guān)鍵字.
②左右子樹又是一顆二叉排序樹
4.平衡二叉樹
①樹上任意結(jié)點(diǎn)的左子樹和右子樹深度只差不超過1
- 二叉樹常考性質(zhì)
1.度為0,1,2的結(jié)點(diǎn)個(gè)數(shù)分別為N0,N1,N2則N0 = N2 + 1
解析：設(shè)2插樹總結(jié)點(diǎn)樹為n=>
①n = N0 + N1 + N2
樹的結(jié)點(diǎn)樹 = 總度數(shù) + 1 =>
②n = N1 + 2N2 + 1
①②聯(lián)立 => N0 = N2 + 1即度數(shù)為0的結(jié)點(diǎn)數(shù)量 = 度數(shù)為2的結(jié)點(diǎn) + 1
2.二叉樹第i層最多2^(i-1)i>=1
3.高度為h的二叉樹最多有 2^h - 1個(gè)結(jié)點(diǎn).
- 存儲(chǔ)結(jié)構(gòu)
順序存儲(chǔ)
1.順序存儲(chǔ)只適合存儲(chǔ)完全二叉樹
解析：二叉樹是完全二叉樹的時(shí)候可以通過错蝴，2i洲愤，2i+1, i/2
來找到結(jié)點(diǎn)之間的關(guān)系，當(dāng)樹為普通二叉樹的時(shí)候顷锰，我們可以將普通二叉樹轉(zhuǎn)換成完全二叉樹柬赐，這樣的話，會(huì)有一部分空間導(dǎo)致浪費(fèi)官紫。
浪費(fèi)的空間
所以二叉樹很少使用順序存儲(chǔ)肛宋，一般樹為完全二叉樹的時(shí)候，可以使用.
2.鏈?zhǔn)酱鎯?chǔ)代碼
#include<stdio.h>
#include<stdlib.h>
typedef struct TreeNode {
char data;
struct TreeNode* leftChild;
struct TreeNode* rightChild;
}TreeNode,Tree;
Tree* inintTree(char root);
TreeNode* getTreeNode(char data);
void preOrder(Tree* tree);
void inOrder(Tree* tree);
void postOrder(Tree* tree);
void visit(TreeNode* treeNode);
int main() {
// 構(gòu)建樹.
TreeNode* tree = inintTree('a');
TreeNode* rootA = tree;
TreeNode* nodeB = getTreeNode('b');
TreeNode* nodeC = getTreeNode('c');
TreeNode* nodeD = getTreeNode('d');
TreeNode* nodeE = getTreeNode('e');
rootA->leftChild = nodeB;
rootA->rightChild = nodeC;
nodeB->leftChild = nodeD;
nodeB->rightChild = nodeE;
//前序遍歷
preOrder(tree);
printf("\n");
// 中序遍歷
inOrder(tree);
printf("\n");
// 層序遍歷
postOrder(tree);
printf("\n");
}
Tree* inintTree(char root) {
return getTreeNode(root);
}
TreeNode* getTreeNode(char data) {
TreeNode* treeNode = (TreeNode*)malloc(sizeof(TreeNode));
treeNode->data = data;
treeNode->leftChild = NULL;
treeNode->rightChild = NULL;
return treeNode;
}
void preOrder(Tree* tree){
if(tree!=NULL) {
visit(tree);
preOrder(tree->leftChild);
preOrder(tree->rightChild);
}
}
void inOrder(Tree* tree){
if(tree!=NULL) {
inOrder(tree->leftChild);
visit(tree);
inOrder(tree->rightChild);
}
}
void postOrder(Tree* tree){
if(tree!=NULL) {
postOrder(tree->leftChild);
postOrder(tree->rightChild);
visit(tree);
}
}
void visit(TreeNode* treeNode) {
printf("%c ",treeNode->data);
}
- 二叉樹的遍歷
①前序遍歷
②中序遍歷
③后序遍歷
④層序遍歷
思想：初始化一個(gè)輔助隊(duì)列束世，根節(jié)點(diǎn)入隊(duì)酝陈，若隊(duì)列非空，隊(duì)頭節(jié)點(diǎn)出隊(duì)毁涉，出隊(duì)節(jié)點(diǎn)存在左右孩子則插入隊(duì)尾沉帮，重復(fù)上述，直到隊(duì)列為空.
- 根據(jù)遍歷順序推出二叉樹的結(jié)構(gòu)
1.前中 √
2.后中√
3.層中√
必須要有中序遍歷贫堰，否則無法推導(dǎo)二叉樹結(jié)構(gòu).
四穆壕、線索二叉樹
1.中序線索二叉樹
#include<stdio.h>
typedef struct TreeNode {
char data;
struct TreeNode leftChild,rightChild;
int leftFlag,rightFlag;
}TreeNode,Tree;
TreeNode* getTreeNode(char data);
void buildThreadBinaryTree(Tree* tree);
void dealTree(Tree* tree);
TreeNode* pre = NULL;
int main() {
TreeNode* treeNodeA = getTreeNode('a');
TreeNode* treeNodeB = getTreeNode('b');
TreeNode* treeNodeC = getTreeNode('c');
TreeNode* treeNodeD = getTreeNode('d');
TreeNode* treeNodeE = getTreeNode('e');
treeNodeA->leftChild = treeNodeB;
treeNodeA->rightChild = treeNodeC;
treeNodeB->leftChild = treeNodeD;
treeNodeE->rightChild = treeNodeE;
//這里以中序線索二叉樹為例.
buildThreadBinaryTree(treeNodeA);
//處理最后一個(gè)結(jié)點(diǎn).
if(pre->rightChild == NULL) {
pre->rightFlag = 1;
}
}
TreeNode* getTreeNode(char data) {
TreeNode* treeNode = (TreeNode*)malloc(sizeof(TreeNode));
treeNode->data = data;
treeNode->leftChild = NULL;
treeNode->leftFlag = 0;
treeNode->rightChild = NULL;
treeNode->rightFlag = 0;
return treeNode;
}
void buildThreadBinaryTree(Tree* tree) {
if(tree != NULL) {
buildThreadBinaryTree(tree->leftChild);
dealTree(tree);
buildThreadBinaryTree(tree->rightChild);
}
}
void dealTree(Tree* tree) {
//找前驅(qū)
if(tree->leftChild == NULL) {
tree->leftChild = pre;
tree->leftFlag = 1;
}
//找后繼
if(pre != NULL && pre->rightChild == NULL) {
pre->rightChild = tree;
pre->rightFlag = 1;
}
pre = tree;
}
2.前序遍歷
void buildThreadBinaryTree(Tree* tree) {
if(tree != NULL) {
dealTree(tree);
//為了防止轉(zhuǎn)圈的問題.
if(tree->leftFlag == 0) {
buildThreadBinaryTree(tree->leftChild);
}
buildThreadBinaryTree(tree->rightChild);
}
}
3.后序遍歷
void buildThreadBinaryTree(Tree* tree) {
if(tree != NULL) {
buildThreadBinaryTree(tree->leftChild);
buildThreadBinaryTree(tree->rightChild);
dealTree(tree);
}
}
4.找前驅(qū)和后繼
待更新....
