【數據結構篇】鏈式結構二叉樹

目錄：

一二叉鏈的概念與結構：

1.1 概念：

1.2 結構：

二二叉鏈的實現：

2.1 二叉樹的構建：

2.2 二叉樹的遍歷：

2.2.1?前序遍歷：

2.2.2 中序遍歷：

2.2.3 后序遍歷：

2.3 二叉樹結點個數：

2.4 二叉樹葉子結點個數：

2.5?二叉樹第k層結點個數：

2.6?二叉樹深度/高度：

2.7?二叉樹查找值為x的結點:

2.8 二叉樹的銷毀：

2.9?二叉樹的層序遍歷：

三?判斷是否為完全二叉樹：

四二叉樹性質選擇題：

一二叉鏈的概念與結構：

1.1 概念：

????????用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關系。通常的方法是鏈表中每個結點由三個域組成，數據域和左右指針域，左右指針分別用來給出該結點左孩子和右孩子所在的鏈結點的存儲地址。

1.2 結構：

typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;

回顧二叉樹：

二叉樹分為空樹和非空二叉樹，非空二叉樹由根結點、根結點的左子樹、根結點的右子樹組成的。根結點的左子樹和右子樹分別又是由子樹結點、子樹結點的左子樹、子樹結點的右子樹組成的，因此二叉樹定義是遞歸式的,后序鏈式二叉樹的操作中基本都是按照該概念實現的。

二二叉鏈的實現：

Tree.h

定義二叉鏈結構

將存儲數據類型重命名

所寫的函數的聲明

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int BTdatatype;typedef struct BinaryTreenode
{int data;struct BinaryTreenode* left;struct BinaryTreenode* right;
}BTnode;//前序遍歷
void Preorder(BTnode* root);//中序遍歷
void Inorder(BTnode* root);//后序遍歷
void Postorder(BTnode* root);// ?叉樹結點個數
int BinaryTreeSize(BTnode* root);// ?叉樹葉?結點個數
int BinaryTreeLeafSize(BTnode* root);// ?叉樹第k層結點個數
int BinaryTreeLevelKSize(BTnode* root, int k);//?叉樹的深度/?度
int BinaryTreeDepth(BTnode* root);// ?叉樹查找值為x的結點
BTnode* BinaryTreeFind(BTnode* root, BTdatatype x);// ?叉樹銷毀
void BinaryTreeDestory(BTnode** root);//層序遍歷
//借助數據結構---隊列
void LevelOrder(BTnode* root);

Tree.c

函數的實現方法

2.1 二叉樹的構建：

二叉樹的構建是遞歸實現的

二叉樹的創建方式比較復雜，為了更好的步入到二叉樹內容中，我們先手動創建一棵鏈式二叉樹

方法：

BTNode* BuyBTNode(int val)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL){perror("malloc fail");return NULL;}newnode->val = val;newnode->left = NULL;newnode->right = NULL;return newnode;
}BTNode* CreateTree()
{BTNode* n1 = BuyBTNode(1);BTNode* n2 = BuyBTNode(2);BTNode* n3 = BuyBTNode(3);BTNode* n4 = BuyBTNode(4);BTNode* n5 = BuyBTNode(5);BTNode* n6 = BuyBTNode(6);BTNode* n7 = BuyBTNode(7);n1->left = n2;n1->right = n4;n2->left = n3; n4->left = n5; n4->right = n6; n5->left = n7; return n1;
}

2.2 二叉樹的遍歷：

按照規則，二叉樹的遍歷有：前序/中序/后序的遞歸結構遍歷：
1）前序遍歷(先序遍歷)：訪問根結點的操作發?在遍歷其左右?樹之前
訪問順序為：根結點、左?樹、右?樹
2）中序遍歷：訪問根結點的操作發?在遍歷其左右?樹之中（間）
訪問順序為：左?樹、根結點、右?樹
3）后序遍歷：訪問根結點的操作發?在遍歷其左右?樹之后
訪問順序為：左?樹、右?樹、根結點

2.2.1?前序遍歷：

核心思想就是遞歸：先遞推，再回歸

?? 傳入根節點，依據前序遍歷根左右的規則，先打印根節點，然后再將左結點當做一課新樹的根節點進行相同操作，右子樹同理為遞推，當root==NULL時，直接返回為回歸。

圖解：

代碼：

void Preorder(BTnode* root)
{if (root == NULL){return;}printf("%d ", root->data);Preorder(root->left);Preorder(root->right);
}

2.2.2 中序遍歷：

原理同前序遍歷：（訪問順序為：左?樹、根結點、右?樹）

//中序遍歷
void Inorder(BTnode* root)
{if (root == NULL){return;}Inorder(root->left);printf("%d ", root->data);Inorder(root->right);}

2.2.3 后序遍歷：

原理同前序遍歷：（訪問順序為：左?樹、右?樹、根結點）

//后序遍歷
void Postorder(BTnode* root)
{if (root == NULL){return;}Postorder(root->left);Postorder(root->right);printf("%d ", root->data);}

2.3 二叉樹結點個數：

求二叉樹結點個數，即當下結點+左子樹+右子樹

當結點某一子樹為空時，返回0即可，遞推結束

// ?叉樹結點個數
int BinaryTreeSize(BTnode* root)
{if (root == NULL){return 0;}return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

2.4 二叉樹葉子結點個數：

葉子結點度為0

要求葉子結點，就是求左右子樹葉子結點之和，依次遞推下去

滿足葉子結點條件或是某一子樹為空結束遞推

// ?叉樹葉?結點個數
int BinaryTreeLeafSize(BTnode* root)
{if (root == NULL){return 0;}if (root->left == NULL && root->right == NULL){return 1;}return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

2.5?二叉樹第k層結點個數：

求第k層節點個數，即將根結點設為k,每遞推一層，便將k-1, 當k==1時說明已經遞推到第k層了，此時若不是空結點，返回1，若遇到空節點，返回0，然后在回歸時將它們加起來即可。

// ?叉樹第k層結點個數
int BinaryTreeLevelKSize(BTnode* root, int k)
{if (root == NULL){return 0;}if (k == 1){return 1;}return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

2.6?二叉樹深度/高度：

要求高度，即子樹高度的最大值+1，子樹高度的最大值又是其子樹高度最大值+1，以此類推當遞推到空節點時結束——>返回0（空節點不算高度）

回歸時每次返回左右子樹高度取最大值+1

//?叉樹的深度/?度
int BinaryTreeDepth(BTnode* root)
{if (root == NULL){return 0;}int leftdep = BinaryTreeDepth(root->left);int rightdep = BinaryTreeDepth(root->right);return leftdep > rightdep ? leftdep + 1 : rightdep + 1;}

2.7?二叉樹查找值為x的結點:

分為左右子樹查找，依次遞推即可

結束條件為空：說明在這一路徑上沒有找到

結束條件找到了返回結點指針即可

// ?叉樹查找值為x的結點
BTnode* BinaryTreeFind(BTnode* root, BTdatatype x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTnode* leftfind = BinaryTreeFind(root->left,x);if (leftfind){return leftfind;}BTnode* rightfind = BinaryTreeFind(root->right,x);if (rightfind){return rightfind;}return NULL;
}

2.8 二叉樹的銷毀：

先銷毀左右子樹，最后銷毀根節點

當為空時，不用銷毀直接返回

// ?叉樹銷毀
//將本來指向根節點的root指針改為空，所以傳二級指針（一級指針也可以，只不過在調用完記得把root置為空）
void BinaryTreeDestory(BTnode** root)
{if (*root == NULL){return;}BinaryTreeDestory(&((*root)->left));BinaryTreeDestory(&((*root)->right));free(*root);*root = NULL;}

2.9?二叉樹的層序遍歷：

除了先序遍歷、中序遍歷、后序遍歷外，還可以對二叉樹進行層序遍歷。設二叉樹的根結點所在層數為1，層序遍歷就是從所在二叉樹的根結點出發，首先訪問第一層的樹根結點，然后從左到右訪問第2 層上的結點，接著是第3層的結點，以此類推，自上而下，自左而右逐層訪問樹的結點的過程就是層序遍歷

由于遞歸會沿著一邊路徑一直遞歸下去，所以顯然不能使用遞歸！

實現層序遍歷需要額外借助數據結構：隊列

圖解：

1.創建并初始化隊列，注意將隊列結點存儲的數據類型更改
2.插入的是指向結點的指針，而不是結點的值，否則找不到結點的左右孩子，所以隊列結點存儲的數據類型為struct BTNode*
3.首先將指向根節點的指針入隊列，保存后并打印結點的值
4.根節點出隊列，保證每一次取到的隊列的頭都是新的
5.如果根節點左右孩子不為空就將其入隊列，為空則無必要，不需要打印NULL
6.重復上述操作直到隊列為空

//層序遍歷
//借助數據結構---隊列
void LevelOrder(BTnode* root)
{Queue q;Queueinit(&q);Queuepush(&q, root);while (!QueueEmpty(&q)){//取隊頭，打印BTnode* front = QueueFront(&q);printf("%d ", front->data);QueuePop(&q);//隊頭節點的左右孩子入隊列if (front->left)QueuePush(&q, front->left);if (front->right)Queuepush(&q, front->right);}//隊列為空QueueDestroy(&q);
}

三?判斷是否為完全二叉樹：

使用層序遍歷
1.左右結點不管是否為空，都入隊列
2.第一個循環用來取二叉樹第一個NULL結點前的所有數據：

???????? 如果是完全二叉樹，跳出此循環后剩下的都是NULL結點
???????? 如果是非完全二叉樹，跳出此循環后還有非空結點

3.第二個循環用來判斷此時隊列里是否有非空的指針

??? 如果直到隊列為空跳出循環說明全是空指針，返回true
??? 反之返回false


//判斷二叉樹是否為完全二叉樹
//---隊列
bool BinaryTreeComplete(BTnode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){BTnode* front = QueueFront(&q);QueuePop(&q);if (front == NULL){break;}QueuePush(&q, front->left);QueuePush(&q, front->right);}//隊列不一定為空while (!QueueEmpty(&q)){BTnode* front = QueueFront(&q);QueuePop(&q);if (front != NULL){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}

四二叉樹性質選擇題：

選 B。

性質：度為0結點個數==度為2結點個數+1

選 A。

2n為偶數，由二叉樹的定義可知，樹中必定存在度為0的結點和度為2的結點，設度為0結點有a個，根據度為0的結點(即葉子結點)總比度為2的結點多一個，得度為2的結點有a-1個。

再根據完全二叉樹的定義，度為1的結點有0個或1個

設度為1的結點有0個，a+0+a-1=2n，得2a=2n-1，由于結點個數必須為整數，假設不成立；

設度為1的結點有1個，a+1+a-1=2n，得a=n，即葉子結點個數為n。

選B。

由2^9-1<531<2^10-1

說明第九層填滿，第十層沒有填滿

選B。

由二叉樹的定義可知，樹中必定存在度為0的結點和度為2的結點，設度為0結點有a個，根據度為0的結點(即葉子結點)總比度為2的結點多一個，得度為2的結點有a-1個。
再根據完全二叉樹的定義，度為1的結點有0個或1個
假設度1結點為0個，a+0+a-1=767，得2a=768，即葉子結點個數為384
當度為1的結點為1個時，a+1+a-1=767，不為整數，舍去。