?
目錄
定義結構體：
初始化：
手動創建一個二叉樹：
前序遍歷：
中序遍歷：
后序遍歷
?二叉樹節點個數：
葉子節點個數：
二叉樹第k層節點個數：
二叉樹的高度：
?查找值為x的節點：
二叉樹的層序遍歷：
判斷二叉樹是否為完全二叉樹：
銷毀二叉樹：
二叉樹增刪查改沒有具體意義。我們主要實現搜索二叉樹
特殊的二叉樹---完全二叉樹（堆） 適合數組結構表示? （堆結構下節更新）
對于普通二叉樹我們采用 鏈式結構
定義結構體：
一個結構體就是一個樹節點
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//鏈式二叉樹//定義結構體 --- 一個結構體就是一個樹節點
typedef char BTDataType;
typedef struct BinaryTreeNode
{BinaryTreeNode* left; //指向節點的指針 類型為節點類型BinaryTreeNode* right;BTDataType data;
}BTNode;初始化：
? 鏈式結構 開辟空間創建新節點
BTNode BuyNode(BTDataType x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));newnode->left = NULL;newnode->right = NULL;newnode->data = x;return newnode;
}手動創建一個二叉樹：
BTNode* CreatBinaryTree()
{BTNode* nodeA = BuyNode('A');BTNode* nodeB = BuyNode('B');BTNode* nodeC = BuyNode('C');BTNode* nodeD = BuyNode('D');BTNode* nodeE = BuyNode('E');BTNode* nodeF = BuyNode('F');nodeA->left = nodeB;nodeA->right = nodeC;nodeB->left = nodeD;nodeC->left = nodeE;nodeC->right = nodeF;return nodeA;
}前序遍歷：
---? 根左右? ?打印放在最前面 再左、右遞歸
void PerOrder(BTNode* root)
{if (root == NULL){return NULL;}printf("%c", root->data);PerOrder(root->left);PerOrder(root->right);
}畫圖理解遞歸過程：?
中序遍歷：
---? 左根右? 打印放在中間 先左遞歸 打印 再右遞歸
void MidOrder(BTNode* root)
{if (root == NULL){return NULL;}MidOrder(root->left);printf("%c", root->data);MidOrder(root->right);
}?
后序遍歷
-- 左右根
void PostOrder(BTNode* root)
{if (root == NULL){return NULL;}PostOrder(root->left);PostOrder(root->right);printf("%c", root->data);
}?二叉樹節點個數：
為空返回0，不為空去遞歸左右子樹，+1是遞歸完左右返回之后+1的，即就會算此時的root節點的數量。（下圖有具體的遞歸過程）左+右+根（1）
int BinaryTreeSize(BTNode* root)
{return root == NULLL ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
葉子節點個數：
走到葉子返回1（不再向下遞歸），返回 左+右? ? ?不算根的個數
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL){return 0;}if (root->left && root->right == NULL) //在遞歸的過程中 走到葉子就會返回1 最后左+右即可{return 1;}return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
二叉樹第k層節點個數：
往下走一層k都會減一，假如要求第五層，走到第五層k=1，把1返回即可
int BinaryTreeLeaveSize(BTNode* root, int k)
{if (root == NULL){return 0;}if (k == 1){return 1;}return BinaryTreeLeaveSize(root->left, k - 1) + BinaryTreeLeaveSize(root->right, k - 1);
}?
二叉樹的高度：
當這棵樹為空樹時,二叉樹的高度應該是0,所以當數為空我們返回0,然而當樹不等于空時,我們可以以大事化小,小事化了的思想,將當前樹的高度轉換成左右子樹兩個中的最大高度再加上一,然后左右子樹中最大高度的樹的高度又可以轉換成我們剛剛的思想,就這樣不斷遞歸下去直接我們遇見空節點.
nt BinaryTreeDepth(BTNode* root)
{//為空 返回0//遞歸左樹 遇到左右都為空的節點 返回1 再遞歸右樹 左右都為空 返回1，//左右比較 返回大的+1if (root == NULL){return NULL;}NTNode* left = BinaryTreeDepth(root->left);NTNode* right = BinaryTreeDepth(root->right);return left > right ? left + 1 : right + 1;
}?查找值為x的節點：
只要找到了就不會返回空，只要返回的不是空就是找到了。左子樹找到了就不會再去右子樹找
BTNode* BinaryTreeFind(BTNode* root, BTNodeType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode* left = BinaryTreeFind(root->left);if (left != NULL){return left;}BTNode* right = BinaryTreeFind(root->right);if (left != NULL){return right;}return NULL;
}二叉樹的層序遍歷：
借助隊列
- 先將根入隊列
- 當前節點出隊列后,將次此節點的左右孩子入隊列
- 一直這樣循環往復直到隊列為空,說明最后一層已經沒有節點了,遍歷結束
void BinaryTreeLevelOrder(BTNode* root)
{if (root == NULL){return NULL;}Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);printf("%c", front->data);if (front->left != NULL){QueuePush(&q, front->left);}if (front->right != NULL){QueuePush(&q, front->right);}}printf("\n");QueueDestroy(&q);
}判斷二叉樹是否為完全二叉樹：
完全二叉樹和非完全二叉樹的區別：前者一旦有空后面就都是空，而后者一旦有空后面還會出現非空。
第二個while循環是遇到空時候，看后面是否全為空，如果是就是完全二叉樹
QueueEmpty(&q)判斷隊列是否為空，看的是front是否為空
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front == NULL){break;}else{QueuePush(&q, front->left);QueuePush(&q, front->right);}}//遇到空了while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front){QueueDestory(&q);return false;}}QueueDestory(&q);return true;
}銷毀二叉樹：
void BinaryTreeDestory(BTNode* root)
{if (root == NULL){return;}BinaryTreeDestory(root->left);BinaryTreeDestory(root->right);free(root);
}
)
