【數據結構】二叉樹的鏈式存儲結構
二叉樹的存儲結構
typedef int BTDataType;
// 二叉樹的結構
typedef struct BinaryTreeNode {
BTDataType data; // 樹的值
struct BinaryTreeNode *left; // 左孩子
struct BinaryTreeNode *right;// 右孩子
} BinaryTreeNode;
二叉樹的深度優(yōu)先遍歷
前序遍歷
前序遍歷，又叫先根遍歷。
遍歷順序：根 -> 左子樹 -> 右子樹
代碼：
// 前序遍歷
void BinaryTreePrevOrder(BinaryTreeNode *root) {
// 前序遍歷 根、左子樹、右子樹
// 如果root為空，遞歸結束
if (root == NULL) {
printf("NULL ");
return;
}
printf("%d ", root->data);
BinaryTreePrevOrder(root->left);
BinaryTreePrevOrder(root->right);
}
中序遍歷
中序遍歷，又叫中根遍歷。
遍歷順序：左子樹 -> 根 -> 右子樹
代碼：文章來源：http://www.zghlxwxcb.cn/news/detail-706871.html
// 中序遍歷
void BinaryTreeInOrder(BinaryTreeNode *root) {
// 中序遍歷 - 左子樹、根、右子樹
if (root == NULL) {
printf("NULL ");
return;
}
BinaryTreeInOrder(root->left);
printf("%d ", root->data);
BinaryTreeInOrder(root->right);
}
后序遍歷
后序遍歷，又叫后根遍歷。
遍歷順序：左子樹 -> 右子樹 -> 根
代碼：
// 后序遍歷
void BinaryPostOrder(BinaryTreeNode *root) {
// 后序遍歷 - 左子樹、右子樹、根
if (root == NULL) {
printf("NULL ");
return;
}
BinaryPostOrder(root->left);
BinaryPostOrder(root->right);
printf("%d ", root->data);
}
二叉樹的廣度優(yōu)先遍歷
層序遍歷
除了先序遍歷、中序遍歷、后序遍歷外，還可以對二叉樹進行層序遍歷。設二叉樹的根節(jié)點所在層數為1，層序遍歷就是從所在二叉樹的根節(jié)點出發(fā)，首先訪問第一層的樹根節(jié)點，然后從左到右訪問第2層 上的節(jié)點，接著是第三層的節(jié)點，以此類推，自上而下，自左至右逐層訪問樹的結點的過程就是層序遍歷。
思路（借助一個隊列）：
- 先把根入隊列，然后開始從隊頭出數據。
- 出隊頭的數據，把它的左孩子和右孩子依次從隊尾入隊列（NULL不入隊列）。
- 重復進行步驟2，直到隊列為空為止。
特點：借助隊列先進先出的性質，上一層數據出隊列的時候帶入下一層數據。
// 層序遍歷 - 利用隊列
void BinaryTreeLevelOrder(BinaryTreeNode *root) {
// 創(chuàng)建一個隊列，隊列中入數據，取隊頭，然后帶左右子樹，出一個數，帶一個樹的所有子樹
Queue q;
QueueInit(&q);
if (root) {
// root不為NULL，就入隊列
QueuePush(&q, root);
}
while (!QueueEmpty(&q)) {
// 取隊頭，打印
BinaryTreeNode *front = QueueFront(&q);
printf("%d ", front->data);
// 取完POP
QueuePop(&q);
// 取隊頭，帶下一層,
if (front->left) {
QueuePush(&q, front->left);
}
if (front->right) {
QueuePush(&q, front->right);
}
}
printf("\n");
QueueDestroy(&q);
}
二叉樹的節(jié)點個數
求解樹的節(jié)點總數時，可以將問題拆解成子問題：
- 若為空，則結點個數為0。
- 若不為空，則結點個數 = 左子樹節(jié)點個數 + 右子樹節(jié)點個數 + 1（自己）。
代碼：
// 求二叉樹節(jié)點個數
int BinaryTreeSize(BinaryTreeNode *root) {
if (root == NULL) {
return 0;
}
return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}
二叉樹的葉子節(jié)點個數
子問題拆解：
- 若為空，則葉子結點個數為0。
- 若結點的左指針和右指針均為空，則葉子結點個數為1。
- 除上述兩種情況外，說明該樹存在子樹，其葉子結點個數 = 左子樹的葉子結點個數 + 右子樹的葉子結點個數。
代碼：
// 求二叉樹的葉子節(jié)點個數
int BinaryTreeLeafSize(BinaryTreeNode *root) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return 1;
}
return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
第K層節(jié)點的個數
思路：
相對于根結點的第k層結點的個數 = 相對于以其左孩子為根的第k-1層結點的個數 + 相對于以其右孩子為根的第k-1層結點的個數。
代碼：
// 求第k層的節(jié)點個數 k>=1
int BinaryTreeLevelSize(BinaryTreeNode *root, int k) {
if (root == NULL) {
return 0;
}
if (k == 1) {
return 1;
}
return BinaryTreeLevelSize(root->left, k - 1) + BinaryTreeLevelSize(root->right, k - 1);
}
值為x的節(jié)點
子問題：
- 先判斷根結點是否是目標結點。
- 再去左子樹中尋找。
- 最后去右子樹中尋找。
代碼：
// 二叉樹查找值為x的節(jié)點
BinaryTreeNode *BinaryTreeFind(BinaryTreeNode *root, BTDataType x) {
if (root == NULL) {
return NULL;
}
if (root->data == x) {
return root;
}
// 左子樹遞歸的節(jié)點保存到leftTree中,如果leftTree不為NULL，則return leftTree
BinaryTreeNode *leftTree = BinaryTreeFind(root->left, x);
if (leftTree) {
return leftTree;
}
// 右子樹遞歸的節(jié)點保存到rightTree中,如果rightTree不為NULL，則return rightTree
BinaryTreeNode *rightTree = BinaryTreeFind(root->right, x);
if (rightTree) {
return rightTree;
}
// 找不到，返回NULL
return NULL;
}
樹的高度
子問題：
- 若為空，則深度為0。
- 若不為空，則樹的最大深度 = 左右子樹中深度較大的值 + 1。
代碼：
// 求二叉樹的高度
int BinaryTreeHeight(BinaryTreeNode *root) {
// 求左子樹的高度，右子樹的高度
// 取最大的
if (root == NULL) {
return 0;
}
int leftHeight = BinaryTreeHeight(root->left);
int rightHeight = BinaryTreeHeight(root->right);
//如果左右子樹兩邊相等就取左邊的高度,所以大于等于
return leftHeight >= rightHeight ? leftHeight + 1 : rightHeight + 1;
}
判斷二叉樹是否是完全二叉樹
判斷二叉樹是否是完全二叉樹的方法與二叉樹的層序遍歷類似，但又有一些不同。
思路（借助一個隊列）：
- 先把根入隊列，然后開始從隊頭出數據。
- 出隊頭的數據，把它的左孩子和右孩子依次從隊尾入隊列（NULL也入隊列）。
- 重復進行步驟2，直到讀取到的隊頭數據為NULL時停止入隊列。
- 檢查隊列中剩余數據，若全為NULL，則是完全二叉樹；若其中有一個非空的數據，則不是完全二叉樹。
代碼：
// 判斷二叉樹是否是完全二叉樹
bool BinaryTreeComplete(BinaryTreeNode *root) {
// 層序走，走到第一個為空的時候，就跳出去，如果是滿二叉樹，后面的節(jié)點都應該為空
Queue q;
QueueInit(&q);
if (root) {
QueuePush(&q, root);
}
while (!QueueEmpty(&q)) {
BinaryTreeNode *front = QueueFront(&q);
QueuePop(&q);
if (front == NULL) {
break;
} else {
QueuePush(&q, front->left);
QueuePush(&q, front->right);
}
}
// 出到空以后，如果后面全是空，則是完全二叉樹
while (!QueueEmpty(&q)) {
BinaryTreeNode *front = QueueFront(&q);
QueuePop(&q);
if (front != NULL) {
QueueDestroy(&q);
return false;
}
}
QueueDestroy(&q);
return true;
}
判斷二叉樹是否是單值二叉樹
單值二叉樹，所有節(jié)點的值都相同的二叉樹即為單值二叉樹，判斷某一棵二叉樹是否是單值二叉樹的一般步驟如下：
- 判斷根的左孩子的值與根結點是否相同。
- 判斷根的右孩子的值與根結點是否相同。
- 判斷以根的左孩子為根的二叉樹是否是單值二叉樹。
- 判斷以根的右孩子為根的二叉樹是否是單值二叉樹。
若滿足以上情況，則是單值二叉樹。
注：空樹也是單值二叉樹。
代碼：
//求單值二叉樹
bool isUnivalTree(BinaryTreeNode *root) {
if (root == nullptr) {
return true;
}
if (root->left && root->data != root->left->data) {
return false;
}
if (root->right && root->data != root->right->data) {
return false;
}
return isUnivalTree(root->left) && isUnivalTree(root->right);
}
判斷二叉樹是否是對稱二叉樹
對稱二叉樹，這里所說的對稱是指鏡像對稱：
要判斷某二叉樹是否是對稱二叉樹，則判斷其根結點的左子樹和右子樹是否是鏡像對稱即可。因為是鏡像對稱，所以左子樹的遍歷方式和右子樹的遍歷方式是不同的，準確來說，左子樹和右子樹的遍歷是反方向進行的。
代碼：
//求對稱二叉樹
bool _isSymmetric(BinaryTreeNode *left, BinaryTreeNode *right) {
// 兩個都為NULL，對稱
if (left == NULL && right == NULL)
return true;
// 兩個其中一個為NULL，一個不為NULL，不對稱
if (left == NULL || right == NULL)
return false;
// left的左孩子的值和right的值不相等，不對稱
if (left->data != right->data)
return false;
// 左子樹的左孩子，和右子樹的右孩子對比，然后左子樹的右孩子和右子樹的左孩子在對比
return _isSymmetric(left->left, right->right) && _isSymmetric(left->right, right->left);
}
bool isSymmetric(BinaryTreeNode *root) {
if (root == nullptr) {
return true;
}
return _isSymmetric(root->left, root->right);
}
翻轉二叉樹
思路：
- 翻轉左子樹。
- 翻轉右子樹。
- 交換左右子樹的位置。
代碼：
BinaryTreeNode *invertTree(BinaryTreeNode *root) {
if (root == nullptr) {
return nullptr;
}
BinaryTreeNode *leftTree = invertTree(root->left);
BinaryTreeNode *rightTree = invertTree(root->right);
root->left = rightTree;
root->right = leftTree;
return root;
}
二叉樹的構建和銷毀
// 申請樹節(jié)點
BinaryTreeNode *BuyBinaryTreeNode(BTDataType x) {
BinaryTreeNode *newnode = (BinaryTreeNode *) malloc(sizeof(BinaryTreeNode));
if (newnode == NULL) {
perror("malloc fail");
exit(-1);
}
newnode->data = x;
newnode->left = newnode->right = NULL;
return newnode;
}
// 通過前序遍歷的數組"ABD##E#H##CF##G##"構建二叉樹
BinaryTreeNode *BinaryTreeCreate(BTDataType *a, int *pi) {
if (a[*pi] == '#') {
(*pi)++;
return NULL;
}
BinaryTreeNode *root = (BinaryTreeNode *) malloc(sizeof(BinaryTreeNode));
if (root == NULL) {
perror("malloc fail");
exit(-1);
}
root->data = a[(*pi)++];
root->left = BinaryTreeCreate(a, pi);
root->right = BinaryTreeCreate(a, pi);
return root;
}
銷毀：文章來源地址http://www.zghlxwxcb.cn/news/detail-706871.html
// 二叉樹銷毀
void BinaryTreeDestory(BinaryTreeNode **root) {
if (*root == NULL) {
return;
}
// 后序遍歷銷毀，根要最后釋放
BinaryTreeDestory(&(*root)->left);
BinaryTreeDestory(&(*root)->right);
free(*root);
*root = NULL;
}
到了這里，關于【數據結構】二叉樹的鏈式存儲結構的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
