c++考研复习之非递归前序中序后序遍历二叉树

 1 /*
 2  * =====================================================================================
 3  *
 4  *       Filename:  Stack.h
 5  *
 6  *    Description:  栈类
 7  *
 8  *        Version:  1.0
 9  *        Created:  2013年11月13日 21时38分49秒
10  *       Revision:  none
11  *       Compiler:  gcc
12  *
13  *         Author:  dependmyse (lxy), dependmyse@gmail.com
14  *        Company:  TianJin University
15  *
16  * =====================================================================================
17  */
18 #ifndef _STACK_H_
19 #define _STACK_H_
20 #include <iostream> 
21 #define MAXSIZE 50
22 #include <iostream>
23 using namespace std;
24 //定义二叉树结构体
25 typedef struct TreeNode {
26     char data;
27     TreeNode *lChild;
28     TreeNode *rChild;
29 }TreeNode,*Tree;
30 
31 class Stack{
32     public:
33         int getTop();
34         void push(TreeNode *data);
35         TreeNode * pop();
36         bool isStackEmpty();
37         bool isStackFull();
38         void initStack();
39         TreeNode *getTopPtr();
40     private:
41         int top;
42         Tree *content;
43 };
44 void Stack::initStack()
45 {
46     content=new Tree[MAXSIZE]; 
47     top=-1;
48 }
49 
50 bool Stack::isStackEmpty()
51 {
52     return top==-1;
53 }
54 bool Stack::isStackFull()
55 {
56     return top==MAXSIZE;
57 }
58 void Stack::push(TreeNode *data)
59 {
60    if(isStackFull()) 
61    {
62        cout<<"栈已满，无法继续插入"<<endl;
63        return;
64    }else
65    {
66        this->content[++top]=data;
67    }
68 }
69 TreeNode* Stack::pop()
70 {
71     if(isStackEmpty())
72     {
73         cout<<"栈已空，无法继续删除"<<endl;
74         return NULL;
75     }else
76     {
77         return this->content[top--];
78     }
79 }
80 int Stack::getTop()
81 {
82     return this->top;
83 }
84 TreeNode* Stack::getTopPtr()
85 {
86     return this->content[top];
87 }
88 #endif

  1 /*
  2  * =====================================================================================
  3  *
  4  *       Filename:  TravelTreeByStack.cpp
  5  *
  6  *    Description: 使用栈分别前中后对二叉树进行遍历 
  7  *
  8  *        Version:  1.0
  9  *        Created:  2013年11月13日 21时22分39秒
 10  *       Revision:  none
 11  *       Compiler:  gcc
 12  *
 13  *         Author:  dependmyse (lxy), dependmyse@gmail.com
 14  *        Company:  TianJin University
 15  *
 16  * =====================================================================================
 17  */
 18 #include "Stack.h"
 19 #include <iostream>
 20 using namespace std;
 21 /*typedef struct TreeNode {
 22     char data;
 23     TreeNode *lChild;
 24     TreeNode *rChild;
 25 }TreeNode;*/
 26 
 27 //递归创建二叉树
 28 TreeNode *createTree()
 29 {
 30     char data;
 31     TreeNode *treeNode;
 32     cin>>data;
 33     if(data!='#')
 34     {
 35         treeNode=new TreeNode();
 36         treeNode->data=data;
 37         cout<<"输入左节点的值"<<endl;
 38         treeNode->lChild=createTree();
 39         cout<<"输入右节点的值"<<endl;
 40         treeNode->rChild=createTree();
 41     }else{
 42         treeNode=NULL;
 43     }
 44     return treeNode;
 45 }
 46 void visit(TreeNode *treeNode)
 47 {
 48     cout<<treeNode->data<<" ";
 49 }
 50 //递归先序遍历
 51 void preOrder(TreeNode *root)
 52 {
 53     if(root!=NULL)
 54     {
 55         visit(root);
 56         preOrder(root->lChild);
 57         preOrder(root->rChild);
 58     }
 59 }
 60 //非递归先序遍历
 61 void preOrderByStack(TreeNode *root)
 62 {
 63     Stack stack;
 64     stack.initStack();
 65     TreeNode *p=root;
 66     TreeNode *temp;
 67     while(p!=NULL||!stack.isStackEmpty())
 68     {
 69         while(p!=NULL)
 70         {
 71             visit(p);
 72             stack.push(p);
 73             p=p->lChild;
 74         }
 75         if(!stack.isStackEmpty())
 76         {
 77             temp=stack.pop();      
 78             p=temp->rChild;
 79         }
 80     }
 81 }
 82 //非递归中序遍历
 83 void inOrderByStack(TreeNode *root)
 84 {
 85     Stack stack;
 86     stack.initStack();
 87     TreeNode *p=root;
 88     TreeNode *temp;
 89     while(p!=NULL||!stack.isStackEmpty())
 90     {
 91         while(p!=NULL)
 92         {
 93             stack.push(p);
 94             p=p->lChild;
 95         }
 96         if(!stack.isStackEmpty())
 97         {
 98             temp=stack.pop();
 99             visit(temp);
100             p=temp->rChild;
101         }
102     }
103 }
104 //非递归后续遍历
105 void postOrder(TreeNode *root)
106 {
107     Stack stack;
108     stack.initStack();
109     //定义标志变量，标记结点是第几次被访问，第二次被访问时
110     //标记变量设为1输出，否则为0
111     int flags[MAXSIZE];
112     TreeNode *p=root;
113     TreeNode *temp;
114     while(p!=NULL||!stack.isStackEmpty())
115     {
116         while(p!=NULL)
117         {
118             stack.push(p);
119             flags[stack.getTop()]=0;
120             p=p->lChild;
121         }
122         while(!stack.isStackEmpty()&&flags[stack.getTop()]==1)
123         {
124             temp=stack.pop();
125             visit(temp);
126         }
127         if(!stack.isStackEmpty())
128         {
129             temp=stack.getTopPtr();    
130             flags[stack.getTop()]=1;
131             p=temp->rChild;
132         }
133     }
134 }
135 int main()
136 {
137     TreeNode *treeNode=createTree();
138     //preOrder(treeNode);
139     cout<<"非递归先序遍历"<<endl;
140     preOrderByStack(treeNode);
141     cout<<endl;
142     cout<<"非递归中序遍历"<<endl;
143     inOrderByStack(treeNode); 
144     cout<<endl;
145     cout<<"非递归后续遍历"<<endl;
146     postOrder(treeNode);
147     cout<<endl;
148     return 0;
149 }

程序运行效果如下图所示