一、二叉樹的遍歷

“遍歷”就是按某種規則?依次訪問樹中的每個節點，確保?每個節點都被訪問一次且只訪問一次

????????遍歷：前序 中序 后序（深度優先），層序（廣度優先）

二、深度優先遍歷

任何一個二叉數、都要看做3個部分：

????????1、根節點；2、左子樹；3、右子樹。

前序：（先根遍歷）根 左子樹 右子樹 -->子樹遇到空才結束，用途：?復制樹、表達式樹轉前綴表達式等

中序：（中根遍歷）?左子樹 根 右子樹 ，用途：?如果是二叉搜索樹（BST），中序遍歷輸出的是升序序列?

后序：（中根遍歷）?左子樹 右子樹 根 ，用途：?刪除樹（先刪子樹再刪根）、表達式樹轉后綴表達式等

示意圖：

二叉樹的前序遍歷實現（利用遞歸的思想）：

????????

代碼實現：

1、二叉樹的初始化

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include <string.h>#define Init_Capcity 5
typedef char BTDataType;
typedef struct BNTreeNode
{BTDataType _data;struct BNTreeNode* left_child;struct BNTreeNode* right_child;
}BNTreeNode;BNTreeNode* BNTreeNode_Init(){BNTreeNode* pt = (BNTreeNode*)malloc(sizeof(BNTreeNode));pt ->left_child =NULL;pt->right_child = NULL;return pt;
}

2、新增子節點

//新增子節點
BNTreeNode* BuyTreeNode(BTDataType val){BNTreeNode* NewNode = (BNTreeNode*)malloc(sizeof(BNTreeNode));NewNode->_data = val;NewNode->left_child = NULL;NewNode->right_child = NULL;return NewNode;
}

3、二叉樹的前序遍歷以及主函數的實現

void BNTraverse(BNTreeNode* root){if(root == NULL){return;}printf("%c  ",root->_data);BNTraverse(root->left_child);BNTraverse(root->right_child);
}int main(){BNTreeNode* Root = BNTreeNode_Init();Root->_data = 'A';Root->left_child = BuyTreeNode('B');Root->right_child = BuyTreeNode('C');(Root->left_child)->left_child = BuyTreeNode('D');(Root->left_child)->right_child = BuyTreeNode('E');(Root->right_child)->left_child = BuyTreeNode('F');BNTraverse(Root);
}

4、二叉樹的中序，后序遍歷

void InOrder(BNTreeNode* root){if(root == NULL){return;}InOrder(root->left_child);printf("%c  ",root->_data);InOrder(root->right_child);
}
void PostOrder(BNTreeNode* root){if(root == NULL){return;}PostOrder(root->left_child);PostOrder(root->right_child);printf("%c  ",root->_data);
}

輸出結果：

A ?B ?D ?NULL NULL E ?NULL NULL C ?F ?NULL NULL NULL?
NULL D ?NULL B ?NULL E ?NULL A ?NULL F ?NULL C ?NULL?
NULL NULL D ?NULL NULL E ?B ?NULL NULL F ?NULL C ?A ?

利用類似的遞歸思路求解，二叉樹的元素個數，葉節點個數，深度等

1、二叉樹元素的個數 -->遇到空節點停止

//兩種方法
void TreeSize(BNTreeNode* root,int* psize){if(root == NULL){return;}//static int size = 0; //靜態變量只有當前文件能使用(*psize)++;TreeSize(root->left_child,psize);TreeSize(root->right_child,psize);
}
//不需要額外參數
int TreeSize(BNTreeNode* root){if(root == NULL){return 0;}else{return 1+TreeSize(root->left_child)+TreeSize(root->right_child);}
}

2、葉節點個數-->遍歷到無子節點（葉節點）

//統計葉節點個數
int TreeLeafSize(BNTreeNode* root){if(root == NULL){return 0;}if(root->left_child == NULL && root->right_child == NULL){return 1;}return TreeLeafSize(root->left_child)+TreeLeafSize(root->right_child);
}

3、需要比較左右子樹的深度 -->遇到空節點停止

int TreeDepth(BNTreeNode* root) {if (root == NULL) {return 0;}int left_depth = TreeDepth(root->left_child);int right_depth = TreeDepth(root->right_child);return 1 + (left_depth > right_depth ? left_depth : right_depth);
}

三、廣度優先遍歷（BFS / 層序遍歷）

使用隊列實現，按照“從上到下、從左到右”的層級順序訪問：堆的訪問順序

訪問順序：?A → B → C → D → E → F?

算法：

1. 把根節點放入隊列；

2. 每次從隊列中取出一個節點，訪問它；

3. 如果它有左子、右子節點，把它們加入隊列；

4. 循環直到隊列為空。

等價于數組的訪問順序，我們直到其實堆就是按數組進行存放的

好了本期內容我們就到這里結束了！謝謝大家的點贊和收藏！