关于二叉树的三种遍历

论坛 期权论坛 期权     
以瞳_阅微   2018-4-26 13:44   5915   2
Of the traversal methods pre-order, in-order and post-order, briefly explain which one, and why, should be used to save the data in a BST back to a file, so that when the file is read, the BST will be re-created in the same order that is wa...Of the traversal methods pre-order, in-order and post-order, briefly explain which one, and why, should be used to save the data in a BST back to a file, so that when the file is read, the BST will be re-created in the same order that is was when it was saved to the file.

明天考试啦 -0- 有人帮我下咩.......展开
分享到 :
0 人收藏

2 个回复

倒序浏览
2#
司文郎  4级常客 | 2018-4-30 02:07:59 发帖IP地址来自
先序
preOrder(BiTree T)
{
  if(T)
  {
     visitor(T);
     preOrder(T->lchild);
     preOrder(T->rchild);
  }
}

中序

inOrder(BiTree T)
{
  if(T)
  {
     preOrder(T->lchild);
     visitor(T);
     preOrder(T->rchild);
  }
}

后序
preOrder(BiTree T)
{
  if(T)
  {

     preOrder(T->lchild);
     preOrder(T->rchild);
     visitor(T);
  }
}

   数据机构丢下太久了,基本不会了,只记得三种遍历了,估计也帮不了你咯... 还有,最好翻成中文发出来,因为有的人即便会,看到英文的怕麻烦也不会回答了....
3#
叶上雪1208  1级新秀 | 2018-4-30 02:08:00 发帖IP地址来自
1.采用二叉树链表作为存储结构,建立二叉树;

2.对二叉树分别按先、中、后序以及按层次遍历,输出相应的访问序列;

3.计算二叉树的深度,统计所有叶子结点总数及树中包含的结点总数。*/
#include"stdio.h"

#include"string.h"
#include"malloc.h"

#define Max 20         //结点的最大个数

typedef struct node{

    char data;

    struct node *lchild,*rchild;

}BinTNode;            //自定义二叉树的结点类型

typedef BinTNode *BinTree;    //定义二叉树的指针

int NodeNum,leaf;           //NodeNum为结点数,leaf为叶子数

//基于先序遍历算法创建二叉树

//要求输入先序序列,其中加入虚结点“#”以示空指针的位置

BinTree CreatBinTree(void)

{

    BinTree T;

    char ch;

    if((ch=getchar())=='#')

       return(NULL);     //读入#,返回空指针

    else{
        T=(BinTNode *)malloc(sizeof(BinTNode));//生成结点

T->data=ch;

       T->lchild=CreatBinTree();        //构造左子树

              T->rchild=CreatBinTree(); //构造右子树

       return(T);

    }

}

//DLR 先序遍历

void Preorder(BinTree T)

{

    if(T) {

              printf("%c",T->data);   //访问结点

              Preorder(T->lchild);    //先序遍历左子树

              Preorder(T->rchild);    //先序遍历右子树

    }

}

//LDR 中序遍历

void Inorder(BinTree T)

{

    if(T) {

       Inorder(T->lchild);      //中序遍历左子树

              printf("%c",T->data);    //访问结点

       Inorder(T->rchild);      //中序遍历右子树

    }

}

//LRD 后序遍历

void Postorder(BinTree T)

{

    if(T) {

       Postorder(T->lchild);    //后序遍历左子树

              Postorder(T->rchild);    //后序遍历右子树

       printf("%c",T->data);    //访问结点

    }

}

//采用后序遍历求二叉树的深度、结点数及叶子数的递归算法

int TreeDepth(BinTree T)

{

    int hl,hr,max;

    if(T){

       hl=TreeDepth(T->lchild);         //求左深度

              hr=TreeDepth(T->rchild);    //求右深度

       max=hl>hr? hl:hr;           //取左右深度的最大值

              NodeNum=NodeNum+1;         //求结点数

       if(hl==0&&hr==0) leaf=leaf+1; //若左右深度为0,即为叶子。

              return(max+1);

    }

    else return(0);

}

//利用“先进先出”(FIFO)队列,按层次遍历二叉树

void Levelorder(BinTree T)

{

    int front=0,rear=1;

    BinTNode *cq[Max],*p;   //定义结点的指针数组cq

    cq[1]=T;                //根入队

    while(front!=rear)

    {

              front=(front+1)%NodeNum;

              p=cq[front];            //出队

              printf("%c",p->data);     //出队,输出结点的值

              if(p->lchild!=NULL){

           rear=(rear+1)%NodeNum;

                  cq[rear]=p->lchild;     //左子树入队

              }

              if(p->rchild!=NULL){

           rear=(rear+1)%NodeNum;

                  cq[rear]=p->rchild;     //右子树入队

       }

    }

}

//主函数

main()

{

    BinTree root;

    int i,depth;

    printf("\n");

printf("Creat Bin_Tree; Input preorder:"); //输入完全二叉树的先序序列,

                         // 用#代表虚结点,如ABD###CE##F##

    root=CreatBinTree();       //创建二叉树,返回根结点

    do {                    //从菜单中选择遍历方式,输入序号。

              printf("\t********** select ************\n");

printf("\t1: Preorder Traversal\n");

       printf("\t2: Iorder Traversal\n");

printf("\t3: Postorder traversal\n");

       printf("\t4: PostTreeDepth,Node number,Leaf number\n");

printf("\t5: Level Depth\n"); //按层次遍历之前,先选择4,求出该树的结点数。

printf("\t0: Exit\n");

       printf("\t*******************************\n");

scanf("%d",&i);    //输入菜单序号(0-5)

switch (i){

              case 1: printf("Print Bin_tree Preorder: ");

       Preorder(root);      //先序遍历

                     break;

case 2: printf("Print Bin_Tree Inorder: ");

                     Inorder(root);      //中序遍历

       break;

       case 3: printf("Print Bin_Tree Postorder: ");

                     Postorder(root);    //后序遍历

       break;

case 4: depth=TreeDepth(root);     //求树的深度及叶子数

              printf("BinTree Depth=%d BinTree Node number=%d",depth,NodeNum);

                     printf(" BinTree Leaf number=%d",leaf);

              break;

              case 5: printf("LevePrint Bin_Tree: ");

       Levelorder(root);     //按层次遍历

                     break;

       default: exit (1);

       }

              printf("\n");

    } while(i!=0);

}
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

积分:
帖子:
精华:
期权论坛 期权论坛
发布
内容

下载期权论坛手机APP