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(pNULL) 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(pNULL) 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(pNULL) 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(BTNULL) return; s[rear] BT; while(frontrear){ 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(pNULL) 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(pNULL) 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(BTNULL) return; s[rear] BT; while(frontrear){ p s[front]; printf( %c,p-Data); if(p-Left) s[rear] p-Left; if(p-Right) s[rear] p-Right; } }