二叉树实验报告

题目：以三元组形式输入任意二叉树（以大写字母表示结点） ，求以任意一选定结点为子树的深度。

1.       编程思路概述：实验采用二叉树的数据结构，以二叉链表存储，三元组形式输入建立二叉树。本实验中，用户输入选择结点后，程序调用BiTNode* Find Node(char tag, BiTNode* node)函数，递归搜索该结点的位置，并返回子树的根结点，然后程序调用int BiTreeDepth(BiTree T)函数，求出子树的深度。

              另外，为了实现多次选择输入，程序用了while语句，以choose为标志，当choose为1时执行程序，为0时结束程序。

2.       算法步骤：1.用户以三元组形式输入二叉树的结点元素及其位置关系，建立二叉树，并打印输出该二叉树。

           2.用户输入选择结点，程序调用BiTNode* Find Node(char tag, BiTNode* node)函数，返回子树的根结点，然后调用BiTreeDepth(BiTree T)函数，求出子树的深度，并输出该值。

           3.用户可以选择是否继续执行程序，若继续，则输入1，否则输入0，结束程序。

3.       主程序代码：

 int main(void)

{

BiTree T;

TElemType e1;

char node;   // node为用户选择输入的结点 //

int b,choose;  // b为以选定结点为子树的深度，choose为实现多次选择输入的标志 //

 BiTNode* a;   // a为选定结点为子树的根结点 //

choose=1;    // 多次选择的标志，当choose为1时运行程序，为0时结束程序 //

InitBiTree(T);

printf("构造空二叉树后,树空否？%d(1:是0:否), 树的深度=%d\n",BiTreeEmpty(T),BiTreeDepth(T));

e1 = Root(T);

if(e1 != Nil)

#ifdef CHAR

           printf("二叉树的根为: %c\n",e1);

#endif

#ifdef INT

           printf("二叉树的根为: %d\n",e1);

#endif

else

           printf("树空，无根\n");

//三元组构建二叉树

string x;

printf("输入格式说明：三元组（P,C,L/R）方式输入,P:parent, C: child, L/R: C is P's left child / right child, 输入 end 结束输入\n");

printf("eg. the root: input ^AL, its left child is B: input ABL, its right child is C: input ACR!\n");

GetUserWord(x);

while(x!="end")

{

           AddNode(T, x[0], x[1], x[2]);

           GetUserWord(x);

}

//输出树

PrintTreeLevel( T );

//以三元组形式输入任意二叉树（以大写字母表示结点） ，求以任意一选定结点为子树的深度。

while(choose)     //  实现多次选择输入 //

{

           printf("Please select a node:  ");

             fflush(stdin);

    scanf("%c",&node);

     a= FindNode(node,T);   // a为生成子树的根 //

     b=BiTreeDepth(a);

     printf("the Depth of BiTree is :  %d\n",b);

    printf("\nif you want to cointue choose 1,else choose 0: ");

           fflush(stdin);

           scanf("%d",&choose);

}

     DestroyBiTree( T );

    return EXIT_SUCCESS;

}

4. 程序计算机运行结果图：

 

第二篇：二叉树的各种基本运算的实现实验报告

软件技术基础实验四

--二叉树的各种基本运算的实现

班级：电信0901

学号：0703090106

姓名：蒋玮珂

实验四 二叉树的各种基本运算的实现

（1）实验题目:

编写一个程序，实现二叉树的各种基本运算，并在此基础上设计一个主程序完成如下功能：

（1）创建二叉树btree

（2）求出二叉树btree的树高

（3）中序遍历二叉树btree

（4）统计二叉树btree的叶结点数

（5）输出二叉树btree的所有叶结点

（2）实验目的：

（1）掌握二叉树的递归操作与运算；

（2）加深对二叉树的建立，先序 中序遍历方法以及树高的理解与应用

（3）调试通过并正确执行给定功能要求的实验代码

#include "stdafx.h"

#include <fstream.h>

struct bitree

{

    char data;

    bitree *lchild;

    bitree *rchild;

};

bitree *createtree(char a[],char b[],int l1,int h1,int l2,int h2)

{

    btree *root;int i,lhigh,rhigh;

    root=(btree*)malloc(sizeof(btree));

    root->data=a[l1];

    if(i=h1,(b[i]!=(root->data)),i++)

    {lhigh=i-h1;

    rhigh=h2-i;

    if(lhigh)

       root->lchild=createtree(a,b,l1+1,l1+lhigh,h1,h1+lhigh-1);

    else

       root->lchild=NULL;

    if(rhigh)

       root->rchild=createtree(a,b,l2-rhigh+1,l2,h2-rhigh+1,h2);

    else

       root->rchild=NULL;}

    return root;

}

int treehigh(bitree *q)

{

     if(q==NULL)

     return 0;

     else

    {int lhigh,rhigh;

     lhigh=treehigh(q->lchild);

    rhigh=treehigh(q->rchild);

    if(lhigh>=rhigh)

       return lhigh+1;

    else

       return rhigh+1;

     }

}

void inorder(bitree *q)

{

    j=0;

     if(q!=NULL)

    {

        inorder(q->lchild,str1+(++j));

        *(str1+j)=q->data;

        inorder(q->rchild,str1+(++j));

    }

}

int countleaf(bitree *q, int count,int flag,char *str2)

{

k=0;

if(q==0)

      return NULL;

  else if (q->lchild==NULL &&q->rchild==NULL)

      {count ++;

       while (flag)

       *(str2+(k++))=q->data;

       return count;}

  else

  {

countleaf(q->lchild ,count,flag,str2+(++k));

      countleaf(q->rchild ,count,flag,str2+(++k));

   if(!flag)

      return count;

   else

      return NULL;

}

}

void main()

{

bitree *q;int high,flag,n=0,i=0;char x,y;

ifstream infile("e:\\Program Files\\MSDev98\\MyProjects\\jwk\\infile.txt");

ofstream outfile("e:\\Program Files\\MSDev98\\MyProjects\\jwk\\outfile.txt");

 char a[20],b[20],str2[20],str1[20];

 while(infile.get(x))

   {      

       infile>>x;

       a[i++]=x;

       n++;

   }

   i=0;

   while(infile.get(y))

  {   

     infile>>y;

     b[i++]=y;

   }

  q=createtree(a,b,1,n,1,n);

  high=treehigh(q);

  outfile<<"The height of the bitree is："<<high<<endl;

  outfile<<"The sequence of the bitree by the way of inorder："<<endl;

  inorder(q,str1);

  i=0;

  while(str1[i])

     outfile<<str1[i++];

 count=0;

 flag=0;count=countleaf(q,count,flag,str2);

 cout<<"The number of the leaves is："<<endl<<count<<endl;

 flag=1;

 cout<<"The leaves of the bitree is："<<endl;

 i=0;

 while(str2[i])

     outfile<<str2[i++];   

 infile.close();

 outfile.close();

}

（4）实验结果截图