6 |
您所在的位置：网站首页 › 二叉树遍历的定义 › 6 |
6
|
6-2 二叉树的遍历 （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; } /* 你的代码将被嵌在这里 */ 输出样例（对于图中给出的树）：附25分代码（仅供参考学习） void InorderTraversal( BinTree BT ) //中序 { if(BT==NULL) return; InorderTraversal(BT->Left); printf(" %c",BT->Data); InorderTraversal(BT->Right); } void PreorderTraversal( BinTree BT ) //先序 { if(BT==NULL) return; printf(" %c",BT->Data); PreorderTraversal(BT->Left); PreorderTraversal(BT->Right); } void PostorderTraversal( BinTree BT ) //后序 { if(BT==NULL) return; PostorderTraversal(BT->Left); PostorderTraversal(BT->Right); printf(" %c",BT->Data); } void LevelorderTraversal( BinTree BT ) //层序 { /* 层序遍历就是一层一层地输出，定义两个BinTree数组，a和b a、b数组都是存的一层的所有节点，且a为输出的当前层，b为下一层 */ if(!BT) return; BinTree a[10000]; a[0]=BT; int len=1;//len记录当前层的节点数量 while(1) { if(len==0) return; int pos=0; BinTree b[10000]; for(int i=0;iData); if(a[i]->Left!=NULL)//如果它的左节点不为空，就存到b数组里 b[pos++]=a[i]->Left; if(a[i]->Right!=NULL)//如果它的右节点不为空，就存到b数组里 b[pos++]=a[i]->Right; } len=pos;//更新下一层宽度，为下一次循环做准备 for(int i=0;i |
【本文地址】
今日新闻 |
推荐新闻 |