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

数据结构--树形结构之二叉树--C语言_设树的结点为char类型,请用左孩子右兄弟表示法建树,并完成遍历等操作。 1,以二元

作者：Monodyee | 2024-06-01 00:05:32

赞

踩

设树的结点为char类型,请用左孩子右兄弟表示法建树,并完成遍历等操作。 1,以二元

目录

一、树和二叉树

1.树的概念

 2.二叉树的概念

 二、二叉树的存储结构

1.二叉树的顺序存储结构

2.二叉树的链式存储

三、二叉树的遍历

1.前序遍历：

2.中序遍历

3.后序遍历

一、树和二叉树

1.树的概念

结点的度：一个结点含有子结点的个数，称为结点的度。如A点的度为6.

叶子节点/终端结点：度为零的结点，也就是没有子结点的结点，如B\C\H\I等结点。

分支结点/非终端节点：度不为零的结点，如D,E,F,G,J。

双亲节点或父节点：若一个节点有子节点，则称这个节点为其子节点的父节点或者双亲节点。

兄弟节点：有相同父节点的节点称为兄弟节点，如图B，C是兄弟节点。

树的度：一棵树中最大的结点的度称为树的度。如图，该树的度为6.

树的高度/层次：树中节点的层次，如图：树的高度为4.

节点的祖先：从根到该节点上的所有节点，如A是所有节点的祖先。

森林：多颗不相交的树叫森林，并查集就是一个森林。

左孩子右兄弟表示方法：

双亲表示法：

树的主要运用于文件目录

 2.二叉树的概念

二叉树是度不超过2的树，有左右之分，不可颠倒，如下图：

完全二叉树和非完全二叉树：

完全二叉树是所有节点按照从左到右依次标号而成的，如图：

 二、二叉树的存储结构

1.二叉树的顺序存储结构

顺序存储结构只适用于完全二叉树，因此，想将顺序存储普通二叉树，必须先将其转化为完全二叉树。

例如下图：

 其顺序存储如下图：

2.二叉树的链式存储

由于顺序存储方式要将普通二叉树转换成完全二叉树，会浪费很多空间，所以链式存储会更适合于二叉树的存储。

 链式节点构成：

Lchild:指向左孩子的指针；

Rchild:指向右孩子的指针；

data:节点的数据域；

节点定义：

  1. typedef struct BinTreeNode
  2. {
  3. 	TreeValType data;//数据域
  4. 	struct BinTreeNode *lchild, *rchlid;//左右孩子
  5. 	struct BinTreeNode *parent;
  6. }BTNode,*BiTree;

创建二叉树：

  1. void CreateBinTree(BinTree *t)
  2. {
  3. 	*t = (BinTree*)malloc(sizeof(BinTree));
  4. 	(*t)->data = 1;
  5. 	(*t)->lchild = (BinTree*)malloc(sizeof(BinTree));
  6. 	(*t)->lchild->data = 2;
  7. 	(*t)->rchild = (BinTree*)malloc(sizeof(BinTree));
  8. 	(*t)->rchild->data = 3;
  9. 	(*t)->rchild->lchild = NULL;
  10. 	(*t)->rchild->rchild = NULL;
  11. 	(*t)->lchild->lchild = (BinTree*)malloc(sizeof(BinTree));
  12. 	(*t)->lchild->rchild = (BinTree*)malloc(sizeof(BinTree));
  13. 	(*t)->lchild->lchild->data = 4;
  14. 	(*t)->lchild->rchild->data = 5;
  15. 	(*t)->lchild->lchild->lchild = NULL;
  16. 	(*t)->lchild->lchild->rchild = NULL;
  17. 	(*t)->lchild->rchild->rchild = NULL;
  18. 	(*t)->lchild->rchild->lchild = NULL;
  19. }
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #define TreeValType int
  4.  
  5. typedef struct BinTreeNode
  6. {
  7. 	TreeValType data;//数据域
  8. 	struct BinTreeNode *lchild, *rchild;//左右孩子
  9. 	struct BinTreeNode *parent;
  10. }BTNode,*BinTree;
  11.  
  12. void CreateBinTree(BinTree *t)
  13. {
  14. 	*t = (BinTree*)malloc(sizeof(BinTree));
  15. 	(*t)->data = 1;
  16. 	(*t)->lchild = (BinTree*)malloc(sizeof(BinTree));
  17. 	(*t)->lchild->data = 2;
  18. 	(*t)->rchild = (BinTree*)malloc(sizeof(BinTree));
  19. 	(*t)->rchild->data = 3;
  20. 	(*t)->rchild->lchild = NULL;
  21. 	(*t)->rchild->rchild = NULL;
  22. 	(*t)->lchild->lchild = (BinTree*)malloc(sizeof(BinTree));
  23. 	(*t)->lchild->rchild = (BinTree*)malloc(sizeof(BinTree));
  24. 	(*t)->lchild->lchild->data = 4;
  25. 	(*t)->lchild->rchild->data = 5;
  26. 	(*t)->lchild->lchild->lchild = NULL;
  27. 	(*t)->lchild->lchild->rchild = NULL;
  28. 	(*t)->lchild->rchild->rchild = NULL;
  29. 	(*t)->lchild->rchild->lchild = NULL;
  30. }
  31.  
  32. int main()
  33. {
  34. 	BinTree Tree;
  35. 	CreateBinTree(&Tree);
  36. 	printf("%d\n", Tree->lchild->rchild->data);
  37. 	getchar();
  38. 	return 0;
  39. }

运行结果：

三、二叉树的遍历

二叉树的基本遍历方法如下：

1.前序遍历：

先遍历根，再遍历左子树，在遍历右子树：

 先序遍历采用的是递归的思想：

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #define TreeValType int
  4.  
  5. typedef struct BinTreeNode
  6. {
  7. 	TreeValType data;//数据域
  8. 	struct BinTreeNode *lchild, *rchild;//左右孩子
  9. 	struct BinTreeNode *parent;
  10. }BTNode,*BinTree;
  11.  
  12. void CreateBinTree(BinTree *t)//创建二叉树
  13. {
  14. 	*t = (BinTree*)malloc(sizeof(BinTree));
  15. 	(*t)->data = 1;
  16. 	(*t)->lchild = (BinTree*)malloc(sizeof(BinTree));
  17. 	(*t)->lchild->data = 2;
  18. 	(*t)->rchild = (BinTree*)malloc(sizeof(BinTree));
  19. 	(*t)->rchild->data = 3;
  20. 	(*t)->rchild->lchild = (BinTree*)malloc(sizeof(BinTree));
  21. 	(*t)->rchild->rchild = (BinTree*)malloc(sizeof(BinTree));
  22. 	(*t)->lchild->lchild = (BinTree*)malloc(sizeof(BinTree));
  23. 	(*t)->lchild->rchild = (BinTree*)malloc(sizeof(BinTree));
  24. 	(*t)->lchild->lchild->data = 4;
  25. 	(*t)->lchild->rchild->data = 5;
  26. 	(*t)->rchild->rchild->data = 7;
  27. 	(*t)->rchild->lchild->data = 6;
  28. 	(*t)->lchild->lchild->lchild = NULL;
  29. 	(*t)->lchild->lchild->rchild = NULL;
  30. 	(*t)->lchild->rchild->rchild = NULL;
  31. 	(*t)->lchild->rchild->lchild = NULL;
  32. 	(*t)->rchild->lchild->lchild = NULL;
  33. 	(*t)->rchild->lchild->rchild = NULL;
  34. 	(*t)->rchild->rchild->rchild = NULL;
  35. 	(*t)->rchild->rchild->lchild = NULL;
  36. }
  37.  
  38. void displayVal(BTNode * Val)
  39. {
  40. 	
  41. 	printf("%d", Val->data);
  42. }
  43.  
  44. //先序遍历二叉树
  45. void PreOrderTraverse(BinTree t)
  46. {
  47. 	if (t != NULL)
  48. 	{
  49. 		displayVal(t);
  50. 		PreOrderTraverse(t->lchild);//访问左孩子
  51. 		PreOrderTraverse(t->rchild);//访问右孩子
  52. 	}
  53. 	return;
  54. }
  55.  
  56. int main()
  57. {
  58. 	BinTree Tree;
  59. 	CreateBinTree(&Tree);
  60. 	printf("先序遍历：\n");
  61. 	PreOrderTraverse(Tree);
  62. 	getchar();
  63. 	return 0;
  64. }

运行结果：

递归的底层是栈的存取结构思想，故二叉树的先序遍历既可以直接采用递归思想实现，也可以使用栈的存储结构模拟递归的思想实现

非递归实现：

非递归的基本思路：使用堆栈

遇到一个结点，就访问它，并去遍历它的右子树；

如果有右孩子，压栈;

然后先序再去遍历它的左孩子。

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<string.h>
  4.  
  5. #define TreeValType int
  6. int top = -1;//初始栈顶元素所在位置
  7.  
  8. //构造节点结构体
  9. typedef struct BinTreeNode
  10. {
  11. 	TreeValType data;
  12. 	struct BinTreeNode * lchild, *rchild;
  13. }BTNode,*BTree;
  14.  
  15. //初始化树的函数
  16. void CreateBinTree(BTree *t)
  17. {
  18. 	*t = (BTree*)malloc(sizeof(BTree));
  19. 	(*t)->data = 1;
  20. 	(*t)->lchild = (BTree*)malloc(sizeof(BTree));
  21. 	(*t)->rchild = (BTree*)malloc(sizeof(BTree));
  22. 	(*t)->lchild->data = 2;
  23. 	(*t)->rchild->data = 3;
  24. 	(*t)->lchild->lchild = (BTree*)malloc(sizeof(BTree));
  25. 	(*t)->lchild->rchild = (BTree*)malloc(sizeof(BTree));
  26. 	(*t)->lchild->lchild->data = 4;
  27. 	(*t)->lchild->rchild->data = 5;
  28. 	(*t)->rchild->lchild = (BTree*)malloc(sizeof(BTree));
  29. 	(*t)->rchild->rchild = (BTree*)malloc(sizeof(BTree));
  30. 	(*t)->rchild->lchild->data = 6;
  31. 	(*t)->rchild->rchild->data = 7;
  32. 	(*t)->lchild->lchild->lchild = NULL;
  33. 	(*t)->lchild->lchild->rchild = NULL;
  34. 	(*t)->lchild->rchild->lchild = NULL;
  35. 	(*t)->lchild->rchild->rchild = NULL;
  36. 	(*t)->rchild->lchild->lchild = NULL;
  37. 	(*t)->rchild->lchild->rchild = NULL;
  38. 	(*t)->rchild->rchild->lchild = NULL;
  39. 	(*t)->rchild->rchild->rchild = NULL;
  40. }
  41. //前序遍历使用的进栈函数
  42. void push(BTree** a, BTNode* Val)
  43. {
  44. 	a[++top] = Val;
  45. }
  46.  
  47. //出栈函数
  48. void pop()
  49. {
  50. 	if (top ==-1)
  51. 	{
  52. 		return;
  53. 	}
  54. 	top--;
  55. }
  56.  
  57. void displayVal(BTNode* Val)
  58. {
  59. 	printf("%d",Val->data);
  60. }
  61.  
  62. //获取栈顶元素
  63. BTNode* gettop(BTNode**a)
  64. {
  65. 	return a[top];
  66. }
  67. //先序遍历非递归算法
  68. 	void preOrderTraverse(BTree tree)
  69. 	{
  70. 		BTNode* a[20];//定义顺序栈
  71. 		BTNode* p;//定义临时指针
  72. 		push(a, tree);
  73. 		while (top != -1)
  74. 		{
  75. 			p = gettop(a);//取栈顶元素
  76. 			pop();//弹栈
  77. 			while (p)
  78. 			{
  79. 				displayVal(p);
  80. 				//如果结点有右孩子，右孩子进栈
  81. 				if (p->rchild)
  82. 				{
  83. 					push(a, p->rchild);
  84. 				}
  85. 				p = p->lchild;//一直指向根节点的最后一个左孩子
  86. 			}
  87. 		}
  88. 	}
  89. 	int main()
  90. 	{
  91. 		BTree tree;
  92. 		CreateBinTree(&tree);
  93. 		printf("先序遍历：\n");
  94. 		preOrderTraverse(tree);
  95. 		getchar();
  96. 		return 0;
  97. 	}

运行结果：

与前面运行结果一致。

2.中序遍历

中序遍历：左子树，根节点，右子树

 递归实现：

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #define TreeValType int
  4.  
  5. typedef struct BinTreeNode
  6. {
  7. 	TreeValType data;
  8. 	struct BinTreeNode * lchild, *rchild;
  9. }BTNode,*BinTree;
  10.  
  11. void CreateBinTree(BinTree *t)
  12. {
  13. 	*t = (BinTree*)malloc(sizeof(BinTree));
  14. 	(*t)->data = 1;
  15. 	(*t)->rchild = (BinTree*)malloc(sizeof(BinTree));
  16. 	(*t)->lchild = (BinTree*)malloc(sizeof(BinTree));
  17. 	(*t)->lchild->data = 2;
  18. 	(*t)->rchild->data = 3;
  19. 	(*t)->rchild->lchild= (BinTree*)malloc(sizeof(BinTree));
  20. 	(*t)->rchild->rchild = (BinTree*)malloc(sizeof(BinTree));
  21. 	(*t)->lchild->lchild = (BinTree*)malloc(sizeof(BinTree));
  22. 	(*t)->lchild->rchild = (BinTree*)malloc(sizeof(BinTree));
  23. 	(*t)->lchild->lchild->data = 4;
  24. 	(*t)->lchild->rchild->data = 5;
  25. 	(*t)->rchild->lchild ->data = 6;
  26. 	(*t)->rchild->rchild->data = 7;
  27. 	(*t)->lchild->lchild->lchild = NULL;
  28. 	(*t)->lchild->lchild->rchild = NULL;
  29. 	(*t)->lchild->rchild->lchild = NULL;
  30. 	(*t)->lchild->rchild->rchild = NULL;
  31. 	(*t)->rchild->lchild->lchild = NULL;
  32. 	(*t)->rchild->lchild->rchild = NULL;
  33. 	(*t)->rchild->rchild->lchild = NULL;
  34. 	(*t)->rchild->rchild->rchild = NULL;
  35. }
  36.  
  37. //输出节点本身的值
  38. void displayVal(BTNode * Val)
  39. {
  40. 	printf("%d", Val->data);
  41. }
  42.  
  43. //中序遍历
  44. void MidOrderTraverse(BinTree t)
  45. {
  46. 	if (t != 0)
  47. 	{
  48. 		MidOrderTraverse(t->lchild);//遍历左孩子
  49. 		displayVal(t);
  50. 		MidOrderTraverse(t->rchild);
  51. 	}
  52. 	//节点为空，返回上一层
  53. 	return;
  54. }
  55.  
  56. int main()
  57. {
  58. 	BinTree tree;
  59. 	CreateBinTree(&tree);
  60. 	printf("中序遍历：\n");
  61. 	MidOrderTraverse(tree);
  62. 	getchar();
  63. }

运行结果：

3.后序遍历

后序遍历：左右根；

  1. #include <stdio.h>
  2. #include <string.h>
  3. #include<stdlib.h>
  4. #define TreevaleType int
  5. //构造结点的结构体
  6. typedef struct BiTNode{
  7. 	TreevaleType data;//数据域
  8. 	struct BiTNode *lchild, *rchild;//左右孩子指针
  9. }BiTNode, *BiTree;
  10. //初始化树的函数
  11. void CreateBiTree(BiTree *T){
  12. 	*T = (BiTNode*)malloc(sizeof(BiTNode));
  13. 	(*T)->data = 1;
  14. 	(*T)->lchild = (BiTNode*)malloc(sizeof(BiTNode));
  15. 	(*T)->rchild = (BiTNode*)malloc(sizeof(BiTNode));
  16.  
  17. 	(*T)->lchild->data = 2;
  18. 	(*T)->lchild->lchild = (BiTNode*)malloc(sizeof(BiTNode));
  19. 	(*T)->lchild->rchild = (BiTNode*)malloc(sizeof(BiTNode));
  20. 	(*T)->lchild->rchild->data = 5;
  21. 	(*T)->lchild->rchild->lchild = NULL;
  22. 	(*T)->lchild->rchild->rchild = NULL;
  23. 	(*T)->rchild->data = 3;
  24. 	(*T)->rchild->lchild = (BiTNode*)malloc(sizeof(BiTNode));
  25. 	(*T)->rchild->lchild->data = 6;
  26. 	(*T)->rchild->lchild->lchild = NULL;
  27. 	(*T)->rchild->lchild->rchild = NULL;
  28. 	(*T)->rchild->rchild = (BiTNode*)malloc(sizeof(BiTNode));
  29. 	(*T)->rchild->rchild->data = 7;
  30. 	(*T)->rchild->rchild->lchild = NULL;
  31. 	(*T)->rchild->rchild->rchild = NULL;
  32. 	(*T)->lchild->lchild->data = 4;
  33. 	(*T)->lchild->lchild->lchild = NULL;
  34. 	(*T)->lchild->lchild->rchild = NULL;
  35. }
  36.  
  37. //模拟操作结点元素的函数，输出结点本身的数值
  38. void displayVale(BiTNode* vale){
  39. 	printf("%d ", vale->data);
  40. }
  41. //后序遍历
  42. void LastOrderTraverse(BiTree T){
  43. 	if (T) {
  44. 		LastOrderTraverse(T->lchild);//遍历左孩子
  45. 		LastOrderTraverse(T->rchild);//遍历右孩子
  46. 		displayVale(T);//调用操作结点数据的函数方法
  47. 	}
  48. 	//如果结点为空，返回上一层
  49. 	return;
  50. }
  51. int main() {
  52. 	BiTree Tree;
  53. 	CreateBiTree(&Tree);
  54. 	printf("后序遍历: \n");
  55. 	LastOrderTraverse(Tree);
  56. 	getchar();
  57. }

运行结果：

与手工迭代一致。 

参考：二叉树后序遍历（递归与非递归）算法及C语言实现 (biancheng.net)

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

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

  

闽ICP备14008679号