1. 首页
  2. IT资讯

二叉树的非递归遍历

前面一篇介绍了二叉树的递归遍历操作http://blog.itpub.net/29876893/viewspace-1841619/,下面介绍二叉树的非递归遍历操作。
运用递归操作,很容易进行二叉树的遍历,结合上篇文章的介绍,在递归的时候都是找到当前结点,压入”栈“中,然后再通过当前结点找到左(右)孩子,递归函数每次返回时,当前结点都会出”栈“。在非递归遍历时,那就构造一个栈,用来存取每个结点的指针,通过该结点找到(左)右孩子,思路是有了。
下面结合下图简单的说明一下:

                                                                                               

          二叉树的非递归遍历

前序遍历:
首先A,B,C依次入栈,然后由于C->lchild为空,所以返回到结点C,遍历其右孩子C->rchild,但是也为空,此时C出栈,遍历B结点的右孩子,为空,B出栈,返回到A,A出栈,遍历A结点的右孩子,打印D的数据域,D进栈,遍历D的左孩子,为空,D出栈,遍历D的右孩子,为空,此时栈也空,该循环结束。
中序遍历:
首先A,B,C依次入栈,然后由于C->lchild为空,所以返回到C,打印C结点的数据域,然后遍历C->rchild,由于为空,C出栈,返回到B,打印结点B的数据域,然后遍历B->rchild,由于为空,B出栈,返回到A,A出栈,打印结点A的数据域,然后遍历A->rchild,不为空,然后遍历D->lchild,为空,返回到D,D出栈,打印D结点的数据域,然后遍历D->rchild,由于为空,此时栈为空,循环结束。
后序遍历:
A,B,C依次入栈,第一次遍历这些结点时,设置了标记,都为0.然后遍历C->lchild,为空,此时返回C,设置标记为1,然后访问C->rchild,由于为空,此时C出栈,打印了C结点的数据域。下面也是这样分析,由于过程复杂,读者可以自己分析,这里不作赘述。
下面给出上述的实现代码:

点击(此处)折叠或打开

  1. #include<iostream>
  2. #define MAX_SIZE 20
  3. using namespace std;
  4. typedef struct TreeNote {
  5.     char ch;
  6.     struct TreeNote *lchild, *rchild;
  7. }*BiTree;
  8. typedef struct Stack {
  9.     BiTree data[MAX_SIZE];
  10.     int top;
  11. };
  12. void createBiTree(BiTree &bt) {
  13.     char chh;
  14.     cin >> chh;
  15.     if (chh == #)
  16.         bt = NULL;
  17.     else {
  18.         bt = new TreeNote;
  19.         bt>ch = chh;
  20.         createBiTree(bt>lchild);
  21.         createBiTree(bt>rchild);
  22.     }
  23. }
  24. void initStack(Stack *&st) {
  25.     st = new Stack;
  26.     st>top = 1;
  27. }
  28. bool emptyStack(Stack *st) {
  29.     return st>top == 1;
  30. }
  31. bool fullStack(Stack *st) {
  32.     return st>top == MAX_SIZE 1;
  33. }
  34. void pushStack(Stack *st, BiTree bt) {
  35.     if (!fullStack(st))
  36.         st>data[++st>top] = bt;
  37.     else
  38.         cout << “栈已满!” << endl;
  39.     // exit(1);
  40. }
  41. BiTree pop(Stack *st) {
  42.     if (!emptyStack(st)) {
  43.         return st>data[st>top];
  44.     }
  45.     else
  46.         return NULL;
  47. }
  48. BiTree getpop(Stack *st) {
  49.     if (!emptyStack(st)) {
  50.         return st>data[st>top];
  51.     }
  52.     else
  53.         return NULL;
  54. }
  55. void preOrderTree(BiTree bt) {
  56.     Stack *st;
  57.     initStack(st);
  58.     BiTree p;
  59.     p = bt;
  60.     while (p != NULL || !emptyStack(st))
  61.     {
  62.         while (p != NULL)
  63.         {
  64.             cout << p>ch << ” “;
  65.             pushStack(st, p);
  66.             p = p>lchild;
  67.         }
  68.         if (!emptyStack(st))
  69.         {
  70.             p = pop(st);
  71.             p = p>rchild;
  72.         }
  73.     }
  74. }
  75. void InOrderTree(BiTree bt) {
  76.     Stack *st;
  77.     initStack(st);
  78.     BiTree p;
  79.     p = bt;
  80.     while (p != NULL || !emptyStack(st)) {
  81.         while (p != NULL) {
  82.             pushStack(st, p);
  83.             p = p>lchild;
  84.         }
  85.         if (!emptyStack(st)) {
  86.             p = pop(st);
  87.             cout << p>ch << ” “;
  88.             p = p>rchild;
  89.         }
  90.     }
  91. }
  92. void postOrderTree(BiTree bt)
  93. {
  94.     BiTree p;
  95.     Stack *st;
  96.     initStack(st);
  97.     p = bt;
  98.     int flag[20];
  99.     while (p != NULL || !emptyStack(st))
  100.     {
  101.         while (p != NULL)
  102.         {
  103.             pushStack(st, p);
  104.             flag[st>top] = 0;
  105.             p = p>lchild;
  106.         }
  107.         while (!emptyStack(st) && flag[st>top] == 1)
  108.         {
  109.             p = pop(st);
  110.             cout << p>ch << ” “;
  111.         }
  112.         if (!emptyStack(st))
  113.         {
  114.             flag[st>top] = 1;
  115.             p = getpop(st);
  116.             p = p>rchild;
  117.         }
  118.         else break;
  119.     }
  120. }
  121. int main() {
  122.     TreeNote *bt;
  123.     cout << “please input some values:” << endl;
  124.     createBiTree(bt);
  125.     cout << “preOrderTree:” << endl;
  126.     preOrderTree(bt);
  127.     cout << endl;
  128.     cout << “InOrderTree:” << endl;
  129.     InOrderTree(bt);
  130.     cout << endl;
  131.     cout << “postOrderTree:” << endl;
  132.     postOrderTree(bt);
  133.     cout << endl;
  134. }

运行结果:
二叉树的非递归遍历

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/29876893/viewspace-1848850/,如需转载,请注明出处,否则将追究法律责任。

主题测试文章,只做测试使用。发布者:℅傍ㄖ免沦陷dε鬼,转转请注明出处:http://www.cxybcw.com/191802.html

联系我们

13687733322

在线咨询:点击这里给我发消息

邮件:1877088071@qq.com

工作时间:周一至周五,9:30-18:30,节假日休息

QR code