二叉链表的头文件怎么写

问题的描述

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. cin>>x

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. cout<<T->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. cout<<T->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. cout<<T->data

79. }

80. }

81.

82. void leverorder(BiTree T){

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

84. if(T){

85. queue<BiTree>q

86. q.push(T)

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

88. BiTree temp = q.front()

89. q.pop()

90. cout<<temp->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. queue<BiTree>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. cout<<endl<<"The tree form of the Binary Tree is:"<<endl

67. DisplayBitree(T1)

68. cout<<endl<<"The preorder of the Binary Tree is:"<<endl

69. preorder(T1)

70. cout<<endl<<"The inorder of the Binary Tree is:"<<endl

71. inorder(T1)

72. cout<<endl<<"The postorder of the Binary Tree is:"<<endl

73. postorder(T1)

74. cout<<endl<<"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. cout<<endl<<"The tree form of the Binary Tree is:"<<endl

83. DisplayBitree(T1)

84. cout<<endl<<"The number of nodes is:"<<NumofNode(T1)<<endl

85. cout<<endl<<"The number of leaves is:"<<Numofleaves(T1)<<endl

86. cout<<endl<<"The height is:"<<BiHight(T1)<<endl

87. cout<<endl<<"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. cout<<endl<<"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. cout<<endl<<"After destroy, the tree form of the [ORIGINAL] Binary Tree is:"<<endl

100. DisplayBitree(T1)

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

102. DisplayBitree(T2)

103. }

登录后复制

关注查看全文

数据结构

链表

算法

细跟高跟凉鞋

精选推荐

广告

2 代码： 1 ）二叉排序树： #include"BSTreeNode.h" #include"seqstack.h" #define Max(x1,x2) (x1>x2?x1:x2) //返回两个数中的最大者 #include using namespace stdtemplate class BSTree { private: //void destory(BSTreeNode *p)//删除以p为根的二叉树 void InOrder(BSTreeNode *r)//私有函数：此算法按照中序次序遍历二叉树 void PostOrder(BSTreeNode *r)//私有函数：此算法按照后序次序遍历二叉树 int Depth(const BSTreeNode *r)//私有函数：此算法计算二叉树的深度 int LeafSize(const BSTreeNode *r)//私有函数：此算法计算二叉树的叶子结晌烂点个数 //宴宴漏void CreatPreThreed(BSTreeNode *&r)BSTreeNode*Find(const Type &k,BSTreeNode*p)constvoid Insert(const Type &x,BSTreeNode*&p)void Delete(const Type &k,BSTreeNode*&p)BSTreeNode*&Min(BSTreeNode*&p)BSTreeNode *rootpublic: BSTree():root(NULL){} BSTreeNode *Root(){return root} int Depth()//计算二叉树的深度 int LeafSize()//计算二叉树的叶子结点个数 void PreOrder()//用栈先序遍历二叉树 void CreatPreThreed(){CreatPreThreed(root)} void InOrder()void PostOrder()BSTreeNode *Find(const Type &k)const{return Find(k,root)} //BSTreeNode*&Min(){Min(BSTreeNode*&p)}//Type Max()void Insret(const Type &x){Insert(x,root)} void Delete(const Type &k){Delete(k,root)} void CreatBSTree()}template void BSTree::InOrder(BSTreeNode *r) { if(r!=NULL) { InOrder(r->GetLeftChild())cout<GetData()<GetRightChild())} } template void BSTree::PostOrder(BSTreeNode*r) { if(r!=NULL) { PostOrder(r->GetLeftChild())PostOrder(r->GetRightChild())cout<GetData()</递归结束条件：空树叶子结点个数为 else if(t->leftChild == NULL &&t->rightChild == NULL) return 1else return LeafSize(t->leftChild)+LeafSize(t->rightChild)} template int BSTree::Depth() { return Depth(root)} template int BSTree::Depth(const BSTreeNode* t) { if(t==NULL) return 0/祥凯/递归结束条件：空树深度为 return 1+Max(Depth(t->leftChild),Depth(t->rightChild))} template void BSTree::PreOrder() { seqstack *>s(50)if(root==NULL) cout<<"二叉树为空！"<data<GetLeftChild()do { if(p!=NULL) { cout<GetData()<GetLeftChild()} else if(s.empty()!=1) { p=s.pop()p=p->GetRightChild()} }while(s.empty()!=1||p!=NULL)} /*template void BSTree::CreatPreThreed(BSTreeNode *&r) { Type chcin>>chif(ch=='#')returnr=new BinTreeNode(ch,NULL,NULL)CreatPreThreed(r->leftChild)CreatPreThreed(r->rightChild)}*/ template void BSTree::InOrder() { InOrder(root)} template void BSTree::PostOrder() { PostOrder(root)}/* template BSTreeNode* BSTree::Find(const Type &k,BSTree*p)const { if(p==NULL) return NULLelse if（kdata） return Find(k,p->leftChild)else if(k>p->data) return Find(k,p->rightChild)else return p}*/ template BSTreeNode *BSTree::Find(const Type &k,BSTreeNode*p)const//在p为根的二叉排序树上进行查找的迭代算法 { BSTreeNode*temp=pif(p!=NULL) { while(temp!=NULL) { if(temp->data==k) return temp//查找成功 if(temp->datarightChild//查找右子树 else temp=temp->leftChild//查找左子树 } } return temp//查找失败 } template void BSTree::Insert(const Type &x,BSTreeNode*&p)//在p为根的二叉排序树上插入结点的递归算法 { if(p==NULL)//空二叉树 p=new BSTreeNode(x)//创建数据元素x的结点 else if(xdata) Insert(x,p->leftChild)//在左子树插入 else if(x>p->data) Insert(x,p->rightChild)//在右子树插入 else //结点x存在 { cout<<"已经存在该节点插入失败"leftChild)//若p的关键字大于k，则在p的左子树删除 else if(k>p->data) //delete(k,p->rightChild)Delete(k,p->rightChild)//若p的关键字小于k，则在p的右子树删除 else if(p->leftChild!=NULL&&p->rightChild!=NULL) { /* temp=Min(p->rightChild)p->data=temp->datadelete(p->data,temp)*/ BSTreeNode *&temp1=Min(p->rightChild)p->data=temp1->dataDelete(p->data,temp1)//注意这里和你原来的比较是Delete而非delete } else { temp=pif(p->leftChild==NULL) p=p->rightChildelse if(p->rightChild==NULL) p=p->leftChilddelete temp} } templatevoid BSTree::CreatBSTree() { int i(0)cout<<'\n'Type chwhile(ch!=-1) { cout<<"第">chif(ch!=-1) { Insert(ch,root)i++} else break} } //template templateBSTreeNode*&BSTree::Min(BSTreeNode *&p) { /* BSTreeNode*&qwhile(p!=NULL) { q=pp=p->GetLeftChild()} */ while (p->leftChild!=NULL) p=p->leftChildreturn p}

---