二叉树的遍历问题和相关算法（思路梳理和代码实现）

在主包的上一篇博客中，我们介绍了堆的相关知识，这篇博客我们便充分补充下二叉树的相关算法问题，普及下常见的遍历方法。正片开始啦！发车！

遍历（前序+中序+后序+补充层序遍历 )

1. 遍历规则

按照规则，⼆叉树的遍历有：前序/中序/后序的递归结构遍历：

1.前序遍历(Preorder Traversal 亦称先序遍历)：访问根结点的操作发⽣在遍历其左右⼦树之前

访问顺序为：根结点、左⼦树、右⼦树

2.中序遍历(Inorder Traversal)：访问根结点的操作发⽣在遍历其左右⼦树之中（间）

访问顺序为：左⼦树、根结点、右⼦树

3.后序遍历(Postorder Traversal)：访问根结点的操作发⽣在遍历其左右⼦树之后

访问顺序为：左⼦树、右⼦树、根结点

那么我们先挑战下分别用三种遍历方法，来遍历这棵二叉树。

答案：

在这里我们要熟悉掌握递归，在有正确的逻辑思路后，便能信手拈来。

2.代码实现

//前序遍历--根左右 void preOrder(BTNode* root) { if (root == NULL) { return NULL; } printf("%d", root->data); preOrder(root->left); preOrder(root->right); }

//中序遍历--左跟右 void inOrder(BTNode* root) { if (root == NULL) { return NULL; } preOrder(root->left); printf("%d", root->data); preOrder(root->right); }

//后序遍历--左右根 void postOrder(BTNode* root) { if (root == NULL) { return NULL; } preOrder(root->left); preOrder(root->right); printf("%d", root->data); }

3.层序遍历

除了先序遍历、中序遍历、后序遍历外，还可以对⼆叉树进⾏层序遍历。设⼆叉树的根结点所在层数为1，层序遍历就是从所在⼆叉树的根结点出发，⾸先访问第⼀层的树根结点，然后从左到右访问第2层上的结点，接着是第三层的结点，以此类推，⾃上⽽下，⾃左⾄右逐层访问树的结点的过程就是层序遍历。

实现层序遍历需要额外借助数据结构：队列

//层序遍历 void leverOrder(BTNode* root) { Queue q; QueueInit(&q); QueuePush(&q,root); while (!QueueEmpty(&q)) { BTNode* top = QueueFront(&q); QueuePop(&q); printf("%c ",top->data); if (top->left) QueuePush(&q, top->left); QueuePush(&q, top->right); } QueueDestroy(&q); }

二叉树的相关算法

1.先前介绍

// ⼆叉树结点个数 int BinaryTreeSize(BTNode* root); //int BinaryTreeSize(BTNode* root,int* psize); // ⼆叉树叶⼦结点个数 int BinaryTreeLeafSize(BTNode* root); // ⼆叉树第k层结点个数 int BinaryTreeLevelKSize(BTNode* root, int k); //⼆叉树的深度/⾼度 int BinaryTreeDepth(BTNode* root); // ⼆叉树查找值为x的结点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x); // ⼆叉树销毁 void BinaryTreeDestory(BTNode** root);

2.代码实现

1.二叉树结点个数

int BinaryTreeSize(BTNode* root) { if (root == NULL) { return 0; } return 1+BinaryTreeSize(root->left) + BinaryTreeSize(root->right); }

2.⼆叉树叶⼦结点个数

int BinaryTreeLeafSize(BTNode* root) { if (root == NULL) { return 0; } if (root->right == NULL && root->left == NULL) { return 1; } return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right); }

3.⼆叉树第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); }

4.⼆叉树的深度/⾼度

int BinaryTreeDepth(BTNode* root) { if (root == NULL) { return 0; } int leftDep = BinaryTreeDepth(root->left); int rightDep = BinaryTreeDepth(root->right); return 1 + (leftDep > rightDep ? leftDep:rightDep); }

5.⼆叉树查找值为x的结点

BTNode* BinaryTreeFind(BTNode* root, BTDataType x) { if (root == NULL) { return NULL; } if (root->data == x) { return root; } BTNode* leftFind = BinaryTreeFind(root->left,x); if (leftFind) { return leftFind; } BTNode* rightFind = BinaryTreeFind(root->right,x); if (rightFind) { return rightFind; } }

6.⼆叉树销毁

void BinaryTreeDestory(BTNode** root) { if (*root == NULL) { return ; } BinaryTreeDestory(&((*(root))->right)); BinaryTreeDestory(&((*(root))->left)); free(*root); *root = NULL; }

做有意义的事，过意义的人生！欢迎大家一起讨论！创作不易，小博主求求赞啦！