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

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

实例代码：

#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;
}

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