二叉树中序遍历的非递归实现

 1 #include<iostream>
 2 #include<stack>
 3 
 4 using namespace std;
 5 
 6 //双孩子表示法
 7 typedef struct treenode
 8 {
 9     treenode* leftchild;
10     treenode* rightchild;
11     int data;
12 }Treenode,*pTreenode;
13 
14 
15 //树中序遍历的非递归方法
16 //算法思想：
17 //1.如果节点有左子树，该节点入栈；如果节点没有左子树，访问该节点 
18 //2.如果节点有右子树，重复步骤1；如果节点没有右子树（节点访问完毕），根据栈顶指示回退，访问栈顶元素，并访问右子树，重复步骤1
19 //3.如果栈为空，则遍历结束
20 //注意：入栈的节点表示该节点本身没有被访问过，同时右子树也没有被访问过
21 void Midrev(pTreenode root,stack<pTreenode> &s)
22 {
23     if(!root)
24     {
25         return;
26     }
27 
28     //步骤1
29     if(root->leftchild)
30     {
31         s.push(root);
32         Midrev(root->leftchild,s);
33     }
34 
35     else if(!root->leftchild)
36     {
37         cout<<root->data<<" ";
38     }
39 
40     //步骤2.3
41     while(!s.empty())//判断的条件即是步骤3，这句while()是整个程序的精华！
42     {
43         if(root->rightchild)
44         {
45             Midrev(root->rightchild,s);
46         }
47 
48         else if(!root->rightchild)
49         {
50             if(!s.empty())
51             {
52                 pTreenode befroot=s.top();
53                 cout<<befroot->data<<" ";
54                 s.pop();
55                 Midrev(befroot->rightchild,s);
56             }
57         }
58     }
59 }
60 
61 
62 int main()
63 {
64     //建立一棵树
65     Treenode t1,t2,t3,t4,t5,t6,t7;//这里不要定义成pTreenode t1的形式，不然下面memset()时会出错
66     memset(&t1,0,sizeof(Treenode));
67     memset(&t2,0,sizeof(Treenode));
68     memset(&t3,0,sizeof(Treenode));
69     memset(&t4,0,sizeof(Treenode));
70     memset(&t5,0,sizeof(Treenode));
71     memset(&t6,0,sizeof(Treenode));
72     memset(&t7,0,sizeof(Treenode));
73 
74     t1.data=1;
75     t2.data=2;
76     t3.data=3;
77     t4.data=4;
78     t5.data=5;
79     t6.data=6;
80     t7.data=7;
81     t1.data=1;
82 
83     t1.leftchild=&t2;
84     t1.rightchild=&t3;
85     t2.leftchild=&t4;
86     t3.leftchild=&t5;
87     t3.rightchild=&t6;
88     t4.rightchild=&t7;
89 
90     //创建一个栈，用来存储树中的元素
91     stack<pTreenode> sta;
92 
93     //中序遍历的非递归实现
94     cout<<"中序遍历的非递归实现：";
95     Midrev(&t1,sta);
96     cout<<endl;
97 
98     return 0;
99 }