二叉树非递归先序遍历

gaotong1991

浏览: 92809 次
来自: 北京

最近访客更多访客>>

u012363178

czj4451

qnlpkuge

zhxhcj

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

算法之道

算法数据结构

二叉树的先序遍历使用递归很简单，代码如下：

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
}