二叉树-遍历（CPP实现简单易懂图解解法很全）_cpp 前序遍历

二叉树-遍历

 

目录

一、二叉树的创建

1.1递归创建

1.2迭代创建

二、先序遍历

2.1递归解法

2.2迭代解法1

2.3迭代解法2

三、中序遍历

3.1递归解法

3.2迭代解法

四、后序遍历

4.1递归解法

4.2迭代解法

五、层次遍历

迭代解法

 

一、二叉树的创建

1.1递归创建

思路

先创建根节点，然后先后创建左右节点

基线条件： 当子节点指针为空时， 返回

递归条件：子节点不为空， 创建新的子节点， 同时把这个子节点当作这个子树的跟节点，递归下去

开辟到堆区的数据情况如下图：

 

算法实现

#include <iostream>
using namespace std;
struct BTreeNode
{
	char data;
	BTreeNode* left;
	BTreeNode* right;
};

class BTree
{
public:
	void create(BTreeNode* &Node)
	{
		char data;
		cin >> data;
		if (data != '0')
		{
			Node = new BTreeNode;
			Node->data = data;
			create(Node->left);
			create(Node->right);
		}
		else
		{
			Node = NULL;
		}
	}

	void clear(BTreeNode*& Node)
	{
		if (Node)
		{
			clear(Node->left);
			clear(Node->right);
			delete Node;
		}
	}
};

int main()
{
	BTree tree;
	BTreeNode* root;
	tree.create(root);
	cout << "二叉树创建完成！" << endl;
    system("pause");
	clear(boot);
	cout << "二叉树清理完成！" << endl;
	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

返回目录

 

1.2迭代创建

思路

按层创建二叉树

使用一个队列， 先初始化根节点，然后将此节点推入队列中，只要队列不为空，就从队列中弹出一个数据，然后将此数据的左节点赋值，一旦赋值成功就将此节点推入队列中，然后将此节点作为根节点，在此后循环中创建子树，然后右节点赋值

 

代码实现

#include <iostream>
using namespace std;
#include <queue>
struct BTreeNode
{
	char data;
	BTreeNode* left;
	BTreeNode* right;
};

class BTree
{
public:
	void levelCreate(BTreeNode*& Node)
	{
		queue<BTreeNode*> que;
		char data;
		cin >> data;
		if (data != '0')
		{
			Node = new BTreeNode;
			Node->data = data;
			que.push(Node);
		}
		else
		{
			Node = NULL;
			return;
		}
		while (!que.empty())
		{
			BTreeNode* node = que.front();
			que.pop();
			//输入左值
			cin >> data;
			if (data != '0')
			{
				node->left = new BTreeNode;
				node->left->data = data;
				que.push(node->left);
			}
			else
			{
				node->left = NULL;
			}
			//输入右值
			cin >> data;
			if (data != '0')
			{
				node->right = new BTreeNode;
				node->right->data = data;
				que.push(node->right);
			}
			else
			{
				node->right = NULL;
			}
		}
	}

	void clear(BTreeNode*& Node)
	{
		if (Node)
		{
			clear(Node->left);
			clear(Node->right);
			delete Node;
		}
	}
};

int main()
{
	BTree tree;
	BTreeNode* boot;
	tree.levelCreate(boot);
	cout << "二叉树创建完成！" << endl;
	system("pause");
	tree.clear(boot);
	cout << "二叉树清理完成！" << endl;
	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
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

返回目录

 

二、先序遍历

2.1递归解法

思路

递归条件：节点不为空， 先返回左节点，然后返回右节点

基线条件：当节点为空时，返回空

 

代码实现

#include <iostream>
using namespace std;
struct BTreeNode
{
	char data;
	BTreeNode* left;
	BTreeNode* right;
};

class BTree
{
public:
	void create(BTreeNode*& Node)
	{
		char data;
		cin >> data;
		if (data != '0')
		{
			Node = new BTreeNode;
			Node->data = data;
			create(Node->left);
			create(Node->right);
		}
		else
		{
			Node = NULL;
		}
	}

	void preorderTree(BTreeNode* Node)
	{
		if (Node)
		{
			cout << Node->data << " ";
			preorderTree(Node->left);
			preorderTree(Node->right);
		}
		else
		{
			return;
		}
	}

	void clear(BTreeNode*& Node)
	{
		if (Node)
		{
			clear(Node->left);
			clear(Node->right);
			delete Node;
		}
	}
};

int main()
{
	BTree tree;
	BTreeNode* root;
	tree.create(root);
	cout << "前序遍历：" << endl;
	tree.preorderTree(root);
	cout << endl;
	tree.clear(root);
	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
56
57
58
59
60
61
62
63
64
65
66

运行结果：

返回目录

 

2.2迭代解法1

思路

准备一个栈容器，只要遇到一个非空节点，就将其推入栈中，一直向左访问直到访问到空指针，然后从栈中弹出元素，依次回溯访问之前还没有访问的右节点，直到此时的指针为空并且栈中元素为空，说明所有非空节点右边子节点均以访问，循环停止

 

代码实现

#include <iostream>
using namespace std;
#include <stack>
struct BTreeNode
{
	char data;
	BTreeNode* left;
	BTreeNode* right;
};

class BTree
{
public:
	void create(BTreeNode*& Node)
	{
		char data;
		cin >> data;
		if (data != '0')
		{
			Node = new BTreeNode;
			Node->data = data;
			create(Node->left);
			create(Node->right);
		}
		else
		{
			Node = NULL;
		}
	}

	void preorderTree(BTreeNode* Node)
	{
		stack<BTreeNode*> node;
		BTreeNode* pnode = Node;
		while (pnode != NULL || !node.empty())
		{
			if (pnode)
			{
				cout << pnode->data << " ";
				node.push(pnode);
				pnode = pnode->left;
			}
			else
			{
				BTreeNode* treenode = node.top();
				node.pop();
				pnode = treenode->right;
			}
		}
	}

	void clear(BTreeNode*& Node)
	{
		if (Node)
		{
			clear(Node->left);
			clear(Node->right);
			delete Node;
		}
	}
};

int main()
{
	BTree tree;
	BTreeNode* root;
	tree.create(root);
	cout << "先序遍历：" << endl;
	tree.preorderTree(root);
	cout << endl;
	tree.clear(root);
	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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

运行结果：

返回目录

 

2.3迭代解法2

思路

准备一个栈容器， 将它的右子节点存入栈中， 递推左子节点直到为空，从栈中弹出一个元素，访问它，一直这样循环直到栈为空，说明所有右子节点都访问完，即前序遍历完成

 

实现代码

#include <iostream>
using namespace std;
#include <stack>
struct BTreeNode
{
	char data;
	BTreeNode* left;
	BTreeNode* right;
};

class BTree
{
public:
	void create(BTreeNode*& Node)
	{
		char data;
		cin >> data;
		if (data != '0')
		{
			Node = new BTreeNode;
			Node->data = data;
			create(Node->left);
			create(Node->right);
		}
		else
		{
			Node = NULL;
		}
	}

	void preorderTree(BTreeNode* Node)
	{
		stack<BTreeNode*> node;
		while (true)
		{
			while (Node)
			{
				cout << Node->data << " ";
				node.push(Node->right);
				Node = Node->left;
			}
			if (node.empty())
			{
				break;
			}
			Node = node.top();
			node.pop();
		}
	}

	void clear(BTreeNode*& Node)
	{
		if (Node)
		{
			clear(Node->left);
			clear(Node->right);
			delete Node;
		}
	}
};

int main()
{
	BTree tree;
	BTreeNode* root;
	tree.create(root);
	cout << "先序遍历：" << endl;
	tree.preorderTree(root);
	cout << endl;
	tree.clear(root);
	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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

运行结果：

返回目录

 

三、中序遍历

3.1递归解法

思路

基线条件：节点为空指针，返回

递归条件：节点不为空，先递归调用访问左子节点， 然后访问当前节点， 最后递归调用访问右子节点

 

代码实现

#include <iostream>
using namespace std;
struct BTreeNode
{
	char data;
	BTreeNode* left;
	BTreeNode* right;
};

class BTree
{
public:
	void create(BTreeNode*& Node)
	{
		char data;
		cin >> data;
		if (data != '0')
		{
			Node = new BTreeNode;
			Node->data = data;
			create(Node->left);
			create(Node->right);
		}
		else
		{
			Node = NULL;
		}
	}

	void inorderTree(BTreeNode* Node)
	{	
		if (Node)
		{
			inorderTree(Node->left);
			cout << Node->data << " ";
			inorderTree(Node->right);
		}
	}

	void clear(BTreeNode*& Node)
	{
		if (Node)
		{
			clear(Node->left);
			clear(Node->right);
			delete Node;
		}
	}
};

int main()
{
	BTree tree;
	BTreeNode* root;
	tree.create(root);
	cout << "中序遍历：" << endl;
	tree.inorderTree(root);
	cout << endl;
	tree.clear(root);
	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
56
57
58
59
60
61
62

运行结果：

返回目录

 

3.2迭代解法

思路

先准备一个栈，依次从根节点一直向左下前进，直到发现当前节点为空，然后从栈中弹出一个节点，先访问自己，然后再访问它的右子节点，一直迭代这过程，直到当前节点为空节点， 并且此时栈为空，即中序遍历完成

 

代码实现

#include <iostream>
using namespace std;
#include<stack>
struct BTreeNode
{
	char data;
	BTreeNode* left;
	BTreeNode* right;
};

class BTree
{
public:
	void create(BTreeNode*& Node)
	{
		char data;
		cin >> data;
		if (data != '0')
		{
			Node = new BTreeNode;
			Node->data = data;
			create(Node->left);
			create(Node->right);
		}
		else
		{
			Node = NULL;
		}
	}

	void inorderTree(BTreeNode* Node)
	{
		stack<BTreeNode*> node;
		while (true)
		{
			while (Node)
			{
				node.push(Node);
				Node = Node->left;
			}

			if (node.empty())
			{
				break;
			}
			Node = node.top();
			node.pop();
			cout << Node->data << " ";
			Node = Node->right;
		}
	}

	void clear(BTreeNode*& Node)
	{
		if (Node)
		{
			clear(Node->left);
			clear(Node->right);
			delete Node;
		}
	}
};

int main()
{
	BTree tree;
	BTreeNode* root;
	tree.create(root);
	cout << "中序遍历：" << endl;
	tree.inorderTree(root);
	cout << endl;
	tree.clear(root);
	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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

运行结果：

返回目录

 

四、后序遍历

4.1递归解法

思路

基线条件：访问结点为空

递归条件：结点不为空，先递归调用左子节点，再调用右子节点，最后访问自己

 

代码实现

#include <iostream>
using namespace std;
#include<stack>
struct BTreeNode
{
	char data;
	BTreeNode* left;
	BTreeNode* right;
};

class BTree
{
public:
	void create(BTreeNode*& Node)
	{
		char data;
		cin >> data;
		if (data != '0')
		{
			Node = new BTreeNode;
			Node->data = data;
			create(Node->left);
			create(Node->right);
		}
		else
		{
			Node = NULL;
		}
	}

	void postorderTree(BTreeNode* Node)
	{
		if (Node)
		{
			postorderTree(Node->left);
			postorderTree(Node->right);
			cout << Node->data << " ";
		}
	}

	void clear(BTreeNode*& Node)
	{
		if (Node)
		{
			clear(Node->left);
			clear(Node->right);
			delete Node;
		}
	}
};

int main()
{
	BTree tree;
	BTreeNode* root;
	tree.create(root);
	cout << "后续遍历：" << endl;
	tree.postorderTree(root);
	cout << endl;
	tree.clear(root);
	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
56
57
58
59
60
61
62
63

运行结果：

返回目录

 

4.2迭代解法

思路

准备一个栈容器，先对根结点一直向左迭代，并每次将其入栈，直到访问到空结点，然后将当前结点设置为栈顶的一个结点，如果它的右结点为空或者已经访问过，就访问当前元素， 并把它移出栈，将当前结点设置为空，以便访问上一个结点，反复如此，直到当前结点和栈为空，退出循环，即后续遍历完成

 

代码实现

#include <iostream>
using namespace std;
#include<stack>
struct BTreeNode
{
	char data;
	BTreeNode* left;
	BTreeNode* right;
};

class BTree
{
public:
	void create(BTreeNode*& Node)
	{
		char data;
		cin >> data;
		if (data != '0')
		{
			Node = new BTreeNode;
			Node->data = data;
			create(Node->left);
			create(Node->right);
		}
		else
		{
			Node = NULL;
		}
	}

	void postorderTree(BTreeNode* Node)
	{
		stack<BTreeNode*> node;
		BTreeNode* cur = Node;
		BTreeNode* pre = NULL;
		while (cur || !node.empty())
		{
			while (cur)
			{
				node.push(cur);
				cur = cur->left;
			}
			cur = node.top();
			if (!cur->right || pre == cur->right)
			{
				cout << cur->data << " ";
				node.pop();
				pre = cur;
				cur = NULL;
			}
			else
			{
				cur = cur->right;
			}
		}
	}

	void clear(BTreeNode*& Node)
	{
		if (Node)
		{
			clear(Node->left);
			clear(Node->right);
			delete Node;
		}
	}
};

int main()
{
	BTree tree;
	BTreeNode* root;
	tree.create(root);
	cout << "后续遍历：" << endl;
	tree.postorderTree(root);
	cout << endl;
	tree.clear(root);
	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
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

运行结果：

返回目录

 

五、层次遍历

迭代解法

思路

准备一个队列， 先将根结点入队，然后弹出队列头部元素，访问它并且将它的左结点（如果存在）入队，右节点（如果存在）入队，直到队列为空，即层次遍历完成

 

代码实现

#include <iostream>
using namespace std;
#include <queue>
struct BTreeNode
{
	char data;
	BTreeNode* left;
	BTreeNode* right;
};

class BTree
{
public:
	void create(BTreeNode*& Node)
	{
		char data;
		cin >> data;
		if (data != '0')
		{
			Node = new BTreeNode;
			Node->data = data;
			create(Node->left);
			create(Node->right);
		}
		else
		{
			Node = NULL;
		}
	}

	void levelorderTree(BTreeNode* Node)
	{
		queue<BTreeNode*> node;
		node.push(Node);
		while (!node.empty())
		{
			Node = node.front();
			node.pop(); 
			cout << Node->data << " ";
			if (Node->left)
			{
				node.push(Node->left);
			}
			
			if (Node->right)
			{
				node.push(Node->right);
			}
		}
	}

	void clear(BTreeNode*& Node)
	{
		if (Node)
		{
			clear(Node->left);
			clear(Node->right);
			delete Node;
		}
	}
};

int main()
{
	BTree tree;
	BTreeNode* root;
	tree.create(root);
	cout << "层次遍历：" << endl;
	tree.levelorderTree(root);
	cout << endl;
	tree.clear(root);
	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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

运行结果：

返回目录