树的中序非递归遍历

源码：

  1 #include <iostream>
  2 #include <stack>
  3 using namespace std;
  4 
  5 // 二叉链表表示法
  6 typedef struct _tag_BitTNode
  7 {
  8     // 数据域
  9     char data;
 10     // 左孩子
 11     struct _tag_BitTNode* lChild;
 12     // 右孩子
 13     struct _tag_BitTNode* rChild;
 14 }BiTNode;
 15 
 16 /*
 17     步骤1：
 18     如果结点有左子树，该结点入栈；
 19     如果结点没有左子树，访问该结点；
 20     步骤2：
 21     如果结点有右子树，重复步骤1；
 22     如果结点没有右子树（结点访问完毕），根据栈顶指示回退，访问栈顶元素，并访问右子树，重复步骤1
 23     如果栈为空，表示遍历结束。
 24 
 25 */
 26 // 步骤1
 27 BiTNode* FindLeft(BiTNode* root, stack<BiTNode*> &st)
 28 {
 29     if (root == NULL)
 30     {
 31         return NULL;
 32     }
 33     // 寻找最左的节点
 34     while (root->lChild != NULL)
 35     {
 36         // 该节点入栈
 37         st.push(root);
 38         // 当前指针指向左孩子
 39         root = root->lChild;
 40     }
 41     // 返回没有左孩子的节点
 42     return root;
 43 }
 44 
 45 void MyOrder(BiTNode* root)
 46 {
 47     if (root == NULL)
 48     {
 49         return;
 50     }
 51     stack<BiTNode*> st;
 52     BiTNode* left = FindLeft(root, st);
 53 
 54     while (left != NULL)
 55     {
 56         // 访问
 57         cout << left->data;
 58         // 判断left又没有右子树
 59         if (left->rChild)
 60         {
 61             left = FindLeft(left->rChild, st);
 62         }
 63         else
 64         {
 65             // 没有右子树
 66             // 判断栈是否为空
 67             if (!st.empty())
 68             {
 69                 // 取出栈顶元素
 70                 left = st.top();
 71                 // 弹出
 72                 st.pop();
 73             }
 74             else
 75             {
 76                 cout << "遍历结束!" << endl;
 77                 break;
 78             }
 79         }
 80     }
 81 }
 82 
 83 
 84 // 井号法创建树 -- 先序遍历的方式
 85 BiTNode* createTree()
 86 {
 87     char c;
 88     // 输入节点数据
 89     cin >> c;
 90     if (c == '#')
 91     {
 92         return NULL;
 93     }
 94     // 先创建根节点
 95     BiTNode* root = new BiTNode;
 96     // 初始化
 97     root->data = c;
 98     // 创建左子树
 99     root->lChild = createTree();
100     // 创建右子树
101     root->rChild = createTree();
102 
103     return root;
104 }
105 // 销毁树
106 void destroyTree(BiTNode* root)
107 {
108     // 后序遍历的方式销毁 - 必须
109     if (root == NULL)
110     {
111         return;
112     }
113     // 销毁左子树
114     destroyTree(root->lChild);
115     // 销毁右子树
116     destroyTree(root->rChild);
117     cout << root->data << endl;
118     // 释放根节点
119     delete root;
120 }
121 
122 
123 void main()
124 {
125     // 构建一颗二叉树
126     BiTNode nodeA, nodeB, nodeC, nodeD, nodeE, nodeF, nodeG;
127     // 初始化
128     memset(&nodeA, 0, sizeof(BiTNode));
129     memset(&nodeB, 0, sizeof(BiTNode));
130     memset(&nodeC, 0, sizeof(BiTNode));
131     memset(&nodeD, 0, sizeof(BiTNode));
132     memset(&nodeE, 0, sizeof(BiTNode));
133     memset(&nodeF, 0, sizeof(BiTNode));
134     memset(&nodeG, 0, sizeof(BiTNode));
135 
136     // 构建树
137     nodeA.data = 'A';
138     nodeA.lChild = &nodeB;
139     nodeA.rChild = &nodeC;
140 
141     nodeB.data = 'B';
142     nodeB.lChild = &nodeD;
143     nodeB.rChild = &nodeE;
144 
145     nodeC.data = 'C';
146     nodeC.lChild = &nodeF;
147     nodeC.rChild = &nodeG;
148 
149     nodeD.data = 'D';
150     nodeE.data = 'E';
151     nodeF.data = 'F';
152     nodeG.data = 'G';
153 
154     printf("树的中序非递归: 
");
155     MyOrder(&nodeA);
156 
157     //
158     cout << "井号法创建树: ABDH#K###E##CFI###G#J##";
159     BiTNode* root = createTree();
160     cout << "中序遍历: ";
161     MyOrder(root);
162     cout << endl;
163 
164     destroyTree(root);
165 
166     system("pause");
167 
168 }
树的中序非递归遍历

源码：

运行结果：
