二叉链表（二叉链表存储方式）

本篇文章给大家谈谈二叉链表，以及二叉链表存储方式对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

本文目录一览：

• 1、二叉树的二叉链表结点是什么意思
• 2、二叉链表的头文件怎么写
• 3、二叉链表
• 4、阐述二叉链表和三叉链表的联系与区别?
• 5、二叉链表是什么
• 6、为什么n各节点的的二叉链表中有n+1个空链域

二叉树的二叉链表结点是什么意思

二叉树的二脊和竖叉链表结点是一种表现形式。根据查询显示，二叉链表是树的二叉链表实现方式，链表中结点的两个链域分别指向该结点的第一个子结点和棚猜第二个子结点，二叉树是逻辑结构，二叉链表是二叉树的樱大物理实现，两者之间的关系属于概念和实现，抽象和具体的关系。

[img]

二叉链表的头文件怎么写

问题的描述

1.1基本功能

1、创建二叉树（10’）

可以使用先序遍历输入，无节点的可以使用#表示。

例如下图可以输入6423####51##7##。这里前面2个#表示节点3左右孩子节点都为空，第3个#表示节点2右孩子为空，第4个#表示节点4右孩子为空，1和7后面的2个#分别代表节点1和7的左右孩子节点都为空。

也可以自己选择其他方式输入，但要在readme文件和实验报告说清楚。

2、遍历二叉树（先序、中序、后序、层序遍历）(20’)

前序遍历：6423517

中序遍历：3246157

后序遍历：3241756

层序遍历：6452173

3、二叉树的计算（二叉树的结点数、叶子数、高度、宽度等）(20’)

结点数：7

叶子数：3

高度：4

宽度：3

4、 二叉树的处理（复制、销毁）(20’)

复制要创建一个新的二叉树，对于原二叉树和复制的二叉树之间销毁操作不能互相影响。

1.2健壮性

对于创建的二叉树为空的情况，要能程序要能正常运行并识别。（5分）

对于陵宽空树，其他功能要可以识别、输出相应信息，并且程序不能异常终止。（5分）

1.3 规范性

代码注释

程序模块化

人机交互友好

2.算法的描述

2.1数据结构的描述

程序中应用到的主要数据结构是二叉树（二叉链表）。

主要变量说明：

变量

类型

说明

Node、BiTNode

结构体

二叉树结点的结构体

*BiTree

二叉树结点指针

二叉树结点的指针

data

可变（由宏定义TElemType确定，示例中为char）

二叉树结点中的数据域

*lchild

二叉树结点指针

结点的左孩子

*rchild

二叉树结点指针

结点的右孩子

TElemType

宏定义

二叉树节点数据域的类型

2.2程序结构的描述

程序主要包含Noah_BiTree.h头文件和main.cpp主文件，其中Noah_BiTree.h是二叉链表数据结构的实现代码头文件，N，main.cpp中主要实现菜单和功能界面的交互以及头文件中函数的调用。其具体结构如下图所示。

3.调试分析

调试功能一：Create a binary tree and show the tree structure

创建二叉树并显示树的结构

测试数据选择:

6423####51##7##

124##5##36##7##

#

1234######

问题及解决方法：

无

调试功能二：Create a binary tree and show show the preoeder, inorder, postorder and levelorder

创建一个二叉树，显示前序、中序后序和层次遍历。

测试数据选择:

6423####51##7##

124##5##36##7##

1234######

问题及解决方法：

无

调试功能三：Create a binary tree and calculate the number of nodes, leaves, height and width

创建一个二叉树，计算节点的数量，叶，高度和宽度

测试数尺亏亮据选择:

6423####51##7##

124##5##36##7##

1234######

问题及解决方法：

无

调试功能四：Create a binary tree, copy it, destory the original one and show the new tree

创建一个二叉树，复制它，销毁原来的树，并显示新的树

测试数据选择:

6423####51##7##

124##5##36##7##

1234######

问题及解决方法：

无空巧

4.算法的时空分析

(1) CreateBiTree_withhint(BiTree T)

时间复杂度：O(n)

空间复杂度：O(n)

(2) preorder(BiTree T)

时间复杂度：O(n)

空间复杂度：O(n)

(3) inorder(BiTree T)

时间复杂度：O(n)

空间复杂度：O(n)

(4) postorder(BiTree T)

时间复杂度：O(n)

空间复杂度：O(n)

(5) levelorder(BiTree T)

时间复杂度：O(n)

空间复杂度：O(n)

(6) NumofNode (BiTree T)

时间复杂度：O(n)

空间复杂度：O(n)

(7) BiHight (BiTree T)

时间复杂度：O(n)

空间复杂度：O(n)

(7) Numofleaves (BiTree T)

时间复杂度：O(n)

空间复杂度：O(n)

(7) BiWidth (BiTree T)

时间复杂度：O(n)

空间复杂度：O(n)

(7) CopyBitree (BiTree T)

时间复杂度：O(n)

空间复杂度：O(n)

(7) DestroyBiTree (BiTree T)

时间复杂度：O(n)

空间复杂度：O(n)

5.测试结果及分析

测试功能一：Create a binary tree and show the tree structure

测试用例

结果

分析

6423####51##7##

√

124##5##36##7##

√

#

√

1234######

√

调试功能二：Create a binary tree and show show the preoeder, inorder, postorder and levelorder

测试用例

结果

分析

6423####51##7##

√

124##5##36##7##

√

1234######

√

测试功能三：Create a binary tree and calculate the number of nodes, leaves, height and width

测试用例

结果

分析

6423####51##7##

√

124##5##36##7##

√

1234######

√

调试功能四：Create a binary tree, copy it, destory the original one and show the new tree

测试用例

结果

分析

6423####51##7##

√

124##5##36##7##

√

1234######

√

6.实验体会和收获

掌握二叉树的递归特性

掌握二叉树的常用存储结构----二叉链表

掌握二叉树的创建、遍历等基本运算

了解递归函数的执行过程，学会编写递归程序

代码

Noah_BiTree.h

1. #ifndef __NOAH_BITREE_H__

2. #define __NOAH_BITREE_H__

3. #include stdlib.h

4. #include iostream

5. #include cstring

6. #include queue

7. #include string

8. #include iostream

9. using namespace std;

10. #define TElemType char

11. /*

12. 1. 对于创建的二叉树为空的情况，要能程序要能正常运行并识别。（5分）

13. 2. 对于空树，其他功能要可以识别、输出相应信息，并且程序不能异常终止。（5分）

14. */

15. typedef struct Node

16. {

17. TElemType data;

18. struct Node *lchild,*rchild;//左右孩子指针

19. }BiTNode,*BiTree;

20.

21. void CreateBiTree_Preorder(BiTree T){

22. //使用先序遍历的输入创建一个二叉树，例如6423####51##7##

23. char x;

24. cinx;

25. if(x==' '||x=='#'){

26. T = NULL;

27. }

28. else {

29. T = (BiTree)malloc(sizeof(BiTNode));

30. if(x !='#')

31. T-data = (TElemType)x;

32. CreateBiTree_Preorder(T-lchild);

33. CreateBiTree_Preorder(T-rchild);

34. }

35. }

36.

37. void CreateBiTree_withhint(BiTree T){

38. //向屏幕输出初始化二叉树的提示信息，调用CreateBiTree_Preorder()

39. cout"Please input a preorder sequence of a binary tree(example:6423####51##7##):"endl;

40. CreateBiTree_Preorder(T);

41. if(T==NULL) cout"Input is an empty BiTree."endl;

42. }

43.

44. int isBiTreeEmpty(BiTree T){

45. //判断二叉树是否为空，为空返回1，不为空返回0

46. if((T-data == NULL T-lchild T-rchild)||T==NULL)

47. return 1;

48. else

49. return 0;

50. }

51.

52. void preorder(BiTree T){

53. //使用先序遍历输出二叉树

54. if(T){

55. coutT-data;

56. preorder(T-lchild);

57. preorder(T-rchild);

58. }

59. else

60. return;

61. //cout"Empty BiTree."endl;

62. }

63.

64. void inorder(BiTree T){

65. //使用中序遍历输出二叉树

66. if(T){

67. inorder(T-lchild);

68. coutT-data;

69. inorder(T-rchild);

70. }

71. }

72.

73. void postorder(BiTree T){

74. //使用后序遍历输出二叉树

75. if(T){

76. postorder(T-lchild);

77. postorder(T-rchild);

78. coutT-data;

79. }

80. }

81.

82. void leverorder(BiTree T){

83. //使用层次遍历输出二叉树

84. if(T){

85. queueBiTree q;

86. q.push(T);

87. while(!q.empty()){//当队列非空时，还有没有遍历的parent结点

88. BiTree temp = q.front();

89. q.pop();

90. couttemp-data;

91. if(temp-lchild!=NULL) q.push(temp-lchild);

92. if(temp-rchild!=NULL) q.push(temp-rchild);

93. }

94. }

95. }

96.

97. int NumofNode(BiTree T){

98. //返回二叉树节点数

99. if(!T) return 0;

100. else return 1 + NumofNode(T-lchild) + NumofNode(T-rchild);

101. }

102.

103. int Numofleaves(BiTree T){

104. //返回二叉树叶子数

105. int num = 0;

106. if(!T) return 0;

107. else{

108. if(T-lchild!=NULL) num = num + Numofleaves(T-lchild);

109. if(T-rchild!=NULL) num = num + Numofleaves(T-rchild);

110. if(T-lchild==NULL T-rchild==NULL) return 1;

111. }

112. return num;

113. }

114.

115. int BiHight(BiTree T){

116. //返回二叉树高度

117. if(!T) return 0;

118. else{

119. int lefthight = BiHight(T-lchild);

120. int righthight = BiHight(T-rchild);

121. return (lefthight=righthight)?lefthight+1:righthight+1;

122. }

123. }

124.

125. int BiWidth(BiTree T){

126. //返回二叉树宽度

127. if (isBiTreeEmpty(T)) {

128. return 0;

129. }

130. queueBiTree q;

131. int maxWidth = 1;

132. q.push(T);

133.

134. while (1) {

135. int len = q.size();

136. if (!len) {

137. break;

138. }

139. while (len--) {

140.

141. BiTree temp = q.front();

142. q.pop();

143. if (temp-lchild) {

144. q.push(temp-lchild);

145. }

146. if (temp-rchild) {

147. q.push(temp-rchild);

148. }

149. }

150. maxWidth = max(maxWidth, (int) q.size());

151. }

152. return maxWidth;

153. }

154.

155. void CopyBitree(BiTree source,BiTree target){

156. //将source中的二叉树复制给target，原二叉树和复制的二叉树之间销毁操作不能互相影响

157. if(!source){

158. target = NULL;

159. return;

160. }

161.

162. else{

163. target = (BiTNode *)malloc(sizeof(BiTNode));

164. target-data = (TElemType)source-data;

165. CopyBitree(source-lchild,target-lchild);

166. CopyBitree(source-rchild,target-rchild);

167. }

168. }

169.

170.

171. void DestroyBiTree(BiTree T){

172. //销毁二叉树并释放内存

173. if(isBiTreeEmpty(T)){

174. cout"DestroyBiTree succeed."endl;

175. return;

176. }

177. else{

178. if(T-lchild!=NULL) DestroyBiTree(T-lchild);

179. if(T-rchild!=NULL) DestroyBiTree(T-rchild);

180. free(T);

181. T = NULL;

182. }

183. }

184.

185. void DisplayBitree_control(BiTree n, bool left, string const indent){

186. //DisplayBitree()函数的中间控制函数

187. if (n-rchild)

188. {

189. DisplayBitree_control(n-rchild, false, indent + (left ? "| " : " "));

190. }

191. cout indent;

192. cout (left ? '\\' : '/');

193. cout "-----";

194. cout n-data endl;

195. if (n-lchild)

196. {

197. DisplayBitree_control(n-lchild, true, indent + (left ? " " : "| "));

198. }

199. }

200. void DisplayBitree(BiTree root){

201. //以树形结构形式输出二叉树

202. if(!root){

203. cout"An empty tree."endl;

204. return;

205. }

206. if (root-rchild)

207. {

208. DisplayBitree_control(root-rchild, false, "");

209. }

210. cout root-data endl;

211. if (root-lchild)

212. {

213. DisplayBitree_control(root-lchild, true, "");

214. }

215. }

216. #endif

登录后复制



main.cpp

1. #include stdio.h

2. #include string.h

3. #include stdlib.h

4. #include iostream

5. using namespace std;

6. #include "Noah_BiTree.h"

7. void Menue_gui();

8. void func1();

9. void func2();

10. void func3();

11. void func4();

12.

13. int main()

14. {

15. while(1){

16. Menue_gui();

17. int func;

18. scanf("%d",func);

19. switch(func){

20. case 0:

21. exit(0);

22. case 1:

23. func1();break;

24. case 2:

25. func2();break;

26. case 3:

27. func3();break;

28. case 4:

29. func4();break;

30. default:

31. printf("Input error! Please try again!");

32. }

33. printf("\n");

34. system("pause");

35. }

36. return 0;

37. }

38.

39. //主界面

40. void Menue_gui(){

41. system("cls");

42. printf("**********************************Binary Tree calcuator**************************************\n");

43. printf("*********************************************************************************************\n");

44. printf("Menue:\n");

45. printf("\nExit this program------------------------------------------------------------------0.\n");

46. printf("\nCreate a binary tree and show the tree structure-----------------------------------1.\n");

47. printf("\nCreate a binary tree and show show the preoeder, inorder, postorder and levelorder-2.\n");

48. printf("\nCreate a binary tree and calculate the number of nodes, leaves, height and width---3.\n");

49. printf("\nCreate a binary tree, copy it, destory the original one and show the new tree------4.\n");

50. printf("\n**********************************************************************************************\n");

51. printf("Choose the function you want to use(input number):\n");

52. }

53.

54. void func1(){

55. system("cls");

56. printf("-----ENTER FUNCTION : Create a binary tree and show the tree structure--1.-----\n");

57. BiTree T1;

58. CreateBiTree_withhint(T1);

59. DisplayBitree(T1);

60. }

61. void func2(){

62. system("cls");

63. printf("-----ENTER FUNCTION : Create a binary tree and show show the preoeder, inorder, postorder and levelorder--2.-----\n");

64. BiTree T1;

65. CreateBiTree_withhint(T1);

66. coutendl"The tree form of the Binary Tree is:"endl;

67. DisplayBitree(T1);

68. coutendl"The preorder of the Binary Tree is:"endl;

69. preorder(T1);

70. coutendl"The inorder of the Binary Tree is:"endl;

71. inorder(T1);

72. coutendl"The postorder of the Binary Tree is:"endl;

73. postorder(T1);

74. coutendl"The levelorder of the Binary Tree is:"endl;

75. leverorder(T1);

76. }

77. void func3(){

78. system("cls");

79. printf("-----ENTER FUNCTION : Create a binary tree and calculate the number of nodes, leaves, height and width--3.-----\n");

80. BiTree T1;

81. CreateBiTree_withhint(T1);

82. coutendl"The tree form of the Binary Tree is:"endl;

83. DisplayBitree(T1);

84. coutendl"The number of nodes is:"NumofNode(T1)endl;

85. coutendl"The number of leaves is:"Numofleaves(T1)endl;

86. coutendl"The height is:"BiHight(T1)endl;

87. coutendl"The width is:"BiWidth(T1)endl;

88. }

89. void func4(){

90. system("cls");

91. printf("-----ENTER FUNCTION : Create a binary tree, copy it, destory the original one and show the new tree--4.-----\n");

92. BiTree T1;

93. CreateBiTree_withhint(T1);

94. coutendl"The tree form of the [ORIGINAL] Binary Tree is:"endl;

95. DisplayBitree(T1);

96. BiTree T2;

97. CopyBitree(T1,T2);//复制T1到T2

98. DestroyBiTree(T1);//销毁T1

99. coutendl"After destroy, the tree form of the [ORIGINAL] Binary Tree is:"endl;

100. DisplayBitree(T1);

101. coutendl"The tree form of the [NEW] Binary Tree is:"endl;

102. DisplayBitree(T2);

103. }

登录后复制



关注查看全文



数据结构

链表

算法

细跟高跟凉鞋

精选推荐

广告



二叉链表

这个是分别左右空指针域的个数推断不出来吧，加起来还可以，原因如下：

设二叉树中度为0的结弯贺滚点个数为n0，度为1的结点个数为n1，度为2的结点个数为n2

按照条件n0 = m，于是n2 = m -1，n1= n - n2 = n - m + 1

虽然叶子结点可以保证左右指针域为空，但是度为1的分支呢？到底是左孩子还是右孩子没有办法知道

总的倒是很清楚：n1 + 2n0 = n + m + 1，实际上就是结点个数加1

你还是看看实例吧：

如m= 1, n = 1，则一个叶子一个分支的二叉树形态拍搏就有两种

A

　/

B

A

　\

　 B

前一种情况下左边一个空，右边两个空

后一种情况下左边两个空，右边一个空

至于更多的结点，二叉树的形态就更多了

当然，如果前面加上限制为没有度为1 的分支，这也就是所埋余谓的正规或者正则二叉树，只有度为0的叶子和度为2的分支，此时倒是可以马上得出结论：

左右指针域为空的都是m个或者n+1个

阐述二叉链表和三叉链表的联系与区别?

阐述二叉链表和三叉链表的联系与区别：

1、三叉链表是二叉树的另一种主要的链式存储结构。

2、三叉链表知激岁与二叉链表的主要区别在于，它的结点比二叉链表的结点多一个指针域，该域用于存储一个指向搭睁本结点双亲的指针。铅轮

二叉链表是什么

每个节点都有两个指针域，分别指向两个相同孙族类型的节点，形似树杈一样成扩散式分布。主要用于物渣二则蚂弊叉树的实现。

为什么n各节点的的二叉链表中有n+1个空链域

因为n个节点有2n个指针

又因为n个节点中有n-1条边禅盯

除了头结点没有边，其余节点都有一个父节点，相当于都有1条边，共n-1条

剩下的空链域就是2n-(n-1)=n+1，即n+1个空指针

以二叉链表作为树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。

扩展资料：

typedef　struct CSNode{

ElemType data；

struct CSNode *firstchild ， *netsibling；

} CSNode，* CSTree；

由于二叉树的存储结构比较简单，处理起来也比较方便，所以有时需要把复杂的树，转换为简单的二叉树后再作处理。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中弊袭灶转租扮换。

关于二叉链表和二叉链表存储方式的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。