二叉树的遍历方式（6-9 二叉树的遍历 (25分)为例）

本题要求给定二叉树的4种遍历。

函数接口定义：
void InorderTraversal( BinTree BT );
void PreorderTraversal( BinTree BT );
void PostorderTraversal( BinTree BT );
void LevelorderTraversal( BinTree BT );
其中BinTree结构定义如下：

typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
ElementType Data;
BinTree Left;
BinTree Right;
};
要求4个函数分别按照访问顺序打印出结点的内容，格式为一个空格跟着一个字符。

裁判测试程序样例：
#include
#include

typedef char ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
ElementType Data;
BinTree Left;
BinTree Right;
};

BinTree CreatBinTree(); /* 实现细节忽略 */
void InorderTraversal( BinTree BT );
void PreorderTraversal( BinTree BT );
void PostorderTraversal( BinTree BT );
void LevelorderTraversal( BinTree BT );

int main()
{
BinTree BT = CreatBinTree();
printf(“Inorder:”); InorderTraversal(BT); printf("\n");
printf(“Preorder:”); PreorderTraversal(BT); printf("\n");
printf(“Postorder:”); PostorderTraversal(BT); printf("\n");
printf(“Levelorder:”); LevelorderTraversal(BT); printf("\n");
return 0;
}
/* 你的代码将被嵌在这里 */
输出样例（对于图中给出的树）：

Inorder: D B E F A G H C I
Preorder: A B D F E C G H I
Postorder: D E F B H G I C A
Levelorder: A B C D F G I E H

先序、中序、后序遍历的实现只是输出的函数在代码中的位置不同，层序遍历是用模拟队列的方式实现的，如果想要以递归的方法实现可以参考这篇博客---->传送门

#include 
#include typedef char ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{ElementType Data;BinTree Left;BinTree Right;
};BinTree CreatBinTree(); /* 实现细节忽略 */
void InorderTraversal( BinTree BT );
void PreorderTraversal( BinTree BT );
void PostorderTraversal( BinTree BT );
void LevelorderTraversal( BinTree BT );int main()
{BinTree BT = CreatBinTree();printf("Inorder:");    InorderTraversal(BT);    printf("\n");printf("Preorder:");   PreorderTraversal(BT);   printf("\n");printf("Postorder:");  PostorderTraversal(BT);  printf("\n");printf("Levelorder:"); LevelorderTraversal(BT); printf("\n");return 0;
}
/* 你的代码将被嵌在这里 */void InorderTraversal( BinTree BT ){//中序if(BT!=NULL){InorderTraversal(BT->Left);printf(" %c",BT->Data);InorderTraversal(BT->Right);}
}
void PreorderTraversal( BinTree BT ){//先序if(BT!=NULL){printf(" %c",BT->Data);PreorderTraversal(BT->Left);PreorderTraversal(BT->Right);}
}
void PostorderTraversal( BinTree BT ){//后续if(BT!=NULL){PostorderTraversal(BT->Left);PostorderTraversal(BT->Right);printf(" %c",BT->Data);}
}
void LevelorderTraversal( BinTree BT ){//层序BinTree a[100];int cnt=0;int p=0;if(BT!=NULL){a[cnt++]=BT;while(cnt>p){printf(" %c",a[p]->Data);if(a[p]->Left!=NULL){a[cnt++]=a[p]->Left;}if(a[p]->Right!=NULL){a[cnt++]=a[p]->Right;}p++;}}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！