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

2020-02-24 14:25:40

字体：大中小

来源：转载

供稿：网友

二叉树主要用于解决寻找线性前体和节点后继不方便的问题，其实它只增加了两个标记域，下文是武林技术频道小编为大家带来的详解C++ 遍历二叉树实例介绍，一起去看看吧。

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++ 遍历二叉树实例介绍，你学习到了吗?如果你想了解其他的专业知识，建议你来js.Vevb.com进行了解。

上一篇：详解c++快速排序的方法

下一篇：c++素数筛选法