遍历二叉树(递归与非递归)

接下来的几天里,我会更多地关注于算法这一块,每天去牛客网刷题,并将其记录在这里。
这两天一直在看与二叉树相关的题,利用这篇博客对于二叉树的遍历做一番总结。

二叉树的遍历是指按照某条搜索路线遍访每个结点且不重复,它是树结构插入、删除、修改、查找和排序运算的前提,也是二叉树一切运算的基础和核心。
因为树的结构定义本身就是递归,所以递归遍历二叉树会显得更加简洁。但是越简单,有时候理解起来就感觉越为抽象,就像著名的汉诺塔问题一样,我对于递归遍历二叉树的流程没有一个深入的认识了解,而接下来我会去深入了解一下。

定义二叉树的存储结构如下:

1
2
3
4
5
typedef struct BiNode
{
char data;
status BiNode *lchild,*rchild;
}TreeNode,*BiTree;

先序遍历

特点:若二叉树为空,则空操作;否则先访问根结点,然后遍历左子树,再遍历右子树

递归

1
2
3
4
5
6
7
void PreOrderTraverse(TreeNode *root)  {
if (root!=NULL) {
cout<<root->data; //在层层调用的过程中即输出结点值
PreOrderTraverse(root->lchild);
PreOrderTraverse(root->rchild);
}
}

原理分析

假如有一棵如下结构的二叉树:

将其利用递归先序的方式遍历,具体执行流程如下:

整个递归过程即是函数的层层调用,类似于将函数进行压栈处理

另外需要提及的一点是:从递归的角度去遍历二叉树时,如果去掉输出语句,三种算法是完全相同的。
访问路径是相同的,只是访问结点的时机不同

从虚线的出发点到终点路径上,每个结点经过3次。

  • 第1次经过时访问结点:先序遍历
  • 第2次经过时访问结点:中序遍历
  • 第3次经过时访问结点:后序遍历

非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void preorderTraverse(TreeNode *root) {
stack<TreeNode *> s;
TreeNode *p=root;
while (p||!s.empty()) {
while (p) { //沿着结点到最左下
cout<<p->data;
s.push(p);
p=p->lchild;
}
if (!s.empty()) {
p=s.top();
s.pop();
p=p->rchild;
}
}
}

原理分析

还是利用上面提及的那棵二叉树,将其利用先序非递归的方式遍历,的变化过程如下:

中序遍历

特点:若二叉树为空,则空操作;否则先遍历左子树,然后访问根结点,再遍历右子树

递归

1
2
3
4
5
6
7
void InOrderTraverse(TreeNode *root)  {
if (root!=NULL) {
InOrderTraverse(root->lchild);
cout<<root->data;
InOrderTraverse(root->rchild);
}
}

非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void InorderTraverse(TreeNode *root)  {
stack<TreeNode *> s;
TreeNode *p=root;
while (p||!s.empty()) {
while (p) {
s.push(p);
p=p->lchild;
}
if (!s.empty()) {
p=s.top();
cout<<p->data;
s.pop();
p=p->rchild;
}
}
}

后序遍历

特点:若二叉树为空,则空操作;否则先遍历左子树,然后访问根结点,再遍历右子树

递归

1
2
3
4
5
6
7
void PostOrderTraverse(TreeNode *root)  {
if (root!=NULL) {
PostOrderTraverse(root->lchild);
PostOrderTraverse(root->rchild);
cout<<root->data;
}
}

非递归

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
void postorderTraverse(TreeNode *root)  {
stack<TreeNode *> s;
TreeNode *p=root,*q=nullptr;
do {
while (p != nullptr) { //顺着结点一直往左下走
s.push(p);
p = p->left;
}
q = nullptr;
while (!s.empty()) {
p = s.top();
s.pop();
//判断处于栈顶的p结点右孩子是否为空或者右孩子是否已经被访问过
if (p->right == q) {
cout<<p->data;
//保存访问过的结点,可供父节点判断使用
q = p;
}
else { //说明右孩子存在且未被访问过
//栈顶的p结点之前被错误释放,所以需要重新入栈
s.push(p);
p = p->right;
break; //跳出当前循环,将右孩子压入栈中
}
}
} while (!s.empty());
}
-------------The End-------------