这篇文章主要介绍了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++中如何遍历二叉树”这篇文章对大家有帮助，同时也希望大家多多支持亿速云，关注亿速云行业资讯频道，更多相关知识等着你来学习!
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
