• 数据结构-链式二叉树

    目录

    链式二叉树的概念及结构

    概念

    结构

    链式二叉树的遍历

    前序遍历

    中序遍历

    后序遍历

    层序遍历

    链式二叉树的基本操作

    求结点个数BTreeSize

    求叶子结点个数BTreeLeafSize

    求某一层的结点个数BTreeKLevelSize

    求链式二叉树的深度BTreeDepth

    判断两棵链式二叉树是否相同BTreeIsSame

    链式二叉树的创建与销毁

    创建BTreeCreate

    销毁BTreeDestroy

    代码

    链式二叉树的概念及结构

    概念

       对于那些非完全二叉树，由于顺序存储结构的空间利用率低，因此二叉树一般都采用链式存储结构，用链表结点来存储二叉树中的每一个结点。在链式二叉树中，结点结构通常包括数据域和若干个指针域。a7492c11e4d74e05b8cd0c4333605c7f.png

    结构

       链式二叉树的结构一般分为两种，一种是二叉链，另一种是三叉链。二叉链的结点包含存储数据的变量，存储左孩子的指针以及存储右孩子的指针。而三叉链的结点除了包含存储数据的变量，存储左孩子的指针以及存储右孩子的指针，还包含存储双亲的指针。特别的在二叉链中，若有n个结点，则一定会有n+1个空指针。5726e2ac8c3b4632825191c56d3a5b0b.png

    链式二叉树的遍历

       二叉树的遍历是指按某条搜索路径访问树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。因为二叉树是递归定义的，遍历一棵二叉树便要决定对根结点，左子树和右子树的访问顺序。根据访问根结点的顺序不同可以分为前序遍历，中序遍历和后序遍历。以下面这颗二叉树为例：89be033d455341f896e038bc4aac5f43.png

     

    1. BinaryTreeNode* BuyBinaryTreeNode(BTDataType x) // 创建二叉链结点
    2. {
    3. 	BinaryTreeNode* node = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
    4. 	if (node == NULL) // 检查结点是否开辟成功
    5. 	{
    6. 		perror("malloc fail");
    7. 		return NULL;
    8. 	}
    9.  
    10. 	node->data = x; // 先将左右指针置空
    11. 	node->left = NULL;
    12. 	node->right = NULL;
    13.  
    14. 	return node;
    15. }
    16.  
    17. int main()
    18. {
    19.  
    20.     BinaryTreeNode* node1 = BuyBinaryTreeNode(1);
    21. 	BinaryTreeNode* node2 = BuyBinaryTreeNode(2);
    22. 	BinaryTreeNode* node3 = BuyBinaryTreeNode(3);
    23. 	BinaryTreeNode* node4 = BuyBinaryTreeNode(4);
    24. 	BinaryTreeNode* node5 = BuyBinaryTreeNode(5);
    25. 	BinaryTreeNode* node6 = BuyBinaryTreeNode(6);
    26. 	BinaryTreeNode* node7 = BuyBinaryTreeNode(7);
    27. 	node1->left = node2;
    28. 	node1->right = node3;
    29. 	node2->left = node4;
    30. 	node2->right = node5;
    31. 	node5->left = node6;
    32. 	node3->right = node7;
    33.  
    34. 	BinaryTreeNode* root = node1;
    35.  
    36. }

    前序遍历

       先访问根结点，再访问左子树，最后访问右子树。fa1267719f3f4b76913ef5e882b661b4.png

    中序遍历

    数据结构实验 排序数基本操作
    doc 4星 超过85%的资源 60KB
    下载

       先访问左子树，再访问根结点，最后访问右子树。233f72138b414a60901937e8f1da4e5c.png

    后序遍历

       先访问左子树，再访问右子树，最后访问根结点。e8cfe075684e4c53a003212212aa7b71.png

    层序遍历

       进行层序遍历，需要借助队列。先将根结点入队，然后出队，若不为空，则将它的左右结点入队，然后继续入队出队直到队列为空。

    1. // 队列
    2. #include "BinaryTree.h"
    3.  
    4. typedef struct BinaryTreeNode* QueueDataType; // 存储的数据类型
    5.  
    6. typedef struct QueueNode
    7. {
    8. 	struct QueueNode* next; // 指向下一个结点
    9. 	QueueDataType data; // 存储数据
    10. }QueueNode;
    11.  
    12. typedef struct Queue
    13. {
    14. 	QueueNode* head; // 头指针
    15. 	QueueNode* tail; // 尾指针
    16. }Queue;
    17.  
    18. extern void QueueInit(Queue* pq);
    19. extern void QueueDestroy(Queue* pq);
    20. extern void QueuePush(Queue* pq, QueueDataType x);
    21. extern void QueuePop(Queue* pq);
    22. extern QueueDataType QueueFront(Queue* pq);
    23. extern QueueDataType QueueBack(Queue* pq);
    24. extern size_t QueueSize(Queue* pq);
    25. extern bool QueueEmpty(Queue* pq);

    9853c343aca4429d85bf205c0c6a54ce.png   利用层序遍历可以判断链式二叉树是否为完全二叉树，其思路为：在层序遍历的过程中，如果遇到结点为空则跳出循环，将剩下没有出队的结点依次出队，如果有非空结点出队，则说明该链式二叉树为非完全二叉树；如果剩下没有出队的结点都为空则说明为完全二叉树。079122fa40da40439c89e4738d3b5a1c.png

    1. bool BTreeComplete(BinaryTreeNode* root) // 判断是否为完全二叉树
    2. {
    3. 	Queue q;
    4. 	QueueInit(&q);
    5.  
    6. 	QueuePush(&q, root);
    7.  
    8. 	while (!QueueEmpty(&q))
    9. 	{
    10. 		QueueDataType front = QueueFront(&q);
    11. 		QueuePop(&q);
    12. 		if (front)
    13. 		{
    14. 			/*printf("%d ", front->data);*/
    15. 			QueuePush(&q, front->left);
    16. 			QueuePush(&q, front->right);
    17. 		}
    18. 		else
    19. 		{
    20. 			break; // 遇到空结点跳出循环
    21. 		}
    22. 	}
    23.  
    24. 	while (!QueueEmpty(&q))
    25. 	{
    26. 		if (QueueFront(&q)!=NULL) // 遇到非空结点，返回false，说明为非完全二叉树
    27. 		{
    28. 			QueueDestroy(&q);
    29.  
    30. 			return false;
    31. 		}
    32. 		QueuePop(&q);
    33. 	}
    34.  
    35. 	QueueDestroy(&q);
    36. 	return true; // 后面没有非空结点，说明是完全二叉树，返回true
    37. }

    链式二叉树的基本操作

    d7f41e22858a4443992d4cca5de66d16.png

    求结点个数BTreeSize

    61875477ef684eedbe1f211d227e10f5.png

    求叶子结点个数BTreeLeafSize

    0d5e4d4518934037b706d688517bafd8.png

    求某一层的结点个数BTreeKLevelSize

    C++实现树（二叉链表实现）
    application/x-rar 4星 超过85%的资源 952KB
    下载

    86a72c1fa5be4e8b8d3d805ee78b5117.png

    求链式二叉树的深度BTreeDepth

    5f2e53e3eef14daaa560df9d66c9fa72.png

    判断两棵链式二叉树是否相同BTreeIsSame

    b99590c91a7e44c6af42da2b45df7d6e.png

    链式二叉树的创建与销毁

    创建BTreeCreate

       创建链接

    1. #include 
    2.  
    3. typedef struct TreeNode
    4. {
    5.     struct TreeNode* left;
    6.     struct TreeNode* right;
    7.     char ch;
    8. }TreeNode;
    9.  
    10. TreeNode* TreeCreate(char* p,int* pi)
    11. {
    12.     if(p[*pi]!='\0')
    13.     {    
    14.         if(p[*pi]!='#')
    15.         {
    16.             TreeNode* node=(TreeNode*)malloc(sizeof(TreeNode));
    17.             if(node==NULL)
    18.             {
    19.                 perror("malloc");
    20.                 return NULL;
    21.             }
    22.             node->ch=p[*pi];
    23.             (*pi)++;
    24.             node->left=TreeCreate(p,pi);
    25.             node->right=TreeCreate(p,pi);
    26.             return node;
    27.         }
    28.         else
    29.         {
    30.             (*pi)++;
    31.             return NULL;
    32.         }
    33.         
    34.     }
    35.     return NULL;
    36. }
    37.  
    38. void TreeInOrder(TreeNode* root)
    39. {
    40.     if(root==NULL)
    41.         return;
    42.     TreeInOrder(root->left);
    43.     printf("%c ",root->ch);
    44.     TreeInOrder(root->right);
    45.         
    46. }
    47.  
    48. int main()
    49. {
    50.     char str[101];
    51.     
    52.     scanf("%s",str);
    53.     
    54.     int i=0;
    55.     
    56.     TreeInOrder(TreeCreate(str, &i));
    57.         
    58.     return 0;
    59. }

    销毁BTreeDestroy

       链式二叉树的销毁应该采用后序遍历的思想，也就是先销毁左子树，再销毁右子树，最后销毁根节点。避免先销毁根节点，左右子树找不到了。fdd1b6cc3b0b440696ed52ff8d3193a7.png

    代码

    1. // 头文件
    2. typedef int BTDataType;
    3.  
    4. typedef struct BinaryTreeNode
    5. {
    6. 	struct BinaryTreeNode* left;
    7. 	struct BinaryTreeNode* right;
    8. 	BTDataType data;
    9. }BinaryTreeNode;
    10.  
    11.  
    12.  
    13. extern BinaryTreeNode* BuyBinaryTreeNode(BTDataType x);
    14. extern void PrevOrder(BinaryTreeNode* root);
    15. extern void InOrder(BinaryTreeNode* root);
    16. extern void PostOrder(BinaryTreeNode* root);
    17. extern int BTreeSize(BinaryTreeNode* root);
    18. extern int BTreeLeafSize(BinaryTreeNode* root);
    19. extern int BTreeKLevelSize(BinaryTreeNode* root, int k);
    20. extern int BTreeDepth(BinaryTreeNode* root);
    21. extern BinaryTreeNode* BTreeFind(BinaryTreeNode* root, BTDataType x);
    22. extern void LevelOrder(BinaryTreeNode* root);
    23. extern bool BTreeComplete(BinaryTreeNode* root);
    24. extern void BTreeDestroy(BinaryTreeNode* root);
    25.  
    26. // 源文件
    27. void PrevOrder(BinaryTreeNode* root) // 前序遍历---根左右
    28. {
    29. 	if (root == NULL)
    30. 	{
    31. 		printf("N ");
    32. 		return;
    33. 	}
    34.  
    35. 	printf("%d ", root->data);
    36. 	PrevOrder(root->left);
    37. 	PrevOrder(root->right);
    38. }
    39.  
    40. void InOrder(BinaryTreeNode* root) // 中序遍历---左根右
    41. {
    42. 	if (root == NULL)
    43. 	{
    44. 		printf("N ");
    45. 		return;
    46. 	}
    47.  
    48. 	InOrder(root->left);
    49. 	printf("%d ", root->data);
    50. 	InOrder(root->right);
    51. }
    52.  
    53. void PostOrder(BinaryTreeNode* root) // 后序遍历---左右根
    54. {
    55. 	if (root == NULL)
    56. 	{
    57. 		printf("N ");
    58. 		return;
    59. 	}
    60.  
    61. 	PostOrder(root->left);
    62. 	PostOrder(root->right);
    63. 	printf("%d ", root->data);
    64.  
    65. }
    66.  
    67. BinaryTreeNode* BuyBinaryTreeNode(BTDataType x) // 创建二叉链结点
    68. {
    69. 	BinaryTreeNode* node = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
    70. 	if (node == NULL) // 检查结点是否开辟成功
    71. 	{
    72. 		perror("malloc fail");
    73. 		return NULL;
    74. 	}
    75.  
    76. 	node->data = x; // 先将左右指针置空
    77. 	node->left = NULL;
    78. 	node->right = NULL;
    79.  
    80. 	return node;
    81. }
    82.  
    83. int BTreeSize(BinaryTreeNode* root) // 求链式二叉树的结点个数
    84. {
    85. 	if (root == NULL)
    86. 	{
    87. 		return 0;
    88. 	}
    89.  
    90. 	return 1 + BTreeSize(root->left) + BTreeSize(root->right);
    91. }
    92.  
    93. int BTreeLeafSize(BinaryTreeNode* root) // 求链式二叉树的叶子结点个数
    94. {
    95. 	if (root == NULL)
    96. 	{
    97. 		return 0;
    98. 	}
    99.  
    100. 	if (root->left == NULL && root->right == NULL)
    101. 	{
    102. 		return 1;
    103. 	}
    104.  
    105. 	return BTreeLeafSize(root->left) + BTreeLeafSize(root->right);
    106. }
    107.  
    108. int BTreeKLevelSize(BinaryTreeNode* root, int k) // 求链式二叉树某一层结点的个数 k+3
    109. {
    110. 	if (root == NULL)
    111. 	{
    112. 		return 0;
    113. 	}
    114. 	if (k == 1)
    115. 	{
    116. 		return 1;
    117. 	}
    118.  
    119. 	return BTreeKLevelSize(root->left, k - 1) + BTreeKLevelSize(root->right, k - 1);
    120. }
    121.  
    122. int BTreeDepth(BinaryTreeNode* root) // 求链式二叉树的层数
    123. {
    124. 	if (!root)
    125. 	{
    126. 		return 0;
    127. 	}
    128.  
    129. 	int leftDepth = BTreeDepth(root->left)+1;
    130. 	int rightDepth = BTreeDepth(root->right)+1;
    131.  
    132. 	return leftDepth > rightDepth ? leftDepth : rightDepth;
    133. }
    134.  
    135. BinaryTreeNode* BTreeFind(BinaryTreeNode* root, BTDataType x) // 按值查找
    136. {
    137. 	if (!root)
    138. 	{
    139. 		return NULL;
    140. 	}
    141. 	if (root->data == x)
    142. 	{
    143. 		return root;
    144. 	}
    145. 	BinaryTreeNode* left = BTreeFind(root->left, x);
    146.  
    147. 	if (left)
    148. 		return left;
    149. 	BinaryTreeNode* right = BTreeFind(root->right, x);
    150.  
    151. 	if (right)
    152. 		return right;
    153.  
    154. 	return NULL;
    155. }
    156.  
    157. void LevelOrder(BinaryTreeNode* root) // 层序遍历
    158. {
    159. 	Queue q;
    160. 	QueueInit(&q);
    161.  
    162. 	QueuePush(&q, root); // 先将根结点入队
    163.  
    164. 	while (!QueueEmpty(&q))
    165. 	{
    166. 		QueueDataType front = QueueFront(&q); // 获取队头元素
    167. 		QueuePop(&q); // 出队
    168. 		if (front) // 不为空则将左右结点入队
    169. 		{
    170. 			printf("%d ", front->data);
    171. 			QueuePush(&q, front->left);
    172. 			QueuePush(&q, front->right);
    173. 		}
    174. 	}
    175.  
    176. 	QueueDestroy(&q);
    177. }
    178.  
    179. bool BTreeComplete(BinaryTreeNode* root) // 判断是否为完全二叉树
    180. {
    181. 	Queue q;
    182. 	QueueInit(&q);
    183.  
    184. 	QueuePush(&q, root);
    185.  
    186. 	while (!QueueEmpty(&q))
    187. 	{
    188. 		QueueDataType front = QueueFront(&q);
    189. 		QueuePop(&q);
    190. 		if (front)
    191. 		{
    192. 			/*printf("%d ", front->data);*/
    193. 			QueuePush(&q, front->left);
    194. 			QueuePush(&q, front->right);
    195. 		}
    196. 		else
    197. 		{
    198. 			break; // 遇到空结点跳出循环
    199. 		}
    200. 	}
    201.  
    202. 	while (!QueueEmpty(&q))
    203. 	{
    204. 		if (QueueFront(&q)!=NULL) // 遇到非空结点，返回false，说明为非完全二叉树
    205. 		{
    206. 			QueueDestroy(&q);
    207.  
    208. 			return false;
    209. 		}
    210. 		QueuePop(&q);
    211. 	}
    212.  
    213. 	QueueDestroy(&q);
    214. 	return true; // 后面没有非空结点，说明是完全二叉树，返回true
    215. }
    216.  
    217. void BTreeDestroy(BinaryTreeNode* root) // 链式二叉树的销毁
    218. {
    219. 	if (!root)
    220. 	{
    221. 		return;
    222. 	}
    223. 	BTreeDestroy(root->left);
    224. 	BTreeDestroy(root->right);
    225. 	free(root);
    226. }
    227.  
    228. bool isSameTree(BinaryTreeNode* p, BinaryTreeNode* q) // 相同返回true否则返回false
    229. {
    230. 	if (p == NULL && q == NULL)
    231. 		return true;
    232.  
    233. 	if (p == NULL || q == NULL)
    234. 		return false;
    235.  
    236. 	if (p->data != q->data)
    237. 		return false;
    238.  
    239. 	return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    240. }

     

     

  • 相关阅读:
    信息学奥赛一本通：1167：再求f(x,n)
    汉字风格迁移篇----EasyFont：一个基于风格学习的系统，可以轻松构建大规模手写字体
    Structure Padding / Memory align
    2. HarmonyOS工程结构
    【简单易操作】图漾TM460-E2深度网络相机在ROS-melodic环境下的配置过程
    Qt学习总结之QToolButton
    新华三与中国移动完成IPv6随流检测互通测试
    2023年计算机毕设选题推荐
    安装使用electron
    【Java面试】@Resource 和 @Autowired 的区别
  • 原文地址：https://blog.csdn.net/m0_61433144/article/details/126116768