二叉树的非递归遍历

忘是亡心i 2022-06-16 05:40 242阅读 0赞

二叉树的非递归实现  
在解决二叉树的问题的时候要善于把树划分成为根左子树和右子树  
前序遍历：根–>左–>右  
中序遍历：左–>根–>右  
后序遍历：左–>右–>根  
这三种遍历的方式的思想都是一样的，借助栈来保存，利用栈先进后出的特性  
![这里写图片描述][SouthEast]  
![这里写图片描述][SouthEast 1]  
中序遍历也是同样的思想，而后序遍历大致也是同样的方式不过必须要做一个标记避免陷入死循环，因为只有右子树访问完了，才能将根节点访问并且pop出去，那么此时就需要加一个标记判断右子树是否访问完了，否则就会一直访问右子树，这样程序就会陷入死循环

#include<iostream>
    #include<stdlib.h>
    #include<stack>
    using namespace std;
    template<class T>
    struct BinaryTreeNode
    {
          BinaryTreeNode( const T &x)
          :Lchild( NULL)
          ,Rchild( NULL)
          , value( x)
          , flag(0)
          {
    
          }
           T value;
           BinaryTreeNode<T > *Lchild;
           BinaryTreeNode<T > *Rchild;
           size_t flag;
    };
    template<class T>
    class BinaryTree
    {
    public:
           typedef BinaryTreeNode <T> Node;
          BinaryTree()
          {
                _root = NULL;
          } //构建一颗空树
          BinaryTree( const T *arr, size_t size , T invalid)
          {
                 size_t index = 0;
                _root = _CreatBinaryTree( arr, size , invalid, index);
          }
           void PrevOrder()
          {
                 stack<Node *>s;
                 Node*cur = _root;
                 while (cur || !s.empty())
                {
                       while (cur)
                      {
                            cout << cur->value << " ";
                            s.push(cur);
                            cur = cur->Lchild;
                      }
                       Node*top = s.top();
                      s.pop();
                      cur = top->Rchild;
                }
                cout << endl;
          }
           void InOrder()
          {
                 stack<Node *>s;
                 Node*cur = _root;
                 while (cur || !s.empty())
                {
                       while (cur)
                      {
                            s.push(cur);
                            cur = cur->Lchild;
                      }
                       Node*top = s.top();
                      cout << top->value << " ";
                      s.pop();
                      cur = top->Rchild;
                }
                cout << endl;
          }
           void PostOrder()//后序遍历
          {
                 stack<Node *>s;
                 Node*cur = _root;
                 while (cur || !s.empty())
                {
                       while (cur)
                      {
                            s.push(cur);
                            cur = cur->Lchild;
                      }
                       Node*top = s.top();
                       if (top->Rchild == NULL )
                      {
                            cout << top->value<< " ";
                            top->flag = 1;
                            s.pop();
                      }
                       else
                      {
                             if (top->Rchild->flag != 1)
                            {
                                  cur = top->Rchild;
                            }
                             else
                            {
                                  cout << top->value << " ";
                                  s.pop();
                            }
    
                      }
                }
          }
    protected:
           Node* _CreatBinaryTree(const T*arr, size_t size , T invalid, size_t &index )
          {
                 Node *root = NULL ;
                 if (index < size&& arr[index ] != invalid)
                {
                      root = new Node (arr[index]);
                      root->Lchild = _CreatBinaryTree(arr , size, invalid, ++index);
                      root->Rchild = _CreatBinaryTree(arr , size, invalid, ++index);
                }
                 return root;
          }
    protected:Node * _root;
    };
    int main()
    {
           int array1[10] = { 1, 2, 3, '#' , '#', 4, '#', '#' , 5, 6 };
           BinaryTree<int >t1(array1,10,'#');
          t1.PrevOrder();
          t1.InOrder();
          t1.PostOrder();
          system( "pause");
           return 0;
    }

[SouthEast]: /images/20220616/3a4d82b410ec4b508abb3aac9e34c669.png
[SouthEast 1]: /images/20220616/d92db37af4cd4450a6e14970aa87a623.png