二叉树后序遍历(非递归)

深藏阁楼爱情的钟 2024-04-17 22:41 10阅读 0赞

二叉树的递归遍历算法就不用说了；在非递归算法中，后序遍历难度大，很多书上只给出思想或者几段无法直接调试的代码，甚至有些书上是错的，当时我在研究的过程中，就是按着书上错误的代码绕了好半天，几预抓狂。好在最终摸索出来了，不禁感叹很多出书人的水平真是...... 这里将直接可以在编译器里调试的代码贴出来(在DEV-C++编译器中编译通过)

![2010120512553664.png][]

**这里我们约定：空的节点用空格表示，按照前序遍历来创建树！**

1 // main.cpp

![复制代码][copycode.gif]

2  \#include  < iostream >   
 3  using  namespace  std;  
 4 typedef  struct  node \{  
 5  char  data;  
 6  struct  node  \* lchild;  
 7  struct  node  \* rchild;  
 8 \}BiNode, \* BiTree;  
 9 typedef  struct  node1\{  
 10 BiTree data\[ 30 \];  // 默认30个元素 ，这里需要一个辅助堆栈！！！   
 11  int  top;  
 12 \}Stack;  
 13   
 14 void  createTree(BiTree  & T)  // 先序递归创建树，这里注意参数的类型，T的类型是 "\*&" ,如果是 "\*\*" 代码稍加改动就OK...   
 15 \{  
 16  char  ch;  
 17 cin. get (ch). get ();  //过滤输入流中每次回车产生的回车符   
 18  if  (ch == '  ' ) T = NULL;  //这里首先判断是不是空格，如果是，则为该节点赋NULL   
 19  else \{  
 20 T = (BiTree)malloc( sizeof (BiNode));  
 21 T \-> data = ch;  
 22 createTree(T \-> lchild);  
 23 createTree(T \-> rchild);  
 24 \}  
 25 \}  
 26 void  initstack(Stack  \*& st)  
 27 \{  
 28 st = (Stack  \* )malloc( sizeof (Stack));  
 29 st \-> top =- 1 ;  
 30 \}  
 31 bool  isempty(Stack  \* st)  
 32 \{  
 33  return  st \-> top ==- 1 ;  
 34 \}  
 35 bool  isfull(Stack  \* st)  
 36 \{  
 37  return  st \-> top == 19 ;  
 38 \}  
 39 void  push(Stack  \* st,BiTree T)  
 40 \{  
 41  if  ( ! isfull(st))  
 42 st \-> data\[ \++ st \-> top\] = T;  //栈顶指针始终指向堆栈最上面可用的一个元素，因此入栈时候，先要将指针加1,然后再执行入栈操作！   
 43  else  cout << " 已满 " << endl;  
 44 \}  
 45 BiTree pop(Stack  \* st)  
 46 \{  
 47  if  ( ! isempty(st))  return  st \-> data\[st \-> top \-- \];  
 48 \}  
 49 BiTree gettop(Stack  \* st)  
 50 \{  
 51  if  ( ! isempty(st))  return  st \-> data\[st \-> top\];  //出栈时，先取出栈顶指针指向的元素，然后再将指针减1，使其指向栈中下一个可用元素！   
 52 \}  
 53 void  preOrderNoRe(BiTree T)  // 前序遍历   
 54 \{  
 55 Stack  \* st;  
 56 initstack(st);  
 57 BiTree p;  
 58 p = T;  
 59  while  (p != NULL ||! isempty(st))  
 60 \{  
 61  while  (p != NULL)  
 62 \{  
 63 cout << p \-> data << "  " ;  
 64 push(st,p);  
 65 p = p \-> lchild;  
 66 \}  
 67  if  ( ! isempty(st))  
 68 \{  
 69 p = pop(st);  
 70 p = p \-> rchild;  
 71 \}  
 72   
 73 \}  
 74 \}  
 75 void  inOrderNoRe(BiTree T)  //中序遍历   
 76 \{  
 77 Stack  \* st;  
 78 initstack(st);  
 79 BiTree p;  
 80 p = T;  
 81  while  (p != NULL ||! isempty(st))  
 82 \{  
 83  while  (p != NULL)  
 84 \{  
 85 push(st,p);  
 86 p = p \-> lchild;  
 87 \}  
 88  if  ( ! isempty(st))  
 89 \{  
 90 p = pop(st);  
 91 cout << p \-> data << "  " ;  
 92 p = p \-> rchild;  
 93 \}  
 94   
 95 \}  
 96 \}  
 97 void  postOrderNoRe(BiTree T)  //后序遍历   
 98 \{  
 99 BiTree p;  
 100 Stack  \* st;  
 101 initstack(st);  
 102 p = T;  
 103  int  Tag\[ 20 \];  // 栈，用于标识从左（0）或右（1）返回    
 104  while  (p != NULL  ||  ! isempty(st))  
 105 \{  
 106  while  (p != NULL)  
 107 \{  
 108 push(st,p);  
 109 Tag\[st \-> top\] = 0 ;  
 110 p = p \-> lchild;  
 111 \}  
 112  while  ( ! isempty(st) && Tag\[st \-> top\] == 1 )  
 113 \{  
 114 p = pop(st);  
 115 cout << p \-> data << "  " ;  
 116 \}  
 117  if  ( ! isempty(st))  
 118 \{  
 119 Tag\[st \-> top\] = 1 ;  // 设置标记右子树已经访问    
 120 p = gettop(st);  
 121 p = p \-> rchild;  
 122 \}  
 123  else  break ;  
 124 \}  
 125 \}  
 126 int  main()  
 127 \{  
 128 cout << " Enter char one by one hicjiajia " << endl;  
 129 BiNode  \* T;  
 130 createTree(T);  
 131 cout << endl;  
 132   
 133 cout << " preOrderNoRe:  " ;preOrderNoRe(T);cout << endl;  
 134 cout << " inOrderNoRe:  " ;inOrderNoRe(T);cout << endl;  
 135 cout << " postOrderNoRe:  " ;postOrderNoRe(T);cout << endl;  
 136 system( " pause " );  
 137  return  0 ;  
 138 \}

![复制代码][copycode.gif]

运行结果如图：

![2010120512560016.png][]

转自[http://www.cnblogs.com/hicjiajia/archive/2010/08/27/1810055.html][http_www.cnblogs.com_hicjiajia_archive_2010_08_27_1810055.html]

[2010120512553664.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/3772bc549f8f4d539cd43ee825341c5d.png
[copycode.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/cf5f61c6fa7a462594833182dad047eb.gif
[2010120512560016.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/5e3f6b0634a947e69a03a170f690f50a.png
[http_www.cnblogs.com_hicjiajia_archive_2010_08_27_1810055.html]: http://www.cnblogs.com/hicjiajia/archive/2010/08/27/1810055.html