一、二叉树的遍历

“遍历”就是按某种规则 依次访问树中的每个节点，确保 每个节点都被访问一次且只访问一次

        遍历：前序 中序 后序（深度优先），层序（广度优先）

二、深度优先遍历

任何一个二叉数、都要看做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. 循环直到队列为空。

等价于数组的访问顺序，我们直到其实堆就是按数组进行存放的

好了本期内容我们就到这里结束了！谢谢大家的点赞和收藏！