数据结构（初阶）（七）----树和二叉树（前中后序遍历） ...

实现链式结构的二叉树


  
⽤链表来表⽰⼀棵⼆叉树，即⽤链来指⽰元素的逻辑关系。 通常的⽅法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别⽤来给出该结点左孩⼦和右孩⼦所在的链结点的存储地址 ，
其结构如下：

1. typedef int BTDataType; // ⼆叉链
2. typedef struct BinaryTreeNode
3. {
4.         struct BinTreeNode* left; // 指向当前结点左孩⼦
5.         struct BinTreeNode* right; // 指向当前结点右孩⼦
6.         BTDataType val; // 当前结点值域
7. }BTNode;

复制代码

遍历

前中后序遍历
前序遍历

也叫先根遍历
先遍历根节点，再遍历左子树，末了遍历右子树
左右根

<img alt="image-20250122120904177" />

<img alt="image-20250122121456060" />

A->B->D->NULL->NULL->NULL->C->E->NULL->NULL->F->NULL->NULL

1. //前序遍历--根左右
2. void PreOrder(BTNode* root)
3. {
4.         if (root == NULL)
5.         {
6.                 printf("NULL ");
7.                 return;
8.         }
9.         printf("%c ", root->data);
10.         PreOrder(root->left);
11.         PreOrder(root->right);
12. }

复制代码

中序遍历

先遍遍历左子树，，再遍历根节点，末了遍历右子树
左根右

<img alt="image-20250122120908431" />

<img alt="image-20250122122358193" />

NULL->D->NULL->B->NULL->A->NULL->E->NULL->C->NULL->F->NULL

1. //中序遍历--左根右
2. void InOrder(BTNode* root)
3. {
4.         if (root == NULL)
5.         {
6.                 printf("NULL ");
7.                 return;
8.         }
9.         InOrder(root->left);
10.         printf("%c ", root->data);
11.         InOrder(root->right);
12. }

复制代码

后序遍历

先遍历左子树，再遍历右子树，末了遍历根节点
左右根

<img alt="image-20250122120912308" />

<img alt="image-20250122123010493" />

NULL->NULL->D->NULL->B->NULL->NULL->E->NULL->NULL->F->C->A

1. //后序遍历--左右根
2. void PostOrder(BTNode* root)
3. {
4.         if (root == NULL)
5.         {
6.                 printf("NULL ");
7.                 return;
8.         }
9.         PostOrder(root->left);
10.         PostOrder(root->right);
11.         printf("%c ", root->data);
12. }

复制代码

节点个数

节点个数 = 1（根节点）+ 左子树节点个数 + 右子树节点个数

1. // ⼆叉树结点个数
2. int BinaryTreeSize(BTNode* root)
3. {
4.         if (root == NULL)
5.         {
6.                 return 0;
7.         }
8.         //节点个数 = 1（根节点）+ 左子树节点个数 + 右子树节点个数
9.         return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
10. }

复制代码

叶子节点个数

叶子节点个数 = 左子树叶子节点个数 + 右子树叶子节点个数

1. //⼆叉树叶⼦结点个数
2. int BinaryTreeLeafSize(BTNode* root)
3. {
4.         if (root == NULL)
5.         {
6.                 return 0;
7.         }
8.         //叶子节点个数 = 左子树叶子节点个数 + 右子树叶子节点个数
9.         if (root->left == NULL && root->right == NULL)
10.         {
11.                 return 1;
12.         }
13.         return BinaryTreeLeafSize(root->left)
14.         + BinaryTreeLeafSize(root->right);
15. }

复制代码

⼆叉树第k层结点个数

当k == 1，直接在当前节点返回，
当k ！= 1，继承向下一层递归，k-1

1. //⼆叉树第k层结点个数
2. int BinaryTreeLevelKSize(BTNode* root, int k)
3. {
4.         if (root == NULL)
5.         {
6.                 return 0;
7.         }
8.         if (k == 1)
9.         {
10.                 return 1;
11.         }
12.         return BinaryTreeLevelKSize(root->left, k - 1)
13.                 + BinaryTreeLevelKSize(root->right, k - 1);
14. }

复制代码

⼆叉树的深度/⾼度

1. //⼆叉树的深度/⾼度
2. int BinaryTreeDepth(BTNode* root)
3. {
4.         if (root == 0)
5.         {
6.                 return 0;
7.         }
8.         //高度 = max（左子树，右子树）+ 1
9.         return 1 + max(BinaryTreeDepth(root->left), BinaryTreeDepth(root->right));
10. }

复制代码

查找值为X的节点

1. //⼆叉树查找值为x的结点
2. BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
3. {
4.         if (root == NULL)
5.         {
6.                 return NULL;
7.         }
8.         if (root->data == x)
9.         {
10.                 return root;
11.         }
12.         BTNode* leftFind = BinaryTreeFind(root->left, x);
13.         if (leftFind)
14.         {
15.                 return leftFind;
16.         }
17.         BTNode* rightFind = BinaryTreeFind(root->right, x);
18.         if (rightFind)
19.         {
20.                 return rightFind;
21.         }
22.         return NULL;
23. }

复制代码

二叉树的销毁

使用后序遍历

1. //⼆叉树销毁
2. void BinaryTreeDestory(BTNode** root)
3. {
4.         if (*root == NULL)
5.         {
6.                 return;
7.         }
8.         BinaryTreeDestory(&((*root)->left));
9.         BinaryTreeDestory(&((*root)->right));
10.         free(*root);
11.         *root = NULL;
12. }

复制代码

层序遍历

按照条理依次遍历（从上到下，从左到右）
广度优先遍历

<img alt="image-20250218160303782" />

思路：
使用队列，根节点入队，循环判定队列是否为空，不为空取队头，将队头结点左右孩子入队（非空）

1. //层序遍历
2. void LevelOrder(BTNode* root)
3. {
4.         Queue q;
5.         QueueInit(&q);
6.         QueuePush(&q, root);
7.         while (!QueueEmpty(&q))
8.         {
9.                 //取队头，出队，将左右孩子(非空)入队
10.                 BTNode* top = QueueFront(&q);
11.                 QueuePop(&q);
12.                 printf("%c ", top->data);
13.                 if (top->left)
14.                 {
15.                         QueuePush(&q,top->left);
16.                 }
17.                 if (top->right)
18.                 {
19.                         QueuePush(&q, top->right);
20.                 }
21.         }
22.         QueueDestory(&q);
23. }

复制代码

判定二叉树是否为完全二叉树

1. // 判断⼆叉树是否是完全⼆叉树
2. bool BinaryTreeComplete(BTNode* root)
3. {
4.         Queue q;
5.         QueueInit(&q);
6.         QueuePush(&q, root);
7.         while (!QueueEmpty(&q))
8.         {
9.                 //取队头，出队，将左右孩子(非空)入队
10.                 BTNode* top = QueueFront(&q);
11.                 QueuePop(&q);
12.                 if (top == NULL)
13.                 {
14.                         break;
15.                 }
16.                 //入队
17.                 QueuePush(&q, top->left);
18.                 QueuePush(&q, top->right);
19.         }
20.         //如果存在非空结点，是非完全二叉树
21.         while (!QueueEmpty(&q))
22.         {
23.                 BTNode* top = QueueFront(&q);
24.                 QueuePop(&q);
25.                 if (top != NULL)
26.                 {
27.                         QueueDestory(&q);
28.                         return false;
29.                 }
30.         }
31.         QueueDestory(&q);
32.         return true;
33. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。