二叉树的先序遍历使用递归很简单,代码如下:
void preOrder(TNode* root)
{
if (root != NULL)
{
Visit(root);
preOrder(root->left);
preOrder(root->right);
}
}
先访问跟节点,然后访问左节点,再访问右节点。如果不用递归,那该怎么做呢?仔细看一下递归程序,就会发现,其实每次都是走树的左分支(left),直到左子树为空,然后开始从递归的最深处返回,然后开始恢复递归现场,访问右子树。
其实过程很简单:一直往左走 root->left->left->left…->null,由于是先序遍历,因此一遇到节点,便需要立即访问;由于一直走到最左边后,需要逐步返回到父节点访问右节点,因此必须有一个措施能够对节点序列回溯。有两个办法:
1.用栈记忆:在访问途中将依次遇到的节点保存下来。由于节点出现次序与恢复次序是反序的,因此是一个先进后出结构,需要用栈。
2.节点增加指向父节点的指针:通过指向父节点的指针来回溯
方法一,直接用栈模拟递归。次将节点压入栈,然后弹出,压右子树,再压入左子树,在遍历过程中,遍历序列的右节点依次被存入栈,左节点逐次被访问。同一时刻,栈中元素为m-1个右节点和1个最左节点,最高为h。所以空间也为O(h);每个节点同样被压栈一次,弹栈一次,访问一次,时间复杂度O(n)
01 |
#include <stdlib.h> |
02 |
#include <stdio.h> |
03 |
#include <iostream> |
04 |
#include <stack> |
05 |
06 |
using namespace std;
|
07 |
08 |
/* 二叉树节点 */ |
09 |
struct node
|
10 |
{ |
11 |
int data;
|
12 |
struct node* left;
|
13 |
struct node* right;
|
14 |
}; |
15 |
16 |
struct node* newNode( int data)
|
17 |
{ |
18 |
struct node* node = new struct node;
|
19 |
node->data = data;
|
20 |
node->left = NULL;
|
21 |
node->right = NULL;
|
22 |
return (node);
|
23 |
} |
24 |
25 |
// 非递归的方式先序遍历二叉树 |
26 |
void iterativePreorder(node *root)
|
27 |
{ |
28 |
if (root == NULL)
|
29 |
return ;
|
30 |
31 |
// 根节点入栈
|
32 |
stack<node *> nodeStack;
|
33 |
nodeStack.push(root);
|
34 |
35 |
while (nodeStack.empty() == false )
|
36 |
{
|
37 |
// 访问根节点
|
38 |
struct node *node = nodeStack.top();
|
39 |
printf ( "%d " , node->data);
|
40 |
nodeStack.pop();
|
41 |
42 |
// 不为空的话则入栈
|
43 |
if (node->right)
|
44 |
nodeStack.push(node->right);
|
45 |
if (node->left)
|
46 |
nodeStack.push(node->left);
|
47 |
}
|
48 |
} |
49 |
50 |
//测试 |
51 |
int main()
|
52 |
{ |
53 |
/* 创建以下的树
|
54 |
10
|
55 |
/ \
|
56 |
8 2
|
57 |
/ \ /
|
58 |
3 5 2
|
59 |
*/
|
60 |
struct node *root = newNode(10);
|
61 |
root->left = newNode(8);
|
62 |
root->right = newNode(2);
|
63 |
root->left->left = newNode(3);
|
64 |
root->left->right = newNode(5);
|
65 |
root->right->left = newNode(2);
|
66 |
iterativePreorder(root);
|
67 |
return 0;
|
68 |
} |
方法二 同样是使用栈,每次都将遇到的节点压入栈,当左子树遍历完毕后才从栈中弹出最后一个访问的节点,访问其右子树。在同一层中,不可能同时有两个节点压入栈,因此栈的大小空间为O(h),h为二叉树高度。时间方面,每个节点都被压入栈一次,弹出栈一次,访问一次,复杂度为O(n)
01 |
void iterativePreorder2(node *root) {
|
02 |
stack<node *> s;
|
03 |
while ((root != NULL) || !s.empty()) {
|
04 |
if (root != NULL) {
|
05 |
printf ( "%d " , root->data);
|
06 |
s.push(root); // 先序就体现在这里了,先访问,再入栈
|
07 |
root = root->left; // 依次访问左子树
|
08 |
} else {
|
09 |
root = s.top(); // 回溯至父亲节点. 此时根节点和左子树都已访问过
|
10 |
s.pop();
|
11 |
root = root->right;
|
12 |
}
|
13 |
}
|
14 |
} |
原文:http://www.acmerblog.com/iterative-preorder-traversal-5853.html
相关推荐
用C++写的,包括二叉树的构建,二叉树的先序遍历、中序遍历和后序遍历非递归算法。
用C++写的二叉树先序遍历、中序遍历和后序遍历非递归算法
要求能够输入树的各个结点,并能够输出用不同方法遍历的遍历序列;分别建立建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数;
用户以先序遍历的方式键入二叉树各结点的数据域值(字符型),程序建立二叉树,然后分别用递归和非递归算法对二叉树进行遍历。每访问一个结点即打印该结点的数据域值。
编写先序遍历二叉树的非递归算法程序,要求: (1)以二叉链表建立二叉树。 (2)输出遍历的结点序列。 (3)有实例验算。
包含一下方法: 1.通过一个数组来构造一颗...6.使用非递归 先序遍历一棵二叉树 7.使用非递归 中序遍历一棵二叉树 8.使用非递归 后序遍历一棵二叉树 PS:代码为C++代码 可以直接下载使用!!! PS2:每句代码都有详细注释
二叉树的几种操作,包括递归先序建立二叉树、先序遍历、中序遍历、后序遍历、非递归的各种遍历、计算叶子节点数目和所有节点数目,使用队列实现二叉树的层次遍历.zip
数据结构二叉树链式结构的前序遍历,中序遍历,后序遍历用递归的方法,层级遍历采用队列结构
按先序遍历的扩展序列建立二叉树的二叉链表存储结构,实现二叉树先序、中序、后序遍历的递归算法,实现二叉树中序遍历的非递归算法,实现二叉树层次遍历的非递归算法(要求使用顺序队列,调用顺序队列基本操作...
C,二叉树中的非递归的先序遍历 (附带算法说明书word)利用栈数据结构实现二叉树中的非递归的先序遍历。
数据结构基于C++语言程序开发的树的非递归先序遍历 if (p->rchild != NULL)/* 右孩子入栈 */ { top++; stack[top] = p->rchild; } if (p->lchild != NULL)/* 左孩子入栈 */ { top++; stack[top] = p->...
主要介绍了C#非递归先序遍历二叉树的实现方法,具有一定参考借鉴价值,需要的朋友可以参考下
二叉树先序、中序、后序遍历非递归算法,简述了二叉树的基本算法。
2)对这棵二叉树进行先序遍历(采用递归算法实现)与中序遍历(采用非递归算法实现),分别输出结点的遍历序列; 2)求二叉树的深度(选做)。 这是本人所做的作业,虽然分有点多,但还是有所值的!
1.建立完全二叉树 2.先序非递归遍历二叉树函数 & 先序递归遍历二叉树验证 3.中序非递归遍历二叉树函数 & 中序递归遍历二叉树验证 4.后序非递归遍历二叉树函数 & 后序递归遍历二叉树验证
C语言实现通用栈结构 递归遍历二叉树 非递归遍历二叉树 (前,中,后序) exmaple.c为测试文件
非递归先序遍历二叉树: 非递归中序遍历二叉树: 非递归后序遍历二叉树: 非递归中序遍历二叉树(算法2): 层次遍历二叉树: 递归计算单分支结点: 递归计算双分支结点: 递归计算叶子数: 二叉数的深度:...
先序遍历的非递归算法C语言二叉树前序、中序、后序三种遍历的非递归算法和递归算法最精悍版
后序遍历二叉树非递归算法的推导及形式化证明,难得的期刊论文资料,对研究二叉树的非递归性遍历有很大帮助