數據結構--二叉樹

?1.二叉樹鏈式結構的實現

1.1 前置說明

1.2?二叉樹的遍歷

1.2.1 前序、中序以及后序遍歷

1.2.2?層序遍歷及判斷是否為完全二叉樹

1.3?節點個數，葉子節點個數，第k層節點個數以及高度等

1.4 二叉樹的創建和銷毀

?1.二叉樹鏈式結構的實現

1.1 前置說明

? ? ? ? 這時直接創建的二叉樹，方便于各個接口函數的測試，當然你也可以選擇1.4的方法直接創建。
typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}TreeNode;TreeNode* BuyTreeNode(int x)
{TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));assert(node);node->data = x;node->left = NULL;node->right = NULL;return node;
}
TreeNode* CreateTree()
{TreeNode* node1 = BuyTreeNode(1);TreeNode* node2 = BuyTreeNode(2);TreeNode* node3 = BuyTreeNode(3);TreeNode* node4 = BuyTreeNode(4);TreeNode* node5 = BuyTreeNode(5);TreeNode* node6 = BuyTreeNode(6);TreeNode* node7 = BuyTreeNode(7);node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;node5->right = node7;return node1;
}
再看二叉樹基本操作前，再回顧下二叉樹的概念，二叉樹是：
????????1. 空樹
????????2. 非空：根節點，根節點的左子樹、根節點的右子樹組成的。

????????從概念中可以看出，二叉樹定義是遞歸式的，因此后序基本操作中基本都是按照該概念實現的。

1.2?二叉樹的遍歷

1.2.1 前序、中序以及后序遍歷

?????????學習二叉樹結構，最簡單的方式就是遍歷。所謂二叉樹遍歷是按照某種特定的規則，依次對二叉樹中的節點進行相應的操作，并且每個節點只操作一次。訪問結點所做的操作依賴于具體的應用問題。遍歷是二叉樹上最重要的運算之一，也是二叉樹上進行其它運算的基礎。

按照規則，二叉樹的遍歷有：前序/中序/后序的遞歸結構遍歷：
????????1. 前序遍歷(Preorder Traversal 亦稱先序遍歷)——訪問根結點的操作發生在遍歷其左右子樹之前。
????????2. 中序遍歷(Inorder Traversal)——訪問根結點的操作發生在遍歷其左右子樹之中間。
????????3. 后序遍歷(Postorder Traversal)——訪問根結點的操作發生在遍歷其左右子樹之后。

下面主要分析前序遞歸遍歷，中序與后序圖解類似，可以自己畫畫看。

????????（1.）**前序遍歷**，也稱為**深度優先遍歷**。它從根節點開始，遞歸地訪問左子樹，然后訪問右子樹。二叉樹的前序遍歷是按以下順序訪問節點的序列： 1. 根節點 2. 根節點的左子樹 3. 根節點的右子樹

????????當左邊遞歸到空時，會從葉子節點開始依次返回遞歸的結果，然后開始遍歷右子樹，遞歸迭代。
前序遍歷遞歸圖解：

前序遍歷的代碼：
void PrevOrder(TreeNode* root)
{if (root == NULL){printf("N ");return;}printf("%d ", root->data);PrevOrder(root->left);PrevOrder(root->right);
}
前序遍歷結果為：1 2 3 4 5 6

????????（2.)**中序遍歷**。它從根節點開始，遞歸地訪問左子樹，然后訪問當前節點，然后訪問右子樹。二叉樹的中序遍歷是按以下順序訪問節點的序列： 1. 當前節點的左子樹 2. 當前節點 3. 當前節點的右子樹

中序遍歷代碼：
void InOrder(TreeNode* root)
{if (root == NULL){printf("N ");return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
}
中序遍歷的結果：3 2 1 5 4 6

????????（3.）**后序遍歷**。它從根節點開始，遞歸地訪問左子樹，然后訪問右子樹，最后訪問根節點。二叉樹的后序遍歷是按以下順序訪問節點的序列： 1. 左子樹的所有節點 2. 右子樹的所有節點 3. 根節點

后序遍歷代碼：
void PostOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}PrevOrder(root->left);PrevOrder(root->right);printf("%d ", root->data);
}
前序遍歷結果為：3 2 5 6 4 1

1.2.2?層序遍歷及判斷是否為完全二叉樹

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

????????實現層序遍歷，我們可以用到隊列，A進入隊列，可以去到B和C的地址，讓A出隊就能取到A的數據，然后通過B可以取到D、通過C可以取到E，F，讓他們依次入隊出隊，就能取到每一層的節點，最后隊列為空就結束
void LevelOrder(TreeNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);int levelSize = 1;while (!QueueEmpty(&q)){// 一層一層出while (levelSize--){TreeNode* front = QueueFront(&q);QueuePop(&q);//這里pop掉了front也能取到，因為這只是pop掉了指向節點的指針//并沒有真的把節點pop掉了printf("%d ", front->data);if (front->left)QueuePush(&q, front->left);if (front->right)QueuePush(&q, front->right);}printf("\n");levelSize = QueueSize(&q);}printf("\n");QueueDestroy(&q);
}
判斷是否為完全二叉樹

? ? ? ? 在層序遍歷的基礎上，我們稍作修改就可以了。我們再出隊列的過程中，如果遇到了NULL，那我們就break，然后去判斷NULL的后面是否有數據，如果NULL的后面還有數據，那么這就不是一個完全二叉樹。
bool TreeComplete(TreeNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);int levelSize = 1;while (!QueueEmpty(&q)){TreeNode* front = QueueFront(&q);QueuePop(&q);if (front == NULL)break;QueuePush(&q, front->left);QueuePush(&q, front->right);}// 前面遇到空以后，后面還有非空就不是完全二叉樹while (!QueueEmpty(&q)){TreeNode* front = QueueFront(&q);QueuePop(&q);if (front)//判斷是否為NULL，不是NULL返回false{QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}

1.3?節點個數，葉子節點個數，第k層節點個數以及高度等

接口函數
// 二叉樹節點個數
int BinaryTreeSize(BTNode* root);
// 二叉樹葉子節點個數
int BinaryTreeLeafSize(BTNode* root);
// 二叉樹第k層節點個數
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉樹查找值為x的節點
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
1.二叉樹節點的個數

? ? ? ? 我們用分治的思想，依次遍歷左右兩子樹，如果不是空則+1
int TreeSize(TreeNode* root)
{return root == NULL ? 0 : TreeSize(root->left) +TreeSize(root->right) + 1;
}
2.葉子節點的個數

? ? ? ? 葉子節點的特征就是，左孩子右孩子都為空，則視為葉子節點，分別遍歷兩個子樹的葉子節點，是葉子節點就返回1。
int treeleafsize(TreeNode* root)
{//空返回0if (root == NULL)return 0;//是葉子返回1if ((root->left == NULL) &&(root->right == NULL))return 1;//非0也不是葉子，那繼續往下找葉子//分治 葉子=左+右return treeleafsize(root->left) +treeleafsize(root->right);
}
3.第k層的節點個數

? ? ? ? 同樣的，這里我們也用分治的思想。我們引入了變量k，我們從第一層開始，如果k不等于1的話，我就進行k-1的操作，直到k=1就到達了指定層數，k=1那么節點數就+1，統計每次遞歸到k=1的節點，就得到了第k層的節點數。
int lvksize(TreeNode* root, int k)
{assert(k > 0);if (root == NULL)return 0;if (k == 1){return 1;}return lvksize(root->left, k - 1) + lvksize(root->right, k - 1);
}
4.二叉樹查找值為x的節點

? ? ? ? 節點的查找不再是簡單的遍歷，我們遞歸一次就要保存一次遞歸的節點，因為遞歸是返回給每次調用的函數本身，函數是不能存值的，因此我們需要一個變量保存。
TreeNode* findtree(TreeNode* root, int x)
{if (root == NULL){return NULL;}if (root->data==x){return root;}//保存左子樹的結果TreeNode* ret=findtree(root->left,x);if (ret){return ret;} //保存右子樹的結果TreeNode* ret1=findtree(root->right, x);if (ret1){return ret1;}
}
5. 二叉樹的高度

要找到二叉樹的高度，我們可以使用以下算法（同樣是分治的思想）：

????????1. 從根節點開始。

????????2. 如果節點沒有子節點，那么它的高度為 0。

? ? ? ? 3.分別遍歷左右子樹

? ? ? ? 4. 如果節點有一個子節點，那么它的高度為 1 加上其子節點的高度。

? ? ? ? 5. 如果節點有兩個子節點，那么它的高度為 1 加上其子節點高度的最大值。

? ? ? ? 6.比較左右子樹的大小，大的那個為二叉樹的高度，最后加上根節點，就得到了二叉樹的高度。
int TreeHeight(TreeNode* root)
{if (root == NULL)return 0;return fmax(TreeHeight(root->left), TreeHeight(root->right)) + 1;
}
這里我們用到fmax函數進行比較，當然你也可以選擇使用運算符進行比較。

1.4 二叉樹的創建和銷毀

1.二叉樹的創建

? ? ? ? 用先序，中序，后序的方式去直接創建二叉樹，那么，知道先序的序列就用先序的序列去遞歸創建樹，知道中序的序列就用中序的序列去遞歸創建樹,知道后序的序列就用后序的序列去遞歸創建樹

eg：用數組來存儲
TreeNode* TreeCreate(char* a, int* pi)
{if (a[*pi] == '#'){(*pi)++;return NULL;}TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));if (root == NULL){perror("malloc fail");exit(-1);}root->data = a[(*pi)++];root->left = TreeCreate(a, pi);root->right = TreeCreate(a, pi);return root;
}
2.二叉樹的銷毀

? ? ? ? 關于二叉樹的銷毀，你可以以任意序列的去銷毀二叉樹
void destroy_tree(Node *root) {if (root == NULL) {return;}destroy_tree(root->left);destroy_tree(root->right);free(root);
}