二叉树的非递归遍历

  1 #include <iostream>
  2 #include <vector>
  3 #include <string>
  4 #include <queue>
  5 #include <stack>
  6 #include <unordered_map>
  7 #include <map>
  8 #include <algorithm>
  9 using namespace std;
 10 
 11 struct TreeNode {
 12     int val;
 13     struct TreeNode *left;
 14     struct TreeNode *right;
 15     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 16 };
 17 
 18 //以前序遍历创建二叉树
 19 void CreateBiTree(TreeNode **T)//*T是指向BiTNode的指针
 20 {
 21     *T = new TreeNode(0);
 22     if (*T == NULL)//如果*T还是指向NULL，表示内存分配失败，退出程序
 23         exit(OVERFLOW);
 24     char ch;
 25     cin >> ch;
 26     if (ch == '#')
 27         *T = NULL;
 28     else
 29     {
 30         (*T)->val = ch;//*T指向的节点的data分配内容，即生成根节点
 31         CreateBiTree(&((*T)->left));//创建&(*T)->lchild临时变量，传入CreateBiTree，构造左子树
 32         CreateBiTree(&((*T)->right));//创建&(*T)->rchild临时变量，传入CreateBiTree，构造右子树
 33     }
 34 }
 35 
 36 //非递归前序遍历
 37 //不需要先进入到左根部，所以先访问父节点，再push右孩子入栈，再push左孩子入栈
 38 vector<char> preorderTraversal(TreeNode* root) {
 39     vector<char> result;
 40     stack<TreeNode*> s;
 41     if (root == NULL)
 42         return result;
 43     s.push(root);
 44     while (!s.empty()) {
 45         TreeNode* p = s.top();
 46         s.pop();
 47         result.push_back(p->val);//访问父节点
 48         if (p->right)//把父节点的右孩子入栈
 49             s.push(p->right);
 50         if (p->left)//把父节点的左孩子入栈
 51             s.push(p->left);
 52     }
 53     return result;
 54 }
 55 
 56 //非递归中序遍历
 57 //需要先进入到左孩子的最末端，直到左孩子为空，则访问该节点，再访问该节点的右孩子
 58 vector<char> inorderTraversal(TreeNode* root) {
 59     vector<char> result;
 60     stack<TreeNode*> s;
 61     if (root == NULL)
 62         return result;
 63     TreeNode* p = root;
 64     while (!s.empty() || p != NULL) {
 65         if (p != NULL) {
 66             //push非空节点和它的左孩子入栈
 67             s.push(p);
 68             p = p->left;
 69         }
 70         else {
 71             //访问该节点，然后访问右子树
 72             p = s.top();
 73             result.push_back(p->val);
 74             s.pop();
 75             p = p->right;
 76         }
 77     }
 78     return result;
 79 }
 80 
 81 //非递归后序遍历
 82 //用一个遍历记录刚刚访问过的节点，如果当前要访问的节点的右子树刚刚已经访问过了，才可以访问当前节点
 83 //否则如果如果是第一次访问该节点，如果重新入栈
 84 vector<char> postorderTraversal(TreeNode* root) {
 85     vector<char> result;
 86     if (root == NULL)
 87         return result;
 88     stack<TreeNode*> s;
 89     TreeNode* p = root;  //当前正访问的节点
 90     TreeNode* q;  //记录刚刚访问过的节点
 91     do {//把该节点的左孩子入栈，直到某节点没有左孩子
 92         while (p != NULL) {
 93             s.push(p);
 94             p = p->left;
 95         }
 96         q = NULL;
 97         while (!s.empty()) {
 98             p = s.top();
 99             s.pop();
100             if (p->right == q) {  //当右子树已经访问过了，才可以访问根
101                 result.push_back(p->val);
102                 q = p;  //记录刚刚访问过的节点
103             }
104             else {
105                 s.push(p); //第一次访问到该节点，需要将它重新入栈
106                 p = p->right;
107                 break;
108             }
109 
110         }
111     } while (!s.empty());
112     return result;
113 }
114 
115 //打印vector
116 void print(vector<char> v)
117 {
118     for (int i = 0;i < v.size();i++)
119         cout << v[i];
120 }
121 
122 //测试
123 int main()
124 {
125     TreeNode **pp;//定义指向BiTNode的二级指针pp
126     TreeNode *p;//定义指向BiTNode的指针p
127     pp = &p;//pp指向p
128     p = NULL;//初始化p指向NULL
129     CreateBiTree(pp);//传入指向p的地址，创建二叉树,输入ABD##E##CF##G##
130 
131     vector<char> preorder;
132     vector<char> inorder;
133     vector<char> postorder;
134     preorder = preorderTraversal(p);
135     inorder = inorderTraversal(p);
136     postorder = postorderTraversal(p);
137 
138     cout << "非递归前序遍历" << endl;
139     print(preorder);
140     cout << endl;
141     cout << "非递归中序遍历" << endl;
142     print(inorder);
143     cout << endl;
144     cout << "非递归后序遍历" << endl;
145     print(postorder);
146     cout << endl;
147     return 0;
148 }