C++——用二叉链表实现一个二叉树_已知二叉树采用二叉链表结构,编写程序,要求建立一颗二叉树,并输出横向显示的树形

题目：

根据二叉树的抽象数据类型的定义，使用二叉链表实现一个二叉树。
二叉树的基本功能：
1、二叉树的建立
2、前序遍历二叉树
3、中序遍历二叉树
4、后序遍历二叉树
5、按层序遍历二叉树
6、求二叉树的深度
7、求指定结点到根的路径
8、二叉树的销毁
9、其他：自定义操作
编写测试main()函数测试线性表的正确性

关于前序遍历、中序遍历、后序遍历

需求分析：

（1）输入的形式：字符型，且为一字符串，还要输入所求路径的叶结点
（2）输出的形式：也为字符串，即开始建立的二叉树的前序，后序，层序，中序遍历结果，和二叉树深度、所求叶结点的路径。
（3）程序所能达到的功能：分析建立的二叉树，求其前序遍历、中序遍历、层序遍历、后序遍历、深度、所求叶结点路径等。
（4）测试数据：
正确输入：AB#D##C## D
（图示意）

正确输出：
该二叉树的前序遍历为： ABDC
该二叉树的中序遍历为： BDAC
该二叉树的后续遍历为： DBCA
该二叉树的层序遍历为： ABCD
该二叉树的深度为：3
从根结点到该结点的路径为：A->B->D->
错误输入：AB#C##
错误输出：此情况下无输出

（原因：没有建立一个标准合法的二叉树）

详细设计：

Main：
（1）调用Create函数输入并建立一个二叉树；
（2）输入想要路径的结点值；
（3）调用PreOrder、Inorder、PostOrder、LevelOrder函数以输出已建立二叉树的
前序遍历，中序遍历，后序遍历，层序遍历。
（4）调用TreeDepth函数输出该二叉树的深度；
（5）调用Find函数找到所求结点在该二叉树的位置；
（6）调用NodePath函数输出根结点到所求结点的路径；
（7）调用~BiTree函数析构。
（8）完成程序：return 0；
类函数BiTree:
（1）在大括号中写上数据或函数的继承关系（public/private/protected）
（2）写出自定义的函数名或数据名，并在前面标注他们的数据（或返回数据）类型
（3）针对函数，在函数名后添上小括号并写出所需的参数及其类型
Create:
（1）输入一个字符串，若某一字符为“#”，则将该位置的结点设为空；
（2）将该结点的数据域置为该位置的字符，初始化指向父结点的指针为空。
（3）若该结点的左孩子不为空，用递归的形式建立其左孩子，并记下左孩子的父亲，即为该结点。同理对右孩子。
（4）最后return 根结点，此时便建立了一个二叉树。

PreOrder和InOrder/PostOrder都可以用递归的方法输出想要的结果。

LevelOrder：
（1）用队列的方法，初始化空队列，并使根结点入队。
（2）若二叉树没有被遍历完毕，则使队头元素出队并打印，右孩子入队，左孩子入队。
Release：若树不为空，则递归调用释放左子树和右子树。
TreeDepth：
（1）若树为空，直接返回0；
（3）树不为空，递归调用TreeDepth探测左子树和右子树。
（4）输出左右子树深度较大的，加一。
Find：在树不为空的前提下，若该结点的数据域为输入的字符，则返回该结点；否则，递归调用Find函数，遍历查找其左子树和右子树，直到找到该结点。
NodePath：
（1）定义布尔型变量find，用于判断是否找到所求结点。定义栈、工作数组和工作指针。
（2）遍历扫描左子树，存入栈。
（3）若结点未被遍历完，则继续遍历其右子树。
（4）若遍历完了该结点，则将该结点处的数组值定义为1.
（5）若找到了目标结点，则通过栈显示从根结点到该处的路径。

用户使用说明：

按照从左子树开始接收数据的方式输入。

测试结果：

输入:ABD##E##CF##G## E
输出：
该二叉树的前序遍历为：
ABDECFG
该二叉树的中序遍历为：
DBEAFCG
该二叉树的后续遍历为：
DEBFGCA
该二叉树的层序遍历为：
ABCDEFG
该二叉树的深度为：3
从根结点到该结点的路径为：A->B->E->

主程序部分：

/* 根据二叉树的抽象数据类型的定义，使用二叉链表实现一个二叉树。
    二叉树的基本功能：
1、二叉树的建立
2、前序遍历二叉树
3、中序遍历二叉树
4、后序遍历二叉树
5、按层序遍历二叉树
6、求二叉树的深度
7、求指定结点到根的路径
8、二叉树的销毁

2018.05.16 created by Cheng Zixin

*/
#include<iostream>
#include<stack>
#include "Tree.h"
using namespace std;
int main()
{
	char m;
	
	/*for (int i = 0; i < n; i++)
	{
		cin >> data[i];
	}*/
	//BiTree<char>BiTree(R);
	BiNode<char>*R=NULL;
	BiNode<char>*p = NULL;
	BiTree<char> myT;
	BiNode<char>*root=myT.Create(R);
	cout << "输出想要路径的结点值：";
	cin >> m;
	cout << "该二叉树的前序遍历为：" << endl;
	myT.PreOrder(root);
	cout << endl;
	cout << "该二叉树的中序遍历为：" << endl;
	myT.InOrder(root);
	cout << endl;
	cout << "该二叉树的后续遍历为：" << endl;
	myT.PostOrder(root);
	cout << endl;
	cout << "该二叉树的层序遍历为：" << endl;
	myT.LevelOrder(root);
	cout << endl;
	cout << "该二叉树的深度为：";cout<<myT.TreeDepth(root);
	cout << endl;
	cout << "从根结点到该结点的路径为：";
	BiNode<char>*target=myT.Find(root,p,m);
	myT.NodePath(root,target);
	cout << endl;
	myT.~BiTree();
	system("pause");
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

头文件部分：

#ifndef TREE_H
#define TREE_H
#include <string>

template<class T>struct BiNode  //二叉链表结点的C++类型描述
{
	char data;
	BiNode<T>*lchild;
	BiNode<T>*rchild,*fa;  //新增一个指向父结点的指针
	
};
//用二叉链表作为存储结构的二叉树完整的C++描述：
template<class T>class BiTree
{
private:
	
	void Release(BiNode<T>*R);  //释放二叉树
public:
	BiNode<T>*root;   //根结点
	//BiTree(BiNode<T>*R);  //构造函数
	BiNode<T>* Create(BiNode<T>*R);  //创建二叉树
	void PreOrder(BiNode<T>*R); //前序遍历
	void InOrder(BiNode<T>*R); //中序遍历
	void PostOrder(BiNode<T>*R); //后序遍历
	void LevelOrder(BiNode<T>*R); //层序遍历
	int TreeDepth(BiNode<T>*R);  //深度
	void NodePath(BiNode<T>*R, BiNode<T>*target); //路径
	BiNode<T>* Find(BiNode<T>*R,BiNode<T>*target,char m);
	~BiTree();     //析构函数
};
//二叉树的创建：以顺序存储结构为输入，采用先建立根结点，再建立左右孩子的方法递归建立二叉链表的二叉树
template<class T>
BiNode<T>* BiTree<T>::Create(BiNode<T>*R)
{  
	char ch;
	cin >> ch;
	if (ch == '#')  R = NULL;
	else {
		R = new BiNode<T>;
		R->data = ch;
		R->fa = NULL;  //初始化指向父结点的指针为空
		R->lchild = Create(R->lchild); //建立左孩子
		if (R->lchild)  //左孩子不为空
			R->lchild->fa = R;  //记下左孩子的父亲
		R->rchild = Create(R->rchild);  //右孩子同理
		if (R->rchild)  R->rchild->fa = R;
	}
	return R;
}
//前序遍历的实现
//1.递归算法
template<class T>
void BiTree<T>::PreOrder(BiNode<T>*R)
{
	if (R != NULL)
	{
		cout << R->data;  //访问结点
		PreOrder(R->lchild);  //遍历左子树
		PreOrder(R->rchild);  //遍历右子树
	}
}
//中序遍历的实现
template<class T>
void BiTree<T>::InOrder(BiNode<T>*R)
{
	if (R != NULL)
	{
		InOrder(R->lchild);  //遍历左子树
		cout << R->data;   //访问结点
		InOrder(R->rchild); //遍历右子树
	}
}
//后序遍历的实现
template<class T>
void BiTree<T>::PostOrder(BiNode<T>*R)
{
	if (R != NULL)
	{
		PostOrder(R->lchild); //遍历左子树
		PostOrder(R->rchild); //遍历右子树
		cout << R->data;  //访问结点
	}
}
//层序遍历的实现(利用队列)
template<class T>
void BiTree<T>::LevelOrder(BiNode<T>*R)
{
	BiNode<T>*queue[100];
	int f = 0, r = 0;   //初始化空队列
	if (R != NULL)  queue[++r] = R;   //根结点入队
	while (f != r)
	{
		BiNode<T>*p = queue[++f];  //队头元素出队
		cout << p->data;    //出队打印
		if (p->lchild != NULL)  queue[++r] = p->lchild; //左孩子入队
		if (p->rchild != NULL)  queue[++r] = p->rchild; //右孩子入队
	}
}
template<class T>
inline BiTree<T>::~BiTree()
{
	Release(root);
}
//析构函数的实现
template<class T>
void BiTree<T>::Release(BiNode<T>*R)  //释放二叉树
{
	if (R != NULL)
	{
		Release(R->lchild);  //释放左子树
		Release(R->rchild);  //释放右子树
		delete R;   //释放根结点
	}
}
//用递归的方法测试二叉树的深度
/*如果一棵树只有一个结点，那么它的深度为1；
如果根结点只有左子树没有右子树，那么树的深度是左子树的深度加1，加1是加上根节点这一层
如果既有左子树又有右子树，那么树的深度应该是左、右子树中深度较大的值再加1*/
template<class T>int BiTree<T>::TreeDepth(BiNode<T>*R)
{
	if (R == NULL)  return 0;
	int nleft = TreeDepth(R->lchild);
	int nright = TreeDepth(R->rchild);
	return (nleft > nright) ? (nleft + 1) : (nright + 1);
}
template<class T>void BiTree<T>::NodePath(BiNode<T>*R,BiNode<T>*p)  //路径
{
	typedef enum {FALSE,TRUE} booler;
	BiNode<T>*stack[20];  //定义栈
	int tag[20];
	int i, top;
	booler find;  //判断是否找到了该路径
	BiNode<T>*s;
	find = FALSE;
	top = 0;
	s = R;
	do
	{
		while (s != NULL)
		{//扫描左子树
			top++;
			stack[top] = s;
			tag[top] = 0;
			s = s->lchild;
		}
		if (top > 0)
		{
			s = stack[top];
			if (tag[top] == 1)
			{
				if (s == p)
				{//找到了目标结点，则显示从根结点到target的路径
					for (i = 1; i <= top; i++)
						cout << stack[i]->data << "->";
					find = TRUE;
				}
				else  top--;
				s = stack[top];
			}
			if (top > 0 && !find)
			{
				if (tag[top] != 1)
				{
					s = s->rchild;//扫描右子树
					tag[top] = 1;
				}
				else s = NULL;
			}
		}
	} while (!find&&top != 0);
}
template<class T>
BiNode<T>* BiTree<T>::Find(BiNode<T>* R,BiNode<T>*p, char m)
{
	if (R != NULL)
	{
		if (R->data == m) { p= R; }
		else {
			p=Find(R->lchild,p,m); //遍历查找左子树
			p=Find(R->rchild,p,m); //遍历查找右子树
		}
	}
	return p;
}
#endif

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186

2021.6.7更新：
因为有好多学弟学妹私信我说想要头文件部分的代码，我最近就重新看了一下，源代码其实已经都在博客里了（之前的排版有点问题，没有在博客里细分出来main函数和tree.h头文件），说明大家还是没有认真看，这个题目其实不是很难，只要沉下心钻研钻研，都能看透的，更何况已经有源代码了。
这次更新主要是加了两张图，说明遍历算法的区别，以及需求分析中测试输入所建立的树长什么样子。