????????

目錄

二叉樹的概念：?

二叉樹的應用與實現：?

?二叉樹實現接口：

通過前序遍歷的數組"ABD##E#H##CF##G##"構建二叉樹?

?二叉樹節點個數?編輯

二叉樹葉子節點個數?

二叉樹第k層節點個數?

?二叉樹查找值為x的節點?編輯

?二叉樹前序遍歷，中序遍歷，后序遍歷

層序遍歷?

判斷二叉樹是否是完全二叉樹?

二叉樹銷毀?

---

二叉樹的概念：?

????????在前面的學習中我們認識了樹的概念，今天的我們將學習數中比較特殊的一類：二叉樹。

二叉樹故名思意，這種樹只存在兩個分支，圖形相貌如下：?

?而二叉樹中又存在著特殊的兩類：滿二叉樹和完全二叉樹。

• 滿二叉樹：一個二叉樹，如果每一個層的結點數都達到最大值，則這個二叉樹就是滿二叉樹。也就是說，如果一個二叉樹的層數為K，且結點總數是 ，則它就是滿二叉樹。
  
  ?
• ?完全二叉樹：完全二叉樹是效率很高的數據結構，完全二叉樹是由滿二叉樹而引出來的。對于深度為K的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編號從1至n的結點一一對應時稱之為完全二叉樹。 要注意的是滿二叉樹是一種特殊的完全二叉樹。

二叉樹的性質
1. 若規定根結點的層數為1，則一棵非空二叉樹的第i層上最多有 2^(i-1)個結點。
2. 若規定根結點的層數為1，則深度為h的二叉樹的最大結點數是 2^h-1。
3. 對任何一棵二叉樹, 如果度為0其葉結點個數為n0, 度為2的分支結點個數為n2,則有n0＝ n2＋1。4. 若規定根結點的層數為1，具有n個結點的滿二叉樹的深度，h=log(n+1) (ps： 是log以2
為底，n+1為對數)
5. 對于具有n個結點的完全二叉樹，如果按照從上至下從左至右的數組順序對所有結點從0開始編號，則對于序號為i的結點有：
1. 若i>0，i位置結點的雙親序號：(i-1)/2；i=0，i為根結點編號，無雙親結點
2. 若2i+1<n，左孩子序號：2i+1，2i+1>=n否則無左孩子
3. 若2i+2<n，右孩子序號：2i+2，2i+2>=n否則無右孩子

二叉樹的應用與實現：?

?二叉樹實現接口：

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>// 類型的定義
typedef char BTDataType;typedef struct BinaryTreeNode
{BTDataType _data;struct BinaryTreeNode* _left;struct BinaryTreeNode* _right;
}BTNode;// 函數的聲明// 通過前序遍歷的數組"ABD##E#H##CF##G##"構建二叉樹
BTNode* BinaryTreeCreate(BTDataType* a, int* pi);// 二叉樹銷毀
void BinaryTreeDestory(BTNode* root);// 二叉樹節點個數
int BinaryTreeSize(BTNode* root);// 二叉樹葉子節點個數
int BinaryTreeLeafSize(BTNode* root);// 二叉樹第k層節點個數
int BinaryTreeLevelKSize(BTNode* root, int k);// 二叉樹查找值為x的節點
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);// 二叉樹前序遍歷 
void BinaryTreePrevOrder(BTNode* root);// 二叉樹中序遍歷
void BinaryTreeInOrder(BTNode* root);// 二叉樹后序遍歷
void BinaryTreePostOrder(BTNode* root);// 層序遍歷
void BinaryTreeLevelOrder(BTNode* root);// 判斷二叉樹是否是完全二叉樹
bool BinaryTreeComplete(BTNode* root);

通過前序遍歷的數組"ABD##E#H##CF##G##"構建二叉樹?

// 通過前序遍歷的數組"ABD##E#H##CF##G##"構建二叉樹
BTNode* BinaryTreeCreate(BTDataType* a, int* pi)
{if (a[(*pi)] == '#'){(*pi)++;return NULL;}BTNode* root = (BTNode*)malloc(sizeof(BTNode));if (root == NULL){perror("malloc fail!");return 1;}root->_data = a[(*pi)++];root->_left = BinaryTreeCreate(a, pi);root->_right = BinaryTreeCreate(a, pi);return root;
}

?二叉樹節點個數

// 二叉樹節點個數
int BinaryTreeSize(BTNode* root)
{return root == NULL ? 0 : BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
}

二叉樹葉子節點個數?

// 二叉樹葉子節點個數
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);
}

二叉樹第k層節點個數?

// 二叉樹第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);
}

?二叉樹查找值為x的節點

// 二叉樹查找值為x的節點
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL)return NULL;if (root->_data == x)return root;BTNode* n1 = BinaryTreeFind(root->_left, x);if (n1){return n1;}BTNode* n2 = BinaryTreeFind(root->_right, x);if (n2){return n2;}return NULL;
}

?二叉樹前序遍歷，中序遍歷，后序遍歷

?

// 二叉樹前序遍歷 
void BinaryTreePrevOrder(BTNode* root)
{if (root == NULL){printf("null ");return;}printf("%c ", root->_data);BinaryTreePrevOrder(root->_left);BinaryTreePrevOrder(root->_right);
}// 二叉樹中序遍歷
void BinaryTreeInOrder(BTNode* root)
{if (root == NULL){printf("null ");return;}BinaryTreeInOrder(root->_left);printf("%c ", root->_data);BinaryTreeInOrder(root->_right);
}// 二叉樹后序遍歷
void BinaryTreePostOrder(BTNode* root)
{if (root == NULL){printf("null ");return;}BinaryTreePostOrder(root->_left);BinaryTreePostOrder(root->_right);printf("%c ", root->_data);
}

層序遍歷?

void BinaryTreeLevelOrder(BTNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);printf("%c ", front->_data);if (front->_left)QueuePush(&q, front->_left);if (front->_right)QueuePush(&q, front->_right);}QueueDestroy(&q);
}

判斷二叉樹是否是完全二叉樹?

// 判斷二叉樹是否是完全二叉樹
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);if (root)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){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}

二叉樹銷毀?

// 二叉樹銷毀
void BinaryTreeDestory(BTNode* root)
{// 使用后序遍歷的方式考慮銷毀if (root == NULL)return;BinaryTreeDestory(root->_left);BinaryTreeDestory(root->_right);free(root);
}

?代碼完整文件：BinaryTree_implement_by_C_2024_5_27 · 陽區欠/數據結構的學習 - 碼云 - 開源中國 (gitee.com)