欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  网络运营

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

程序员文章站 2022-07-04 18:29:29
数据结构 二叉树的递归与非递归 实例代码: #include #include #incl...

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

实例代码:

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

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