用递归算法先序中序后序遍历二叉树

2025-02-07 21:18:21

推荐回答（3个）

回答1：

1、先序

void PreOrderTraversal(BinTree BT)

{

if( BT )

{

printf(“%d\n”, BT->Data); //对节点做些访问比如打印

PreOrderTraversal(BT->Left); //访问左儿子

PreOrderTraversal(BT->Right); //访问右儿子

}

2、中序

void InOrderTraversal(BinTree BT)

{

if(BT)

{

InOrderTraversal(BT->Left);

printf("%d\n", BT->Data);

InOrderTraversal(BT->Right);

}

3、后序

void PostOrderTraversal(BinTree BT)

{

if (BT)

{

PostOrderTraversal(BT->Left);

PostOrderTraversal(BT->Right);

printf("%d\n", BT->Data);

}

扩展资料：

注意事项

1、前序遍历

从整棵二叉树的根结点开始，对于任意结点VV，访问结点VV并将结点VV入栈，并判断结点VV的左子结点LL是否为空。若LL不为空，则将LL置为当前结点VV；若LL为空，则取出栈顶结点，并将栈顶结点的右子结点置为当前结点VV。

2、中序遍历

从整棵二叉树的根结点开始，对于任一结点VV，判断其左子结点LL是否为空。若LL不为空，则将VV入栈并将L置为当前结点VV；若LL为空，则取出栈顶结点并访问该栈顶结点，然后将其右子结点置为当前结点VV。重复上述操作，直到当前结点V为空结点且栈为空，遍历结束。

3、后序遍历

将整棵二叉树的根结点入栈，取栈顶结点VV，若VV不存在左子结点和右子结点，或VV存在左子结点或右子结点，但其左子结点和右子结点都被访问过了，则访问结点VV，并将VV从栈中弹出。若非上述两种情况，则将VV的右子结点和左子结点依次入栈。重复上述操作，直到栈为空，遍历结束。

回答2：

#include
#include
#include
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef char TElemType;
typedef struct Btn{
TElemType data;
struct Btn *lchild , *rchild;
}BTN ,*BT;
int CreateBT(BT &T) {
//按前序遍历规则创建二叉树，请输入结点
//（不存在的结点用*代替），如"AB*DG***CEM**N**F*X**"
char ch;
getchar();
printf("\n请输入二叉树的元素\n");
scanf("%c",&ch);
if(ch == '*')T = NULL;
else {
if(!(T = (BTN *)malloc(sizeof(BTN)))) exit(OVERFLOW);
T->data = ch;
CreateBT(T->lchild);
CreateBT(T->rchild);
}
return OK;
}//创建二叉树
int PreOrderT(BT T ) {
//前序遍历二叉树 T：打印每个结点的数据域一次且仅一次
if (T != NULL) {
printf("%c \n", T -> data);
PreOrderT( T -> lchild ) ;
PreOrderT( T -> rchild ) ;
}
return OK;
}//先序遍历二叉树
int InOrderT(BT T) {
//后序遍历二叉树 T：打印每个结点的数据域一次且仅一次
if (T != NULL) {
InOrderT( T -> lchild ) ;
printf("%c \n", T -> data);
InOrderT( T -> rchild ) ;
}
return OK;
}//后序遍历二叉树 T
int PostOrderT(BT T) {
//后序遍历二叉树 T：打印每个结点的数据域一次且仅一次
if (T != NULL) {
PostOrderT( T -> lchild ) ;
PostOrderT( T -> rchild ) ;
printf("%c \n", T -> data);
}
return OK;
}//后序遍历二叉树 T
BT LocateElem(BT T , TElemType e){
//编写算法在二叉树T(二叉链表存储结构)中查找数据元素e。
//查找成功返回结点地址；否则返回NULL
BT s;
if (T->data == e || T == NULL ) return (T);
s = LocateElem ( T -> lchild, e ) ;
if ( s != NULL ) return (s);
else return ( LocateElem ( T -> rchild , e ) ) ;
}//中查找数据元素e
int BTnum(BT T){
// 编写算法统计二叉树T(二叉链表存储结构)的结点总数
int i=0;
if (T != NULL) {
InOrderT( T -> lchild ) ;
i++;
InOrderT( T -> rchild ) ;
}
return i;
}
int BTdepth(BT T){
//编写算法求二叉树T(二叉链表存储结构)的深度。
int rd,ld;
if(!T) return 0;
else { ld=BTdepth(T->lchild);
rd=BTdepth(T->rchild);
if(ld>rd) return rd+1;
else return ld+1;
}
}
/*int LevelElem(BT T,TElemType e){
//求e在T中的层次。如果不存在，返回值为0；否则，返回值为层次。
int rd,ld;
if(!T) return 0;
else
if(e!=T->data){
ld=BTdepth(T->lchild);
rd=BTdepth(T->rchild);
if(ld>rd)
return rd+1;
else return ld+1;
}
}*/
int main(){
BT T;
TElemType e;
int /*Te,*/j;
while(j){
printf("\n请输入你要的功能\n");
printf("-----华丽的分割线------\n");
printf("1:按前序遍历规则创建二叉树\n");
printf("2:前序遍历二叉树 T\n");
printf("3:中序遍历二叉树 T\n");
printf("4:后序遍历二叉树 T\n");
printf("5:查找数据元素e\n");
printf("6:统计二叉树T的结点总数\n");
printf("7:编写算法求二叉树T的深度\n");
printf("0:退出程序\n");
// printf("8:求e在T中的层次\n");
printf("-----华丽的分割线------\n");
scanf("%d",&j);
switch(j){
case 1:CreateBT(T);break;
case 2:PreOrderT(T);break;
case 3:InOrderT(T);break;
case 4:PostOrderT(T);break;
case 5:
printf("\n请输入想要查找的元素\n");
scanf("%c",&e);
LocateElem(T,e);break;
case 6: BTnum(T);
case 7:BTdepth(T);break;
/* case 8:
printf("\n请输入元素\n");
scanf("%c",&e);
Te=LevelElem(T,e);
printf("\n%c的层数为%d\n",e,Te);
break;*/
case 0:exit(1);
}
}
return 0;
}
给分

回答3：

我有C++的不知道，能不能帮到你?

怎么开始跟女生聊天？家人介绍了个女生，还没见过面，加了微信，打算先作为朋友接触一下，可是该怎么开

从中国寄到加拿大的ems快递，派送的时候是直接送到家门口还是放到邮箱里自己去取啊？

女朋友的外婆病重,做为男朋友应该和她一起回去看望吗?前提她妈妈不同意我和女儿耍朋友，反对我们在一