实验目的

1. 通过实验掌握二叉树的基本存储结构；
2. 掌握二叉树的建立与遍历的基本算法，并加以应用；

实验环境

CodeBlocks

实验要求

1. 熟悉c语言的语法知识；
2. 掌握二叉树的链式存储结构—二叉链表的定义、构造、遍历等基本操作；

实验内容

完成二叉树的二叉链表的存储结构的定义、创建、前序遍历、中序遍历、后序遍历、求叶子数和求深度等函数的编写。完成以下函数的编写： (1) 编写一个函数输出结点的值。visit( BiTree T) (2)编写一个函数，用递归算法求二叉树的结点总数，函数原型为：int node(BiTree T)。 (3)要求在主函数中实现对以上操作的调用，实现以下功能： ①定义一棵二叉树T，并调用创建函数创建一棵如下图所示的二叉树： ②分别输出二叉树的前序序列、中序序列和后序序列。 ③分别输出二叉树的叶子结点数、深度和结点总数。

源代码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXSIZE 1024

typedef char ElemType; /*二叉链表的定义*/
typedef struct BiTreeNode
{
          
   
    ElemType data;
    struct BiTreeNode *lchild,*rchild;
}BiTreeNode, *BiTree;

BiTree CreateBiTree(char str[]) /*创建二叉树*/
{
          
   
    BiTree bt;
    char ch;
    static int i=0;
    ch=str[i++];
    if(ch==.)bt=NULL;
    else
    {
          
   
        bt=(BiTree)malloc(sizeof(BiTreeNode));
        bt->data=ch;
        bt->lchild=CreateBiTree(str);
        bt->rchild=CreateBiTree(str);
    }
    return bt;
}

void PreOrder(BiTree bt) /*先序遍历*/
{
          
   
    if(bt!=NULL)
    {
          
   
        visit (bt);
        PreOrder (bt->lchild);
        PreOrder (bt->rchild);
    }
}

void InOrder(BiTree bt) /*中序遍历*/
{
          
   
    if(bt!=NULL)
    {
          
   
        InOrder (bt->lchild);
        visit (bt);
        InOrder (bt->rchild);
    }
}

void PostOrder(BiTree bt) /*后序遍历*/
{
          
   

    if(bt!=NULL)
        {
          
   PostOrder (bt->lchild);
        PostOrder (bt->rchild);
        visit (bt);}
}

void visit(BiTree bt) /*输出结点的值*/
{
          
   
    if(bt)
        printf("%c",bt->data);
}

int BitreeLeaf (BiTree bt) /*统计二叉树的叶子节点数*/
{
          
   
    if (bt==NULL) return 0;
    if (bt->lchild==NULL&&bt->rchild==NULL)
        return 1;
    return (BitreeLeaf (bt->lchild)+BitreeLeaf (bt->rchild));
}

int BitreeDepth (BiTree bt) /*求二叉树的深度*/
{
          
   
    int d=0,depthL,depthR;
    if (bt==NULL) return 0;
    depthL=BitreeDepth (bt->lchild);
    depthR=BitreeDepth (bt->rchild);
    d=max (depthL , depthR);
    return d+1;
}

int max(int a,int b) /*判断大小*/
{
          
   
  if(a>=b)

        return a;
  else
    return b;
}

int SumNode(BiTree T) /*递归算法求二叉树的结点总数*/
{
          
   

    int n;
    if(T==NULL)
        return 0;
    else
    {
          
   
        n=SumNode (T->lchild)+SumNode (T->rchild);
        return n+1;
    }
}

void main() /*主函数*/
{
          
   
    BiTree T;
    int n;
    char str[MAXSIZE];
    printf("创建一棵二叉树，以.代表空子树：
");
    gets(str);
    T=CreateBiTree(str);
    printf("
二叉树的先序遍历得到的序列是：
");
    PreOrder(T);
    printf("
二叉树的中序遍历得到的序列是：
");
    InOrder(T);
    printf("
二叉树的后序遍历得到的序列是：
");
    PostOrder(T);
    n=BitreeLeaf(T);
    printf("
二叉树的叶子节点数为：%d
",n);
    n=BitreeDepth(T);
    printf("
二叉树的深度为：%d
",n);
    n=SumNode(T);
    printf("
而产生的节点数为：%d
",n);
}

运行结果