devbox
小蓝xlanll
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

二叉树的构建与遍历（C语言）_c语言二叉树的创建与遍历

作者：小蓝xlanll | 2024-04-30 17:40:40

赞

踩

c语言二叉树的创建与遍历

目录

一、二叉树的存储结构

二、二叉树的遍历

三.节点个数以及高度

四、构建二叉树

五：完整代码

一、二叉树的存储结构

1.顺序存储：

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空 间的浪费。而现实中使用中只有堆才会使用数组来存储。二叉树顺 序存储在物理上是一个数组，在逻辑上是一颗二叉树。

2.链式存储

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是 链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。 

下面主要来讲 链式存储 的二叉树。所以得先用结构体来表示二叉树单个节点的结构： 
  1. typedef int DataType;
  2. typedef struct BinaryTreeNode{
  3. 	DataType data;
  4. 	struct BinaryTreeNode* left;//左孩子节点的地址
  5. 	struct BinaryTreeNode* right;//右孩子节点的地址
  6. }BTNode;

二、二叉树的遍历

用递归的方式创建二叉树的过程比较抽象，所以先来讲二叉树的遍历（前、中、后）序。现在有下图的二叉树，我们依次来遍历此二叉树 ：

1. 前序遍历 —— 访问根结点的操作发生在遍历其左右子树之前。
在下面代码中打印出节点的data值就是遍历该节点，前序遍历代码如下： 
  1. void PreOrder(BTNode* root){//前序遍历
  2. 	if (root == NULL){//空树就返回
  3. 		return;
  4. 	}
  5. 	printf("%d ", root->data);//打印当前节点的data值
  6. 	PreOrder(root->left);//遍历左子树
  7. 	PreOrder(root->right);//遍历右子树
  8. }
上面的代码中，root为指向根节点的指针（根节点是值为1的节点）。下面继续用图像的形式来直观的上述代码的执行流程：

 所以前序遍历的结果为：1，2，3，4，5，6

2. 中序遍历 —— 访问根结点的操作发生在遍历其左右子树之中（间）。
中序遍历的代码只需要在前序遍历的代码上稍稍修改就好： 
  1. void InOrder(BTNode* root){//中序遍历
  2. 	if (root == NULL){
  3. 		return;
  4. 	}
  5. 	InOrder(root->left);
  6. 	printf("%d ", root->data);
  7. 	InOrder(root->right);
  8. }

那么中序遍历的结果为：3，2，1，5，4，6

3. 后序遍历 —— 访问根结点的操作发生在遍历其左右子树之后。 
  1. void PostOrder(BTNode* root){//后序遍历
  2. 	if (root == NULL){
  3. 		return;
  4. 	}
  5. 	PostOrder(root->left);
  6. 	PostOrder(root->right);
  7. 	printf("%d ", root->data);
  8. }

后序遍历的结果为：3，2，5，6，4，1

三.节点个数以及高度

1.二叉树节点个数

  1. int BinaryTreeSize(BTNode* root){//二叉树节点数
  2. 	if (root == NULL){//空树直接返回0
  3. 		return 0;
  4. 	}
  5. 	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
  6. }

以上代码也是递归，求出左子树的节点个数和右子树的节点个数，把他们加起来就是最终结果。加1指的是加上当前节点。

2.二叉树叶子节点的个数

  1. int BinaryTreeLeafSize(BTNode* root){//叶子节点数
  2. 	if (root == NULL){//空树直接返回0
  3. 		return 0;
  4. 	}
  5. 	if (root->left == NULL&&root->right == NULL){//满足条件，说明遇到了叶子节点，返回1
  6. 		return 1;
  7. 	}
  8. 	return  BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
  9. }

求叶子节点个数，关键在于判定当前节点是否为叶子节点，如果是则 返回1。

3.第k层节点个数（默认根节点为第一层）

  1. int BinaryTreeLevelKSize(BTNode* root, int k){//第k层节点个数
  2. 	if (root == NULL || k < 1){//空树或者k不合法，直接返回0
  3. 		return 0;
  4. 	}
  5. 	if (k == 1){//当前的某一个节点
  6. 		return 1;
  7. 	}
  8. 	return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
  9. }

用直观的一幅图来理解上述代码：

 

 当想要求二叉树的第K层节点个数时，可以把问题转化成求其左右子树的第K-1层的节点个数，递归出口为root==NULL或当K==1时返回1，那么就求出了第K层节点个数。

4.二叉树的深度（只有一个节点那么深度是1）

  1. int Depth(BTNode* root){//计算树的深度
  2. 	if (root == NULL){//无左右子树直接返回0
  3. 		return 0;
  4. 	}
  5. 	int leftdepth=Depth(root->left) + 1;//求其左子树深度
  6. 	int rightdepth = Depth(root->right) + 1;//求其右子树深度
  7. 	return leftdepth > rightdepth ? leftdepth : rightdepth;
  8. }

将问题转化为求左右子树的深度，但是函数的返回值只有一个，返回值为左右子树中最深的树的深度。注意递归出。

5.查找某个节点

  1. BTNode* BinaryTreeFind(BTNode* root, DataType x){//查找某个节点
  2. 	if (root == NULL){
  3. 		return NULL; 
  4. 	}
  5. 	if (root->data == x){
  6. 		return root;
  7. 	}
  8. 	BTNode* ret=BinaryTreeFind(root->left, x);
  9. 	if (ret){
  10. 		return ret;//找到了直接返回，就不用在遍历其右子树
  11. 	}
  12. 	return BinaryTreeFind(root->right, x);
  13. }

用前序遍历的思想来创建二叉树，树为空，直接返回。先判断当前节点的值是否是要查找的值，如果不是，那么遍历其左子树，一旦找到就返回当前节点的地址。注意：在返回其左子树查找的结果时，要判断当前结果是否为空，如果是空，说明没有找到，那么还需要在右子树中去查找。

四、构建二叉树

链式存储的二叉树需要在堆上申请空间，所以先给出申请单个节点的代码：

  1. BTNode* BuyNode(DataType x){
  2. 	BTNode* node = (BTNode *)malloc(sizeof(BTNode));
  3. 	if (node == NULL){
  4. 		perror("malloc");
  5. 		exit(0);
  6. 	}
  7. 	node->left = NULL;
  8. 	node->right = NULL;
  9. 	node->data = x;
  10. 	return node;
  11. }

默认把单个节点的left和right的值置为NULL，返回值为创建好的节点的地址。

构建二叉树时需要用到前序遍历的思想，就是先创建根节点，然后在创建其左右子树。假如要创建如下图的二叉树：

首先会得到二叉树中的值为：1 2 3 4 5 6，那么此时需要用数组将这些值保存起来，例如：

DataType arr[] = { 1, 2, 3,4, 5,6};

这时，如果用前序遍历(递归)的思想来创建这颗树，那么会发现根本找不到递归出口，无法创建。那么得找到那个递归的出口，现在可以把要创建的二叉树假想成下图的样子：

 对二叉树进行补充，补充上无效值0，那么保存二叉树值的数组变成：

DataType arr[] = { 1, 2, 3, 0, 0, 0, 4, 5, 0, 0, 6 ，0，0};

此时递归出口就是碰到无效值退出。先上代码：

  1.  
  2. BTNode* _CreatBinaryTree(DataType* arr, int size, DataType invalid, int *subscript){//创建二叉树
  3. 	if (*subscript < size&&arr[*subscript]!=invalid){//当没有越界或者没有碰到无效值就执行下面的代码
  4. 		BTNode* root = BuyNode(arr[*subscript]);//创建当前根节点
  5. 		(*subscript)++;//相当于数组下标加1
  6. 		root->left = _CreatBinaryTree(arr, size, invalid, subscript);//创建左子树
  7. 		(*subscript)++;
  8. 		root->right = _CreatBinaryTree(arr, size, invalid, subscript);
  9. 		return root;
  10. 	}
  11. 	return NULL;
  12. }

此时代码有四个参数，第一个参数为：数组的首地址，第二个参数为：数组此时包含的元素个数，第三个参数为：数组中的无效值（可更改），第四个参数是一个变量的地址，这个变量初始值为0，代表数组元素的下标。

利用前序遍历的思想，在每次调用函数时就把当前根节点创建好，然后在创建其左右子树，需要注意的是：每次创建左右子树时数组的下标需要加1，所以才有了变量subscript，每次进行传递地址，以保证数组的下标在不断加1（也可以定义一个全局变量，此时就不用传递地址了）。递归结束条件为：碰到无效值0或者下标大于数组合法下标。

五：完整代码

1.BinaryTreeNode.h

  1. #pragma once
  2. #include <stdio.h>
  3. #include <windows.h>
  4. #include <assert.h>
  5. typedef int DataType;
  6. typedef struct BinaryTreeNode{
  7. 	DataType data;
  8. 	struct BinaryTreeNode* left;//左孩子节点的地址
  9. 	struct BinaryTreeNode* right;//右孩子节点的地址
  10. }BTNode;
  11. extern BTNode* CreatBinaryTree(DataType* arr, int size, DataType invalid);
  12. extern void PreOrder(BTNode* root);
  13. extern void InOrder(BTNode* root);
  14. extern void PostOrder(BTNode* root);
  15. extern int BinaryTreeSize(BTNode* root);
  16. extern int BinaryTreeLeafSize(BTNode* root);
  17. extern int BinaryTreeLevelKSize(BTNode* root, int k);
  18. extern BTNode* BinaryTreeFind(BTNode* root, DataType x);
  19. extern int Depth(BTNode* root);
  20. extern void BinaryTreeDestory(BTNode** root);

2.BinaryTreeNode.c

  1. #include "BinaryTreeNode.h"
  2. BTNode* BuyNode(DataType x){
  3. 	BTNode* node = (BTNode *)malloc(sizeof(BTNode));
  4. 	if (node == NULL){
  5. 		perror("malloc");
  6. 		exit(0);
  7. 	}
  8. 	node->left = NULL;
  9. 	node->right = NULL;
  10. 	node->data = x;
  11. 	return node;
  12. }
  13. BTNode* _CreatBinaryTree(DataType* arr, int size, DataType invalid, int *subscript){//创建二叉树
  14. 	if (*subscript < size&&arr[*subscript]!=invalid){//当没有越界或者没有碰到无效值就执行下面的代码
  15. 		BTNode* root = BuyNode(arr[*subscript]);//创建当前根节点
  16. 		(*subscript)++;//相当于数组下标加1
  17. 		root->left = _CreatBinaryTree(arr, size, invalid, subscript);//创建左子树
  18. 		(*subscript)++;
  19. 		root->right = _CreatBinaryTree(arr, size, invalid, subscript);
  20. 		return root;
  21. 	}
  22. 	return NULL;
  23. }
  24. BTNode * CreatBinaryTree(DataType* arr, int size, DataType invalid){//创建二叉树
  25. 	int subscript = 0;//可以理解为数组下标
  26. 	return _CreatBinaryTree(arr, size, invalid, &subscript);
  27. }
  28. void PreOrder(BTNode* root){//前序遍历
  29. 	if (root == NULL){//空树就返回
  30. 		return;
  31. 	}
  32. 	printf("%d ", root->data);//打印当前节点的data值
  33. 	PreOrder(root->left);//遍历左子树
  34. 	PreOrder(root->right);//遍历右子树
  35. }
  36. void InOrder(BTNode* root){//中序遍历
  37. 	if (root == NULL){
  38. 		return;
  39. 	}
  40. 	InOrder(root->left);
  41. 	printf("%d ", root->data);
  42. 	InOrder(root->right);
  43. }
  44. void PostOrder(BTNode* root){//后序遍历
  45. 	if (root == NULL){
  46. 		return;
  47. 	}
  48. 	PostOrder(root->left);
  49. 	PostOrder(root->right);
  50. 	printf("%d ", root->data);
  51. }
  52. int BinaryTreeSize(BTNode* root){//二叉树节点数
  53. 	if (root == NULL){//空树直接返回0
  54. 		return 0;
  55. 	}
  56. 	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
  57. }
  58. int BinaryTreeLeafSize(BTNode* root){//叶子节点数
  59. 	if (root == NULL){//空树直接返回0
  60. 		return 0;
  61. 	}
  62. 	if (root->left == NULL&&root->right == NULL){//满足条件，说明遇到了叶子节点，返回1
  63. 		return 1;
  64. 	}
  65. 	return  BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
  66. }
  67. int BinaryTreeLevelKSize(BTNode* root, int k){//第k层节点个数
  68. 	if (root == NULL || k < 1){//空树或者k不合法，直接返回0
  69. 		return 0;
  70. 	}
  71. 	if (k == 1){//当前的某一个节点
  72. 		return 1;
  73. 	}
  74. 	return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
  75. }
  76. BTNode* BinaryTreeFind(BTNode* root, DataType x){//查找某个节点
  77. 	if (root == NULL){
  78. 		return NULL; 
  79. 	}
  80. 	if (root->data == x){
  81. 		return root;
  82. 	}
  83. 	BTNode* ret=BinaryTreeFind(root->left, x);
  84. 	if (ret){
  85. 		return ret;//找到了直接返回，就不用在遍历其右子树
  86. 	}
  87. 	return BinaryTreeFind(root->right, x);
  88. }
  89. int Depth(BTNode* root){//计算树的深度
  90. 	if (root == NULL){
  91. 		return 0;
  92. 	}
  93. 	int leftdepth=Depth(root->left) + 1;//求其左子树深度
  94. 	int rightdepth = Depth(root->right) + 1;//求其右子树深度
  95. 	return leftdepth > rightdepth ? leftdepth : rightdepth;
  96. }
  97. void BinaryTreeDestory(BTNode** root){//销毁二叉树
  98. 	assert(root);
  99. 	if (*root == NULL){
  100. 		return;
  101. 	}
  102. 	BinaryTreeDestory(&(*root)->left);
  103. 	BinaryTreeDestory(&(*root)->right);
  104. 	free(*root);
  105. 	*root = NULL;
  106. }

3.main.c

  1. #include "BinaryTreeNode.h"
  2. int main(){
  3. 	DataType arr[] = { 1, 2, 3, 0, 0, 0, 4, 5, 0, 0, 6 };
  4. 	BTNode* root = CreatBinaryTree(arr,sizeof(arr)/sizeof(arr[0]),-1);
  5. 	PreOrder(root);
  6. 	printf("\n");
  7. 	InOrder(root);
  8. 	printf("\n");
  9. 	PostOrder(root);
  10. 	printf("\n");
  11. 	printf("二叉树节点个数为:%d\n", BinaryTreeSize(root));
  12. 	printf("二叉树叶子节点个数为:%d\n", BinaryTreeLeafSize(root));
  13. 	printf("二叉树第3层节点个数为:%d\n", BinaryTreeLevelKSize(root,3));
  14. 	printf("二叉树深度为:%d\n", Depth(root));
  15. 	BinaryTreeDestory(&root);
  16. 	system("pause");
  17. 	return 0;
  18. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小蓝xlanll/article/detail/514460
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号