数据结构实验：C++实现二叉树的建立与遍历(先、中、后序，层次)_二叉树的创建先序,中序,后序遍历cpp

数据结构实验三：二叉树的建立与遍历

---

1. 实验内容

运用先序遍历的顺序建立二叉树,
对二叉树进行先序、中序、后序(包括递归与非递归)和层次遍历
1
2

2.二叉树结点类与二叉树类

template<typename ElemType>
class treeNode {
public:
	ElemType data;
	treeNode* lchild, * rchild;  //树左右孩子结点
	treeNode() :data(0), lchild(NULL), rchild(NULL) {};
	treeNode(ElemType _data):data(_data), lchild(NULL), rchild(NULL) {};  //构造函数
	~treeNode() {};
};

class binaryTree {
public:
	treeNode<char>* root; //树根结点
	binaryTree() :root(NULL) {};
	void preorderCreate(string s);//先序建立二叉树
	treeNode<char>* preorderCreateTree(treeNode<char>* T,string s);//递归先序创建二叉树函数
	void preOrder(treeNode<char>* T);//递归先序遍历
	void _preOrder(treeNode<char>* T);//非递归先序遍历
	void inOrder(treeNode<char>* T);//递归中序遍历
	void _inOrder(treeNode<char>* T);//非递归中序遍历
	void postOrder(treeNode<char>* T);//递归后序遍历
	void _postOrder(treeNode<char>* T);//非递归后序遍历
	void levelOrder(treeNode<char>* T);//层次遍历
	~binaryTree() {};
}
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

3.二叉树的先序建立与实现遍历(先序、中序、后序、层次)

//先序建立二叉树
int p;
void binaryTree::preorderCreate(string s) {
	p = -1;
	root = preorderCreateTree(root,s);
}
//递归先序创建二叉树函数
treeNode<char>* binaryTree::preorderCreateTree(treeNode<char>* T, string s) {
	p++;
	if (s[p] == '#')
		T = NULL;
	else {
		T = new treeNode<char>;
		T->data = s[p];
		T->lchild = preorderCreateTree(T->lchild,s);
		T->rchild = preorderCreateTree(T->rchild, s);
	}
	return T;
}

//递归先序遍历二叉树
void binaryTree::preOrder(treeNode<char>* T) {
	if (T != NULL) {
		cout << T->data;
		preOrder(T->lchild);
		preOrder(T->rchild);
	}
}

//非递归先序遍历二叉树，与非递归中序遍历类似，只是把访问结点的操作放在入栈前面
void binaryTree::_preOrder(treeNode<char>* T) {
	myStack<treeNode<char>*>mStack;
	treeNode<char>* tNode;  //遍历指针
	mStack.initStack();  //初始化栈
	tNode = T;  //开始时指向根结点
	while (tNode || !mStack.isEmpty()) {
		if (tNode) {
			cout << tNode->data;  //访问结点
			mStack.push(tNode);
			tNode = tNode->lchild;  //访问当前结点，并入栈，左孩子不空一直向左走
		}
		else {
			mStack.pop(tNode);
			tNode = tNode->rchild;  //若为空则弹出栈顶结点并指向右孩子结点
		}
	}
}

//递归中序遍历
void binaryTree::inOrder(treeNode<char>* T) {
	if (T != NULL) {
		inOrder(T->lchild);
		cout << T->data;
		inOrder(T->rchild);
	}
}

//非递归中序遍历
void binaryTree::_inOrder(treeNode<char>* T) {
	myStack<treeNode<char>*>mStack;
	treeNode<char>* tNode;  //遍历指针
	mStack.initStack();  //初始化栈
	tNode = T;  //开始时指向根结点
	while (tNode || !mStack.isEmpty()) {
		if (tNode) {
			mStack.push(tNode);
			tNode = tNode->lchild;//沿着根的左孩子，依次入栈，直至左孩子为空，找到可以输出的结点
		}
		else {
			mStack.pop(tNode);  //栈顶元素出栈访问
			cout << tNode->data;
			tNode = tNode->rchild;  //左孩子遍历完转到右子树
		}
	}
}

//递归后续遍历二叉树
void binaryTree::postOrder(treeNode<char>* T) {
	if (T != NULL) {
		postOrder(T->lchild);
		postOrder(T->rchild);
		cout << T->data;
	}
}

//非递归后续遍历二叉树
void binaryTree::_postOrder(treeNode<char>* T) {
	myStack<treeNode<char>*>mStack;
	treeNode<char>* tNode;  //遍历指针
	mStack.initStack();  //初始化栈
	tNode = T;  //开始时指向根结点
	treeNode<char>* r;//设置一个辅助指针，指向最近访问过的结点以分清返回时是从左子树还是右子树返回的
	r = NULL;
	while (tNode || !mStack.isEmpty()) {
		if (tNode) {
			mStack.push(tNode);
			tNode = tNode->lchild;
		}
		else
		{
			tNode=mStack.getTop();
			if (tNode->rchild && tNode->rchild != r)
				tNode = tNode->rchild;
			else
			{
				mStack.pop(tNode);
				cout << tNode->data;
				r = tNode;  //记录最近访问过的结点
				tNode = NULL;  //结点访问结束，重置TNode指针
			}
		}
	}
}

//层次遍历
//类似于BFS算法，借助一个队列，将根节点入队，然后将其出队，访问它，若它有左子树，则将左子树根节点入队，若有
//右子树，则把左子树根节点入队。然后出队，访问出队结点……直到队列为空
void binaryTree::levelOrder(treeNode<char>* T) {
	myQueue<treeNode<char>*>mQueue;
	treeNode<char>* tNode;  //遍历指针
	mQueue.initQueue();  //初始化栈
	mQueue.enQueue(T);  //根结点入队
	tNode = T;
	while (!mQueue.isEmpty()) {  //当队列不为空就一直循环
		mQueue.deQueue(tNode);
		cout << tNode->data;
		if (tNode->lchild != NULL)
			mQueue.enQueue(tNode->lchild);  //左子树不空，则将左子树根节点入队
		if (tNode->rchild != NULL)
			mQueue.enQueue(tNode->rchild);
	}
}
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

4.自定义栈与队列

自定义队列：

#pragma once
#ifndef myqueue_H
#define myqueuq_H
const int MAXSIZE = 100;
template<class ElemType>
class myQueue {
private:
	ElemType* base;
	int front;
	int rear;
public:
	bool initQueue();  //初始化
	bool enQueue(ElemType e);  //入队
	bool deQueue(ElemType& e);  //出队
	bool isEmpty();  //判断是否为空队列
	int length();  //求队列长度
	ElemType getFront();  //获取队列首元素
};

template<class ElemType>
inline bool myQueue<ElemType>::initQueue() {
	base = new ElemType[MAXSIZE];
	if (!base)
		return false;
	front = rear = 0;
	return true;
}
template<class ElemType>
inline bool myQueue<ElemType>::enQueue(ElemType e) {
	if ((rear + 1) % MAXSIZE == front)
		return false;
	base[rear] = e;
	rear = (rear + 1) % MAXSIZE;
	return true;
}

template<class ElemType>
inline bool myQueue<ElemType>::deQueue(ElemType& e) {
	if (front == rear)
		return false;
	e = base[front];
	front = (front + 1) % MAXSIZE;
	return true;
}

template<class ElemType>
inline bool myQueue<ElemType>::isEmpty() {
	if (front == rear)
		return true;
	return false;
}

template<class ElemType>
inline int myQueue<ElemType>::length() {
	return (rear - front + MAXSIZE) % MAXSIZE;
}

template<class ElemType>
inline ElemType myQueue<ElemType>::getFront() {
	if (front != rear)
		return base[front];
}

#endif // !myqueue_H

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

自定义栈：

#pragma once
#ifndef mystack_H
#define mystack_H
#define MAXSIZE 1000;
template<typename ElemType>
class myStack
{
private:
	ElemType* base;
	ElemType* top;
	int stackSize;
public:
	bool initStack();//1.初始化
	bool push(ElemType e);//2.入栈
	bool pop(ElemType& e);//3.出栈
	bool isEmpty();//4.判断是否为空
	bool isFull();//5.判断是否为满
	ElemType getTop();//6.获取栈顶元素
};

//初始化栈
template<typename ElemType>
bool myStack<ElemType>::initStack() {
	base = new ElemType[1000];
	if (!base)
		return false;
	top = base;
	stackSize = MAXSIZE;
	return true;
}

//入栈
template<typename ElemType>
bool myStack<ElemType>::push(ElemType e) {
	if (this->top - this->base == stackSize)
		return false;
	*top++ = e;
	return true;
}

//出栈
template<typename ElemType>
bool myStack<ElemType>::pop(ElemType& e) {
	if (this->top == this->base)
		return false;
	e = *(top - 1);
	top--;
	return true;
}

//判断栈是否为空(没有用到)
template<typename ElemType>
bool myStack<ElemType>::isEmpty() {
	if (top == base) 
		return true;
	return false;
	
}

//判断栈是否为满(没有用到)
template<typename ElemType>
bool myStack<ElemType>::isFull() {
	if (this->top - this->base == stackSize) 
		return true;
	return false;

}

//获取栈顶元素，不弹出
template<typename ElemType>
ElemType myStack<ElemType>::getTop() {
	if (base != top)
		return *(top - 1);
}

#endif // !mystack_H

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

5.main函数

#include"BinaryTree.h"
int main() {
	string s;
	cout << "请输入二叉树序列：" << endl;
	cin >> s;
	binaryTree bt;
	bt.preorderCreate(s);
	cout << "递归先序成功建立二叉树" << endl;
	cout << "递归先序遍历的结果：" << endl;
	bt.preOrder(bt.root);
	cout << endl;
	cout << "非递归先序遍历结果：" << endl;
	bt._preOrder(bt.root);
	cout << endl;
	cout << "递归中序遍历结果：" << endl;
	bt.inOrder(bt.root);
	cout << endl;
	cout << "非递归中序遍历：" << endl;
	bt._inOrder(bt.root);
	cout << endl;
	cout << "递归后续遍历结果：" << endl;
	bt.postOrder(bt.root);
	cout << endl;
	cout << "非递归后续遍历结果：" << endl;
	bt._postOrder(bt.root);
	cout << endl;
	cout << "层次遍历结果：" << endl;
	bt.levelOrder(bt.root);
	return 0;
}
//ABD##E#F##C##
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

main函数所用例子对应的二叉树如下图所示：