二叉树的建立先及二叉树的先序、中序、后序遍历
运行结果：建立：
先序：
后续：
中序：
完整代码：
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstring>
using namespace std;
#define OVERFLOW -2
//二叉树的二叉链表存储表示
typedef struct BiTNode{
char data;
struct BiTNode *lchild, *rchild;//左右孩子指针
}BiTNode,*BiTree;
BiTNode* CreateTree(BiTNode *&T);//创建二叉树
void PreOrder(BiTNode *T);//先序遍历
void PostOrder(BiTNode *T);//后序遍历
void InOrder(BiTNode *T);//中序遍历
int main()
{
BiTNode *T = NULL;
char ch1, ch2;
ch1 = 'y';
while (ch1 == 'y')
{
cout << "-----------二叉树------------" << endl;
cout << "-------1.创建二叉树 ------" << endl;
cout << "-------2.先序遍历二叉树------" << endl;
cout << "-------3.后序遍历二叉树------" << endl;
cout << "-------4.中序遍历二叉树------" << endl;
cout << "-------0.返回 ------" << endl;
cout << "-------请选择菜单号 ------" << endl;
cin >> ch2;
getchar();
cout << endl;
switch (ch2)
{
case'1':
cout << "请输入按先序创建二叉树的结点序列（#表示结点为空）：";
CreateTree(T);
cout << "二叉树创建成功"<<endl;
break;
case'2':
cout << "该二叉树的先序遍历为：" << endl;
PreOrder(T);
cout << endl;
break;
case'3':
cout << "该二叉树的后序遍历为：" << endl;
PostOrder(T);
cout << endl;
break;
case'4':
cout << "该二叉树的中序遍历为：" << endl;
InOrder(T);
cout << endl;
break;
case'0':
ch1 = 'n';
break;
default:
cout << "输入有误" << endl;
}//switch
}//while
return 0;
}
BiTNode* CreateTree(BiTNode *&T)//创建
{
char ch;
scanf("%c", &ch);
if (ch == '#')
T = NULL;
else
{
if (!(T = (BiTNode *)malloc(sizeof(BiTNode))))
exit(OVERFLOW);
T->data = ch;//生成根节点
T->lchild=CreateTree(T->lchild);//构建左子树
T->rchild = CreateTree(T->rchild);//构建右子树
}
return T;
}
void PreOrder(BiTNode *T)//先序遍历
{
if (T)
{
cout << T->data;//访问根节点
PreOrder(T->lchild);//左子树
PreOrder(T->rchild);//右子树
}
}
void PostOrder(BiTNode *T)//后序遍历
{
if (T)
{
PostOrder(T->lchild);//左子树
PostOrder(T->rchild);//右子树
cout << T->data;//访问根
}
}
void InOrder(BiTNode *T)//中序遍历
{
if (T)
{
PostOrder(T->lchild);//左子树
cout << T->data;//访问根
PostOrder(T->rchild);//右子树
}
}
二叉树的创建以及遍历都是使用递归的思想来进行的
文档来源：51CTO技术博客https://blog.51cto.com/u_15098794/3035591
页:
[1]