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

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