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

实例代码：

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

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

# 数据结构  # 二叉树的递归与非递归  # 二叉树的递归  # C++ 数据结构二叉树（前序/中序/后序递归、非递归遍历）  # C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法  # C++基于递归和非递归算法判定两个二叉树结构是否完全相同(结构和数据都相同)  # C++基于递归和非递归算法求二叉树镜像的方法  # C++非递归队列实现二叉树的广度优先遍历  # C++非递归建立二叉树实例  # C语言数据结构之二叉树的非递归后序遍历算法  # 递归  # 遍历  # 希望能  # 谢谢大家  # 与非  # 二叉树  # _root  # public  # invalid  # size_t  # Node  # NULL  # amp  # typedef  # BinaryTree  # index  # root  # _DestroyTree  # br 

相关栏目： 【 网站优化151355 】 【 网络推广146373 】 【 网络技术251813 】 【 AI营销90571 】

相关推荐： 网站制作怎么样才能赚钱,用自己的电脑做服务器架设网站有什么利弊，能赚钱吗？  零基础网站服务器架设实战：轻量应用与域名解析配置指南  Laravel如何使用Eloquent进行子查询  如何用低价快速搭建高质量网站？  Laravel Debugbar怎么安装_Laravel调试工具栏配置指南  EditPlus 正则表达式 实战(3)  Win11怎么设置默认图片查看器_Windows11照片应用关联设置  如何确保FTP站点访问权限与数据传输安全？  如何在IIS服务器上快速部署高效网站？  网站广告牌制作方法,街上的广告牌，横幅，用PS还是其他软件做的？  微信小程序 闭包写法详细介绍  如何用AI一键生成爆款短视频文案？小红书AI文案写作指令【教程】  jquery插件bootstrapValidator表单验证详解  黑客入侵网站服务器的常见手法有哪些？  香港服务器租用费用高吗？如何避免常见误区？  JavaScript如何实现错误处理_try...catch如何捕获异常？  如何快速启动建站代理加盟业务？  如何构建满足综合性能需求的优质建站方案？  如何快速搭建高效香港服务器网站？  移动端脚本框架Hammer.js  Laravel如何处理和验证JSON类型的数据库字段  Android GridView 滑动条设置一直显示状态(推荐)  微信小程序 require机制详解及实例代码  Laravel如何实现密码重置功能_Laravel密码找回与重置流程  网站制作软件有哪些,制图软件有哪些？  如何在建站宝盒中设置产品搜索功能？  Laravel如何使用Facades（门面）及其工作原理_Laravel门面模式与底层机制  如何在阿里云虚拟机上搭建网站？步骤解析与避坑指南  七夕网站制作视频,七夕大促活动怎么报名？  网站制作报价单模板图片,小松挖机官方网站报价？  如何快速生成高效建站系统源代码？  大同网页,大同瑞慈医院官网？  Laravel用户密码怎么加密_Laravel Hash门面使用教程  海南网站制作公司有哪些,海口网是哪家的？  谷歌浏览器如何更改浏览器主题 Google Chrome主题设置教程  Laravel如何设置定时任务（Cron Job）_Laravel调度器与任务计划配置  如何在建站主机中优化服务器配置？  Laravel如何使用Service Container和依赖注入？（代码示例）  如何快速搭建支持数据库操作的智能建站平台？  laravel怎么为API路由添加签名中间件保护_laravel API路由签名中间件保护方法  Laravel怎么使用Markdown渲染文档_Laravel将Markdown内容转HTML页面展示【实战】  怎样使用JSON进行数据交换_它有什么限制  javascript和jQuery中的AJAX技术详解【包含AJAX各种跨域技术】  重庆市网站制作公司,重庆招聘网站哪个好？  Laravel如何实现多级无限分类_Laravel递归模型关联与树状数据输出【方法】  Laravel如何使用缓存系统提升性能_Laravel缓存驱动和应用优化方案  5种Android数据存储方式汇总  如何挑选高效建站主机与优质域名？  JavaScript模板引擎Template.js使用详解  Swift开发中switch语句值绑定模式