二叉树建立（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
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
#include<iostream>
#include<queue>
using namespace std;
class tree {
public:
	char value;//结点值
	tree *liftchild;//左子树指针
	tree *rightChild;//右子树指针
};
void creat_tree(tree * &T)//创建二叉树
{
	char ch;
	ch = getchar();//从键盘输入一串字母,依次读取,直至换行键
	if (ch == '#')
		T = NULL;
	else {
		T = new tree;
		T->value = ch;
		creat_tree(T->liftchild);
		creat_tree(T->rightChild);
	}
}
void VLR(tree *T)//先序遍历二叉树
{
	if (T == NULL)
		return;
	else {
			cout << T->value;
			VLR(T->liftchild);
			VLR(T->rightChild);
	}
}
void LVR(tree *T)//中序遍历二叉树
{
	if (T == NULL)
		return;
	else {
		LVR(T->liftchild);
		cout << T->value;
		LVR(T->rightChild);
	}
}
void LRV(tree *T)
{
	if (T == NULL)
		return;
	else {
		LRV(T->liftchild);
		
		LRV(T->rightChild);
		cout << T->value;
	}

}
int caclnum(tree* T)//计算结点个数
{
	if (T == NULL)
		return 0;
	else
	{
		return 1 + caclnum(T->liftchild) + caclnum(T->rightChild);//计算二叉树结点个数
	}

}
void LevelOrder(tree * T)//层次遍历
{
	if (T == NULL)
		return;
	queue<tree *> deq;//建立一个队列容器
	
	deq.push(T);
	while (!deq.empty())
	{
		tree *tr = deq.front();
		cout << tr->value << endl;
		deq.pop();
		if (tr->liftchild != NULL)
			deq.push(tr->liftchild);

		if (tr->rightChild!= NULL)
			deq.push(tr->rightChild);
	}
}
int main() {

	tree * T ;
	creat_tree(T);
	VLR(T);//前序遍历
	cout << endl;
	LVR(T);//中序遍历
	cout << endl;
	LRV(T);//后序遍历
	cout << caclnum(T);//统计结点个数
	LevelOrder(T);//层次遍历
	system("pause");
	
	return 0;
}