0%

数据结构-树和二叉树(二)二叉树的遍历

数据结构-树和二叉树(二)二叉树的遍历

1 先序遍历

DLR—先序遍历,即先根再左再右

先序遍历(PreOrder)的操作过程如下:

  1. 若二叉树为空,则什么也不做;

  2. 若二叉树非空:

    ①访问根结点;

    ②先序遍历左子树;

    ③先序遍历右子树。

2 中序遍历

LDR—中序遍历,即先左再根再右

中序遍历(InOrder)的操作过程如下:

  1. 若二叉树为空,则什么也不做;

  2. 若二叉树非空:

    ①中序遍历左子树;

    ②访问根结点;

    ③中序遍历右子树。

3 后序遍历

LRD—后序遍历,即先左再右再根

后序遍历(PostOrder)的操作过程如下:

  1. 若二叉树为空,则什么也不做;

  2. 若二叉树非空:

    ①后序遍历左子树;

    ②后序遍历右子树;

    ③访问根结点。

4 层次遍历

算法思想:

①初始化一个辅助队列

②根结点入队

③若队列非空,则队头结点出队,访问该结点,并将其左、右孩子插入队尾(如果有的话)

④重复③直至队列为空

5 代码实现

实现对如图二叉树创建遍历

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
#include <iostream>
#include <string>
#include <queue>
using namespace std;
typedef struct BiTNode {
int value; //数据域
struct BiTNode *lChild, *rChild; //左、右孩子指针
}BiTNode, *BiTree;

/**
* 创建二叉树
* @param root
* @return
*/
bool CreateBiTNode(BiTree &root) {
//创造新结点
auto *node1 = (BiTNode *)malloc(sizeof(BiTNode));
auto *node2 = (BiTNode *)malloc(sizeof(BiTNode));
auto *node3 = (BiTNode *)malloc(sizeof(BiTNode));
auto *node4 = (BiTNode *)malloc(sizeof(BiTNode));
auto *node5 = (BiTNode *)malloc(sizeof(BiTNode));
auto *node6 = (BiTNode *)malloc(sizeof(BiTNode));
//为结点赋值
root->value = 15;
node1->value = 10;
node2->value = 23;
node3->value = 8;
node4->value = 12;
node5->value = 21;
node6->value = 9;
//分层赋子节点
root->lChild = node1;
root->rChild = node2;
//
node1->lChild = node3;
node1->rChild = node4;
node2->lChild = node5;
node2->rChild = nullptr;
//
node3->lChild = nullptr;
node3->rChild = node6;
node4->lChild = nullptr;
node4->rChild = nullptr;
node5->rChild = nullptr;
node5->lChild = nullptr;
//
node6->lChild = nullptr;
node6->rChild = nullptr;
}


/**
* 先序遍历--先根再左再右
* @param root
*/
void PreOrderTraversal(BiTree root) {
if (root == NULL) {
return;
}
cout << root->value << "->";
PreOrderTraversal(root->lChild); //先序遍历左子树
PreOrderTraversal(root->rChild); //先序遍历右子树
}

/**
* 中序遍历--先左再根再右
* @param root
*/
void InOrderTraversal(BiTree root) {
if (root == NULL) {
return;
}
InOrderTraversal(root->lChild); //中序遍历左子树
cout << root->value << "->";
InOrderTraversal(root->rChild); //中序遍历右子树
}

/**
* 后序遍历--先左再右再根
* @param root
*/
void PostOrderTraversal(BiTree root) {
if (root == nullptr) {
return;
}
PostOrderTraversal(root->lChild); //后序遍历左子树
PostOrderTraversal(root->rChild); //h序遍历右子树
cout << root->value << "->";
}

/**
* 层次遍历
* @param root
*/
void LevelOrderTraversal(BiTree root) {
queue<BiTNode *> tree; //声明队列
tree.push(root); //根节点入队
while (!tree.empty()) { //当队列不为空
BiTNode *p = tree.front(); //队头结点出队
tree.pop();
cout << p->value << "->"; //打印队头结点数据
if (p->lChild != nullptr) { //左子树不为空,左子树根节点入队
tree.push(p->lChild);
}
if (p->rChild != nullptr) { //左子树不为空,左子树根节点入队
tree.push(p->rChild);
}
}

}
int main() {
BiTree root;
root = (BiTNode *)malloc(sizeof(BiTNode));
cout << "初始化创建二叉树" << endl;
CreateBiTNode(root);
cout << "先序遍历二叉树--先左再根再右" << endl;
PreOrderTraversal(root);
printf("\n");
cout << "中序遍历二叉树--先左再根再右" << endl;
InOrderTraversal(root);
printf("\n");
cout << "后序遍历二叉树--先左再右再根" << endl;
PostOrderTraversal(root);
printf("\n");
cout << "层次遍历二叉树--按层次遍历" << endl;
LevelOrderTraversal(root);
return 0;
}
1
2
3
4
5
6
7
8
9
10
初始化创建二叉树
先序遍历二叉树--先左再根再右
15->10->8->9->12->23->21->
中序遍历二叉树--先左再根再右
8->9->10->12->15->21->23->
后序遍历二叉树--先左再右再根
9->8->12->10->21->23->15->
层次遍历二叉树--按层次遍历
15->10->23->8->12->21->9->
Process finished with exit code 0

6 由遍历序列构造二叉树

北以晨光 wechat
欢迎您扫一扫上面的微信公众号,订阅我的博客!
------ 本文结束感谢您的阅读 ------