数据结构(c语言版)

发布网友 发布时间：2022-04-23 01:09

我来回答

共1个回答

热心网友 时间：2023-10-09 19:39

测试数据1:
创建二叉树,输入先序扩展序列:ABD##E##C#F##
先序遍历输出节点:A B D E C F
中序遍历输出节点:D B E A C F
后序遍历输出节点:D E B F C A

二叉树示意图:
          A
       /      \
      B        C
    /    \    / \
   D      E  #   F
  / \    / \    / \
 #   #  #   #  #   #


测试数据2:
创建二叉树,输入先序扩展序列:ABC##DE#G##F###
先序遍历输出节点:A B C D E G F
中序遍历输出节点:C B E G D F A
后序遍历输出节点:C G E F D B A

二叉树示意图:
           A
         /   \
        B     #
    /      \
   C        D
  / \    /     \
 #  #   E       F
       / \     / \
      #   G   #   #
         / \
        #   #


#include<stdio.h>
#include<stdlib.h>

typedef struct Node   //二叉树的结构体
{
    char data;            //字符
    struct Node *lchild;  //左分支
    struct Node *rchild;  //右分支
}Bitree;

//创建二叉树: 用"先序遍历"(递归法)
void CreateBiTree(Bitree **bt)
{
    char ch;
    scanf("%c",&ch); //输入字符
    if(ch=='#')      //'#'是空节点NULL
        *bt=NULL;
    else
    {
        *bt=(Bitree *)malloc(sizeof(Bitree));
        (*bt)->data=ch;
        CreateBiTree(&((*bt)->lchild));
        CreateBiTree(&((*bt)->rchild));
    }
}

//用"先序遍历"输出节点(递归法)
void preOrder(Bitree *ptr)
{
    if(ptr!=NULL)
    {
        printf("%c ",ptr->data);
        preOrder(ptr->lchild);
        preOrder(ptr->rchild);
    }
}

//用"中序遍历"输出节点(递归法)
void inOrder(Bitree *ptr)
{
    if(ptr!=NULL)
    {
        inOrder(ptr->lchild);
        printf("%c ",ptr->data);
        inOrder(ptr->rchild);
    }
}

//用"后序遍历"输出节点(递归法)
void postOrder(Bitree *ptr)
{
    if(ptr!=NULL)
    {
        postOrder(ptr->lchild);
        postOrder(ptr->rchild);
        printf("%c ",ptr->data);
    }
}

int main()
{
    Bitree *root;
    printf("创建二叉树,输入先序扩展序列:");
    CreateBiTree(&root);

    printf("先序遍历输出节点: ");
    preOrder(root);
    printf("\n中序遍历输出节点: ");
    inOrder(root);
    printf("\n后序遍历输出节点: ");
    postOrder(root);

    printf("\n");
    return 0;
}