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

原文地址为:
二叉树后序遍历(非递归)


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

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


 

这里我们约定:空的节点用空格表示,按照前序遍历来创建树!

   1 // main.cpp

  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 
}

 运行结果如图:

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

 

转载请注明本文地址:
二叉树后序遍历(非递归)

    原文作者:dearbaba_8520
    原文地址: https://blog.csdn.net/dearbaba_8520/article/details/81661663
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞