C++ 遍历二叉树实例详解

2叉数又叫红黑树，关于2叉数的遍历问题，有很多，一般有三种常用遍历方法：

(1)前序遍历(2)中序遍历(3)后续遍历

       以下是经典示例：

#include "stdafx.h" 
 
#include<stdio.h> 
#include<malloc.h> 
#include <math.h > 
#define MaxSize 20 
 
typedef struct BiTNode 
{ 
 int data; 
 struct BiTNode *lchild, *rchild; 
}BiTNode,*BiTree; 
 
//建立二叉树 
void CreateBiTree(BiTree *T) 
{ 
 char ch; 
 scanf("%c",&ch); 
 getchar(); 
 if(ch==' ') 
 { 
  printf("不产生子树。\n"); 
  *T=NULL; 
 } 
 else 
 { 
  if(!(*T=(BiTNode *)malloc(sizeof(BiTNode)))) 
  { 
   printf("分配空间失败"); 
   return; 
  }//生成一个新节点 
  (*T)->data = ch; 
  printf("产生左右子树。\n"); 
  CreateBiTree(&(*T)->lchild);        
  CreateBiTree(&(*T)->rchild);        
 } 
} 
 
//递归前序遍历 
void Preorder(BiTNode *T) 
{ 
 if(T) 
 { 
  printf("%c ",T->data); 
  Preorder(T->lchild);         
  Preorder(T->rchild);        
 } 
} 
 
//递归中序遍历 
void Inorder(BiTNode *T) 
{ 
 if(T) 
 { 
  Inorder(T->lchild); 
  printf("%c ",T->data); 
  Inorder(T->rchild); 
 } 
} 
 
//递归后序遍历 
void Postorder(BiTNode *T) 
{ 
 if(T) 
 { 
  Postorder(T->lchild); 
  Postorder(T->rchild); 
  printf("%c ",T->data); 
 } 
} 
 
//非递归前序遍历 
void NPreorder(BiTNode *T) 
{ 
 BiTNode *stack[MaxSize],*p; 
 int top=-1; 
 if(T) 
 { 
  top++; 
  stack[top]=T;     //根节点进栈 
  while(top>-1)     //栈不为空时循环 
  { 
   p=stack[top];    //退栈并访问该节点 
   top--; 
   printf("%c ",p->data); 
   if(p->rchild)    //右孩子进栈 
   { 
    top++; 
    stack[top]=p->rchild; 
   } 
   if(p->lchild)    //左孩子进栈 
   { 
    top++; 
    stack[top]=p->lchild; 
   } 
  }       
 } 
} 
 
//非递归中序遍历 
void NInorder(BiTNode *T) 
{ 
 BiTNode *stack[MaxSize],*p; 
 int top=-1; 
 p=T; 
 while(p||top!=-1) 
 { 
  if(p) 
  { 
   top++; 
   stack[top]=p; 
   p=p->lchild; 
  }        //根节点进栈，遍历左子树 
  else       //根节点退栈，访问根节点，遍历右子树 
  { 
   p=stack[top]; 
   top--; 
   printf("%c ",p->data); 
   p=p->rchild; 
  } 
 } 
} 
 
//非递归后序遍历 
void NPostorder(BiTNode *T) 
{ 
 BiTNode *stack[MaxSize],*p; 
 int flag,top=-1; 
 do 
 { 
  while(T) 
  { 
   top++; 
   stack[top]=T; 
   T=T->lchild; 
  }        //所有左节点进栈 
  p=NULL;      //p总是指向当前节点的前一个已经访问过的节点 
  flag=1;      //flag为1表示当前节点已经访问过了 
  while(top!=-1 && flag) 
  { 
   T=stack[top]; 
   if(T->rchild==p)   //右子树不存在或者已经被访问过时 
   { 
    printf("%c ",T->data); 
    top--; 
    p=T;     //调整p指针 
   } 
   else 
   { 
    T=T->rchild; 
    flag=0;    //调整访问标志 
   } 
  } 
 } while(top!=-1); 
} 
 
//层次遍历二叉树 
void Translever(BiTNode *T) 
{ 
 struct node 
 { 
  BiTNode *vec[MaxSize]; 
  int f,r;    //r为队尾，f为队头 
 }queue; 
 BiTNode *p; 
 p=T; 
 queue.f=0; 
 queue.r=0; 
 if(T) 
  printf("%c ", p->data); 
 queue.vec[queue.r]=p; 
 queue.r=queue.r+1; 
 while(queue.f<queue.r) 
 { 
  p=queue.vec[queue.f]; 
  queue.f=queue.f+1; 
  if(p->lchild) 
  { 
   printf("%c ",p->lchild->data); 
   queue.vec[queue.r]=p->lchild; 
   queue.r=queue.r+1; 
  } 
  if(p->rchild) 
  { 
   printf("%c ",p->rchild->data); 
   queue.vec[queue.r]=p->rchild; 
   queue.r=queue.r+1; 
  } 
 } 
 printf("\n"); 
} 
 
//求二叉树的深度 
int Depth(BiTNode *T) 
{ 
 int dep1,dep2; 
 if(T==NULL) 
  return(0); 
 else 
 { 
  dep1=Depth(T->lchild); 
  dep2=Depth(T->rchild); 
  if(dep1>dep2) 
   return(dep1+1); 
  else 
   return(dep2+1); 
 } 
} 
 
//输出二叉树 
void Disptree(BiTNode *T) 
{ 
 if(T) 
 { 
  printf("%c",T->data); 
  if(T->lchild || T->rchild) 
  { 
   printf("("); 
   Disptree(T->lchild); 
   if(T->rchild) 
    printf(","); 
   Disptree(T->rchild); 
   printf(")"); 
  } 
 } 
} 

main.cpp

void main() 
{ 
 BiTree T=NULL; 
 char j; 
 int sign = 1; 
 
 printf("本程序可以进行建立二叉树、递归与非递归先序、中序、后序遍历二叉树、层次遍历二叉树、输出二叉树的扩展序列的操作。\n"); 
 printf("请将二叉树的先序序列输入以建立二叉树，叶子节点用空格代替。\n"); 
 printf("您必须一个一个地输入字符。\n"); 
 while(sign) 
 { 
  printf("请选择: \n"); 
  printf("0.生成二叉树         1.求二叉树的深度\n"); 
  printf("2.递归先序遍历        3.非递归先序遍历\n"); 
  printf("4.递归中序遍历        5.非递归中序遍历\n"); 
  printf("6.递归后序遍历        7.非递归后序遍历\n"); 
  printf("8.层次遍历         9.输出二叉树的广义表形式\n"); 
  printf("q.退出程序\n"); 
  scanf("%c",&j); 
  getchar(); 
  switch(j) 
  { 
  case '0': 
   printf("生成二叉树:"); 
   CreateBiTree(&T); 
   printf("\n"); 
   printf("\n"); 
   break; 
  case '1': 
   if(T) 
   { 
    printf("此二叉树的深度为:"); 
    printf("%d",Depth(T)); 
    printf("\n"); 
    printf("\n"); 
   } 
   else printf("二叉树为空!\n"); 
   break; 
  case '2': 
   if(T) 
   { 
    printf("递归先序遍历二叉树:"); 
    Preorder(T); 
    printf("\n"); 
    printf("\n"); 
   } 
   else 
    printf("二叉树为空!\n"); 
   break; 
  case '3': 
   if(T) 
   { 
    printf("非递归先序遍历二叉树:"); 
    NPreorder(T); 
    printf("\n"); 
    printf("\n"); 
   } 
   else 
    printf("二叉树为空!\n"); 
   break; 
  case '4': 
   if(T) 
   { 
    printf("递归中序遍历二叉树:"); 
    Inorder(T); 
    printf("\n"); 
    printf("\n"); 
   } 
   else printf("二叉树为空!\n"); 
   break; 
  case '5': 
   if(T) 
   { 
    printf("非递归中序遍历二叉树:"); 
    NInorder(T); 
    printf("\n"); 
    printf("\n"); 
   } 
   else printf("二叉树为空!\n"); 
   break; 
  case '6': 
   if(T) 
   { 
    printf("递归后序遍历二叉树:"); 
    Postorder(T); 
    printf("\n"); 
    printf("\n"); 
   } 
   else printf("二叉树为空!\n"); 
   break; 
  case '7': 
   if(T) 
   { 
    printf("非递归后序遍历二叉树:"); 
    NPostorder(T); 
    printf("\n"); 
    printf("\n"); 
   } 
   else printf("二叉树为空!\n"); 
   break; 
  case '8': 
   if(T) 
   { 
    printf("层次遍历二叉树:"); 
    Translever(T); 
    printf("\n"); 
    printf("\n"); 
   } 
   else printf("二叉树为空!\n"); 
   break; 
  case '9': 
   if(T) 
   { 
    printf("输出二叉树:"); 
    Disptree(T); 
    printf("\n"); 
    printf("\n"); 
   } 
   else printf("二叉树为空!\n"); 
   break; 
  default: 
   sign=0; 
   printf("程序运行结束，按任意键退出!\n"); 
  } 
 } 
} 

示例：

转换成双向链表

先序列：H      F       C       D      M     I        N
中序列：C       F       D      H      I        M     N
后序列：C       D      F       I        N      M     H 

#include <iostream> 
using namespace std; 
struct BSTreeNode{ 
 char m_val; 
 BSTreeNode *m_pLeft; 
 BSTreeNode *m_pRight; 
}; 
BSTreeNode *pHead;//链表显示的头结点 
BSTreeNode *pListIndex;//游标指针 
void showOrderLiust(BSTreeNode *pCurrent); 
void createBSTree(BSTreeNode *&pCurrent,char ch) 
{ 
 if (NULL == pCurrent) { 
 pCurrent = new BSTreeNode; 
 pCurrent->m_val = ch; 
 pCurrent->m_pLeft = NULL; 
 pCurrent->m_pRight = NULL; 
 }else { 
 if (pCurrent->m_val > ch) { 
 createBSTree(pCurrent->m_pLeft,ch); 
 }else if (pCurrent->m_val < ch) { 
 createBSTree(pCurrent->m_pRight,ch); 
 } 
 else 
 { 
 return; 
 } 
 } 
} 
//遍历二叉树/*先序遍历*/ 
void PreOrderTraverse(BSTreeNode *pCurrent) 
{ 
 if (NULL == pCurrent) { 
 return; 
 } 
 
 if (NULL!=pCurrent) 
 { 
 //先遍历根节点 
 cout<<pCurrent->m_val<<endl; 
 //在遍历左节点 
 PreOrderTraverse(pCurrent->m_pLeft); 
 //在遍历右节点 
 PreOrderTraverse(pCurrent->m_pRight); 
 } 
 
} 
//中序遍历 
void InOrderTraverse(BSTreeNode *pCurrent) 
{ 
 if (NULL == pCurrent) { 
 return; 
 } 
 if (NULL != pCurrent->m_pLeft) { 
 InOrderTraverse(pCurrent->m_pLeft); 
 } 
 
 showOrderLiust(pCurrent); 
 //在遍历右节点 
 if (NULL != pCurrent->m_pRight) { 
 InOrderTraverse(pCurrent->m_pRight); 
 } 
} 
//后序遍历 
void EndOrderTraverse(BSTreeNode *pCurrent) 
{ 
 if (NULL == pCurrent) { 
 return; 
 } 
 if (NULL != pCurrent->m_pLeft) { 
 EndOrderTraverse(pCurrent->m_pLeft); 
 } 
 cout<<pCurrent->m_val<<endl; 
 //在遍历右节点 
 if (NULL != pCurrent->m_pRight) { 
 EndOrderTraverse(pCurrent->m_pRight); 
 } 
} 
/*该二元查找树转换成一个排序的双向链表。 
 要求不能创建任何新的结点，只调整指针的指向*/ 
void showOrderLiust(BSTreeNode *pCurrent) 
{ 
 pCurrent->m_pLeft = pListIndex; 
 if (NULL != pListIndex) { 
 pListIndex->m_pRight = pCurrent; 
 }else 
 { 
 pHead = pCurrent; 
 } 
 pListIndex = pCurrent; 
 cout<<pCurrent->m_val<<endl; 
} 
int main(int argc,char**argv) 
{ 
 BSTreeNode *pRoot = NULL; 
 pHead = NULL; 
 pListIndex = NULL; 
 createBSTree(pRoot,'H'); 
 createBSTree(pRoot,'F'); 
 createBSTree(pRoot,'C'); 
 createBSTree(pRoot,'D'); 
 createBSTree(pRoot,'M'); 
 createBSTree(pRoot,'I'); 
 createBSTree(pRoot,'N'); 
 PreOrderTraverse(pRoot); 
 InOrderTraverse(pRoot); 
 EndOrderTraverse(pRoot); 
 delete pRoot; 
 return 0; 
} 

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

# C++  # 遍历二叉树  # 二叉树遍历  # C++ 非递归实现二叉树的前中后序遍历  # C++树之遍历二叉树实例详解  # C++ 数据结构二叉树（前序/中序/后序递归、非递归遍历）  # C++基于先序、中序遍历结果重建二叉树的方法  # 一波二叉树遍历问题的C++解答实例分享  # C++非递归队列实现二叉树的广度优先遍历  # C++实现二叉树非递归遍历方法实例总结  # C++超详细实现二叉树的遍历  # 遍历  # 递归  # 二叉树  # 子树  # 为空  # 链表  # 转换成  # 过了  # 有很多  # 希望能  # 不存在  # 请选择  # 请将  # 谢谢大家  # 又叫  # 有三种  # 您必须  # 与非  # 红黑  # void 

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

相关推荐： 三星、SK海力士获美批准：可向中国出口芯片制造设备  Laravel怎么集成Vue.js_Laravel Mix配置Vue开发环境  google浏览器怎么清理缓存_谷歌浏览器清除缓存加速详细步骤  免费视频制作网站,更新又快又好的免费电影网站？  Laravel怎么实现模型属性的自动加密  如何基于云服务器快速搭建个人网站？  香港服务器建站指南：免备案优势与SEO优化技巧全解析  JavaScript如何实现路由_前端路由原理是什么  网站制作公司哪里好做,成都网站制作公司哪家做得比较好，更正规？  实现点击下箭头变上箭头来回切换的两种方法【推荐】  Laravel如何实现用户密码重置功能？（完整流程代码）  如何在阿里云购买域名并搭建网站？  专业商城网站制作公司有哪些,pi商城官网是哪个？  Laravel如何与Pusher实现实时通信？（WebSocket示例）  Laravel怎么导出Excel文件_Laravel Excel插件使用教程  ,怎么在广州志愿者网站注册？  Laravel怎么进行数据库事务处理_Laravel DB Facade事务操作确保数据一致性  html文件怎么打开证书错误_https协议的html打开提示不安全【指南】  如何用腾讯建站主机快速创建免费网站？  矢量图网站制作软件,用千图网的一张矢量图做公司app首页，该网站并未说明版权等问题，这样做算不算侵权？应该如何解决？  为什么php本地部署后css不生效_静态资源加载失败修复技巧【技巧】  如何快速搭建FTP站点实现文件共享？  Laravel怎么生成二维码图片_Laravel集成Simple-QrCode扩展包与参数设置【实战】  VIVO手机上del键无效OnKeyListener不响应的原因及解决方法  详解jQuery停止动画——stop()方法的使用  Laravel如何部署到服务器_线上部署Laravel项目的完整流程与步骤  Java遍历集合的三种方式  再谈Python中的字符串与字符编码（推荐）  如何确保西部建站助手FTP传输的安全性？  网易LOFTER官网链接 老福特网页版登录地址  弹幕视频网站制作教程下载,弹幕视频网站是什么意思？  详解Nginx + Tomcat 反向代理 负载均衡 集群 部署指南  如何在阿里云完成域名注册与建站？  JavaScript实现Fly Bird小游戏  ,交易猫的商品怎么发布到网站上去？  网站设计制作书签怎么做,怎样将网页添加到书签/主页书签/桌面？  如何在阿里云ECS服务器部署织梦CMS网站？  手机怎么制作网站教程步骤,手机怎么做自己的网页链接？  手机网站制作与建设方案,手机网站如何建设？  EditPlus中的正则表达式 实战(4)  5种Android数据存储方式汇总  Python数据仓库与ETL构建实战_Airflow调度流程详解  Laravel如何配置中间件Middleware_Laravel自定义中间件拦截请求与权限校验【步骤】  如何用AI帮你把自己的生活经历写成一个有趣的故事？  HTML5空格和nbsp有啥关系_nbsp的作用及使用场景【说明】  微信小程序 HTTPS报错整理常见问题及解决方案  Python文件异常处理策略_健壮性说明【指导】  如何在橙子建站中快速调整背景颜色？  网站建设保证美观性，需要考虑的几点问题！  教你用AI润色文章，让你的文字表达更专业