PTA 6-9 二叉树的遍历

本题要求给定二叉树的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 <stdio.h> #include <stdlib.h> 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

中序：

//中序 void InorderTraversal( BinTree BT ){ BinTree s[100]; int top = -1; BinTree p = BT; if(p==NULL) return; while(p!=NULL||top!=-1){ if(p!=NULL){ s[++top] = p; p = p->Left; }else{ p = s[top--]; printf(" %c",p->Data); p = p->Right; } } }

先序：

//先序 void PreorderTraversal( BinTree BT ){ BinTree s[100]; int top = -1; BinTree p = BT; if(p==NULL) return; s[++top] = p; while(top!=-1){ p = s[top--]; printf(" %c",p->Data); if(p->Right) s[++top] = p -> Right; if(p->Left) s[++top] = p-> Left; } }

先序输出叶结点：

void PreorderPrintLeaves( BinTree BT ){ BinTree s[100]; int top = -1; BinTree p = BT; if(p==NULL) return; s[++top] = p; while(top!=-1){ p = s[top--]; if(p->Left == NULL && p->Right == NULL){ printf(" %c",p->Data); } if(p->Right) s[++top] = p->Right; if(p->Left) s[++top] = p->Left; } }

后序：

//后序 void PostorderTraversal( BinTree BT ){ BinTree s[100]; int top = -1; BinTree p = BT; BinTree last = NULL; while(p!=NULL || top!=-1){ if(p!=NULL){ s[++top] = p; p = p->Left; }else{ p = s[top]; if(p->Right!=NULL &&p->Right!=last){ p = p->Right; }else{ p = s[top--]; printf(" %c",p->Data); last = p; p = NULL; } } } }

层次遍历：

//层次遍历 void LevelorderTraversal( BinTree BT ){ BinTree s[100]; int front = 0,rear = 0; BinTree p; if(BT==NULL) return; s[rear++] = BT; while(front<rear){ p = s[front++]; printf(" %c",p->Data); if(p->Left) s[rear++] = p->Left; if(p->Right) s[rear++] = p->Right; } }

综合代码：

//中序 void InorderTraversal( BinTree BT ){ BinTree s[100]; int top = -1; BinTree p = BT; if(p==NULL) return; while(p!=NULL||top!=-1){ if(p!=NULL){ s[++top] = p; p = p->Left; }else{ p = s[top--]; printf(" %c",p->Data); p = p->Right; } } } //先序 void PreorderTraversal( BinTree BT ){ BinTree s[100]; int top = -1; BinTree p = BT; if(p==NULL) return; s[++top] = p; while(top!=-1){ p = s[top--]; printf(" %c",p->Data); if(p->Right) s[++top] = p -> Right; if(p->Left) s[++top] = p-> Left; } } //后序 void PostorderTraversal( BinTree BT ){ BinTree s[100]; int top = -1; BinTree p = BT; BinTree last = NULL; while(p!=NULL || top!=-1){ if(p!=NULL){ s[++top] = p; p = p->Left; }else{ p = s[top]; if(p->Right!=NULL &&p->Right!=last){ p = p->Right; }else{ p = s[top--]; printf(" %c",p->Data); last = p; p = NULL; } } } } //层次遍历 void LevelorderTraversal( BinTree BT ){ BinTree s[100]; int front = 0,rear = 0; BinTree p; if(BT==NULL) return; s[rear++] = BT; while(front<rear){ p = s[front++]; printf(" %c",p->Data); if(p->Left) s[rear++] = p->Left; if(p->Right) s[rear++] = p->Right; } }