数据结构 二叉树的递归与非递归

技术  /  管理员 发布于 7年前   395

数据结构 二叉树的递归与非递归

实例代码：

#include <iostream> #include <queue> #include <stack> #include <assert.h> using namespace std; template<class T> struct BinaryTreeNode {   BinaryTreeNode<T>* _left;   BinaryTreeNode<T>* _right;   T _data;   BinaryTreeNode(const T& x)     :_left(NULL)     , _right(NULL)     , _data(x)   {}     }; template <class T> class BinaryTree {   typedef BinaryTreeNode<T> Node; public:   BinaryTree()     :_root(NULL)   {}   BinaryTree(T* a, size_t n, const T& invalid)   {     size_t index = 0;      _root=CreateTree(a, n, invalid, index);   }   BinaryTree(const BinaryTree<T>& t)   {      _root = _Copy(t._root);   }   BinaryTree<T>& operator=( BinaryTree<T>& t)   {     swap(_root,t._root);     return *this;   }   ~BinaryTree()   {       _DestroyTree(_root);   }   Node* CreateTree(const T* a, size_t n, const T& invalid, size_t& index)   {     assert(a);     Node* root = NULL;     if (index < n && a[index] != invalid)     {       root = new Node(a[index]);       root->_left = CreateTree(a, n, invalid, ++index);       root->_right = CreateTree(a, n, invalid, ++index);     }     return root;   } 

 先序遍历(递归法)  

 void PrevOrder()   {     _PrevOrder(_root);     cout << endl;   }   //先序遍历非递归   void PrevOrderNorR( )   {     Node* cur = _root;     stack< Node* >s;     while (cur||!s.empty())     {       while (cur)       {         cout << cur->_data << " ";         s.push(cur);         cur = cur->_left;       }       Node* top = s.top();       s.pop();       cur = top->_right;     }     cout << endl;   } 

后序遍历     

 void PostOrder()   {     _PostOrder(_root);     cout << endl;   }   //后序遍历非递归   void PostOrderNorR()   {        Node* cur = _root;       Node* prev = NULL;       stack< Node* >s;       while (cur || !s.empty())       {         while (cur)         {           s.push(cur);           cur = cur->_left;         }         Node* top = s.top();         if (NULL==top->_right && prev==top->_right)         {           cout << top->_data << " ";s.pop();prev = top;         }         cur = top->_right;       }       cout << endl;   }    //中序遍历   void InOrder()   {     _InOrder(_root);     cout << endl;   }   //中序遍历非递归   void InOrderNorR()   {     Node* cur = _root;     stack< Node* >s;     while (cur || !s.empty())     {       while (cur)       {         s.push(cur);         cur = cur->_left;       }       Node* top = s.top();       s.pop();       cout << top->_data << " ";       cur = top->_right;     }     cout << endl;   }    //节点个数   size_t Size()   {     return _Size(_root);   }   //叶子节点个数   size_t LeafSize()   {     return _LeafSize(_root);   }   //树的深度   size_t Depth()   {     return _Depth(_root);   }    size_t GetKLevel(size_t k)   {     return _GetKLevel(_root,k);   }   // 查找   Node* Find(size_t x)   {     return _Find(_root,x);   }   //层序遍历   void LevelOrder()   {     queue<Node*> q;     if (_root)     {       q.push(_root);     }     while (!q.empty())     {       Node* front = q.front();       cout << front->_data << " ";       q.pop();       if (front->_left)       {         q.push(front->_left);       }       if (front->_right)       {         q.push(front->_right);       }     }     cout << endl;   }    protected:   Node* _Copy(Node* root)   {     if (root==NULL)     {       return NULL;     }     Node* NewRoot = new Node(root->_data);     NewRoot->_left = _Copy(root->_left);     NewRoot->_right = _Copy(root->_right);     return NewRoot;   }   void _DestroyTree(Node* root)   {     if (NULL==root)     {       return;     }    _DestroyTree(root->_left);    _DestroyTree(root->_right);    delete root;   }   void _PrevOrder(BinaryTreeNode<T>* root)   {     if (root)     {       cout << root->_data << " ";        _PrevOrder(root->_left);       _PrevOrder(root->_right);     }     }   void _PostOrder(BinaryTreeNode<T>* root)   {     if (root)     {       _PostOrder(root->_left);       _PostOrder(root->_right);       cout << root->_data << " ";     }   }   void _InOrder(BinaryTreeNode<T>* root)   {     if (root)     {       _InOrder(root->_left);       cout << root->_data << " ";       _InOrder(root->_right);}   }   int _Size(BinaryTreeNode<T>* root)   {    if (root==0)    {      return 0;    }    return _Size(root->_left) + _Size(root->_right) + 1;   }   int _LeafSize(BinaryTreeNode<T>* root)   {     if (root==NULL)     {     return 0;     }     else if (root->_left == NULL&&root->_right == NULL)     {       return 1;     }     return _LeafSize(root->_left) + _LeafSize(root->_right);   }   int _Depth(Node* root)   {     if (root==NULL)     {       return 0;     }     int left = _Depth(root->_left);     int right = _Depth(root->_right);     return left > right ? left + 1 : right + 1;   }     int _GetKLevel(Node* root, size_t k)   {     assert(k>0);     if (root==NULL)     {       return 0;     }     else if (k==1)     {       return 1;     }     return _GetKLevel(root->_left, k - 1) + _GetKLevel(root->_right, k - 1);   }   Node* _Find(Node* root, const T& x)   {     if (root==NULL)     {       return NULL;     }     if (root->_data==x)     {       return root;     }     Node* ret = _Find(root->_left,x);     if (ret != NULL)       return ret;     return _Find(root->_right, x);   }    private:   BinaryTreeNode<T>* _root; };    

void TestBinaryTree() {   int array[10] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6 };   BinaryTree<int> t1(array,sizeof(array)/sizeof(array[0]),'#');   BinaryTree<int>t2(t1);   BinaryTree<int> t3;   t3 = t2;   t2.LevelOrder();   t3.LevelOrder();   t1.LevelOrder();   t1.PrevOrder();   t1.PrevOrderNorR();   t1.InOrder();   t1.InOrderNorR();   t1.PostOrder();   t1.PostOrderNorR();   cout << endl;   cout << t1.Size() << endl;   cout << t1.LeafSize() << endl;   cout << t1.Depth() << endl;    cout << t1.GetKLevel(2) << endl;   cout << t1.Find(2) << endl; } 

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！