一  实验题目

实现二叉树的基本操作的代码实现

二  实验目的

1、掌握二叉树的基本特性

2、掌握二叉树的先序、中序、后序的递归遍历算法

3、通过求二叉树的深度、度为2的结点数和叶子结点数等算法

三  实习要求

（1）认真阅读书上给出的算法

（2）编写程序并独立调试

四、给出二叉树的抽象数据类型

ADT BinaryTree{

//数据对象D：D是具有相同特性的数据元素的集合。
//数据关系R：
// 若D=Φ，则R=Φ，称BinaryTree为空二叉树；
// 若D≠Φ，则R={H}，H是如下二元关系；
// （1）在D中存在惟一的称为根的数据元素root，它在关系H下无前驱；
// （2）若D-{root}≠Φ，则存在D-{root}={D1,Dr}，且D1∩Dr =Φ；
// （3）若D1≠Φ，则D1中存在惟一的元素x1，<root,x1>∈H，且存在D1上的关系H1 ?H；若Dr≠Φ，则Dr中存在惟一的元素xr，<root,xr>∈H，且存在上的关系Hr ?H；H={<root,x1>,<root,xr>,H1,Hr}；
// （4）(D1,{H1})是一棵符合本定义的二叉树，称为根的左子树；(Dr,{Hr})是一棵符合本定义的二叉树，称为根的右子树。

//基本操作：
CreateBiTree( &T, definition )
// 初始条件：definition给出二叉树T的定义。
// 操作结果：按definiton构造二叉树T。

BiTreeDepth( T )
// 初始条件：二叉树T存在。
// 操作结果：返回T的深度。

PreOrderTraverse( T, visit() )
// 初始条件：二叉树T存在，Visit是对结点操作的应用函数。
// 操作结果：先序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败。

InOrderTraverse( T, visit() )
// 初始条件：二叉树T存在，Visit是对结点操作的应用函数。
// 操作结果：中序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败。

PostOrderTraverse( T, visit() )
// 初始条件：二叉树T存在，Visit是对结点操作的应用函数。
// 操作结果：后序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败。

LeafNodes(p)
// 初始条件：二叉树T存在。
// 操作结果：返回T的叶子结点数。

BothNodes(p)
//初始条件：二叉树T存在。

// 操作结果：返回T的度为2的结点数。

五、详细设计

1、给出本数据的存储结构定义

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define NULL 0

#define OVERFLOW -2

2、实现二叉树的抽象数据类型如下:

typedef         int                 Status;

typedef         char        TElemType; 定义二叉树的数据元素类型为chr

3、存储实现的抽象数据类型如下：

typedef  struct     BiTNode0120

{

       TElemType   data;

       struct            BiTNode0120      *lchild; // 左孩子指针

       struct            BiTNode0120      *rchild;// 右孩子指针

}BiTNode0120, *BiTree;

4、运算的函数声明：

Status CreateBiTree0120 (BiTree T, definition )//构建二叉树

Status PreOrder0120 (BiTree p)//先序遍历

Status InOrder0120 (BiTree p)//中序遍历

Status PostOrder0120 (BiTree p)//后序遍历

Status BTNodeDepth0120 (BiTree p)//求二叉树的深度

Status LeafNodes0120 (BiTree p,int *i)//求二叉树叶子结点的个数

void getDataFromFile0120(char fileName[],BiTree &root);

Status BothNodes0120 (BiTree p,int *i)//求度为2的结点数

5、给出操作实现的伪码

Status createBiTree0120 (BiTree &root,char in[],int begin1,int end1,char post[],int begin2,int end2)

{   //根据给定的中序序列in,后序序列post,构造二叉树root

       //其中： begin1，end1分别为叉树的中序序列在in[]中的开始位置（序号，数组下标+1）、结束位置；

    //其中： begin2，end2分别为叉树的后序序列在post[]中的开始位置（序号，数组下标+1）、结束位置；

      

       char r;

       int i;

    int  m1;   //中序序列中，左子树根位置

       int  m2;   //后序序列中，左子树最后一个结点位置

    if(begin1-end1!=begin2-end2) return ERROR;

      

    if(end1-begin1>=0)

    {

              root=(BiTree)malloc(sizeof(BiTNode));

              r=post[end2];

              root->data=r;  //根

              for(i=begin1;i<=end1;i++)

                     if(in[i]==r) break;

                     m1=i-1;

                     m2=begin2+i-begin1-1;

                     root->lchild=NULL;

                     root->rchild=NULL;

                     if(createBiTree0120 (root->lchild  ,in,begin1,m1    ,post,begin2,m2)==ERROR)  //构造左子树

                            printf("初始化二叉树出错！\n\n请检查初始数据！\n\n");

                     if(createBiTree0120 (root->rchild  ,in,m1+2,end1    ,post,m2+1,end2-1)==ERROR)  //构造右子树

                            printf("初始化二叉树出错！\n\n请检查初始数据！\n\n");

    }

    else

    {

              root=NULL;

    }

       return OK;

}

void getDataFromFile0120 (char fileName[],BiTree &root)

{  //从文件fileName中读取数据构造二叉树root

       FILE *fp;

      

       char inOrder0120 [100];

       char postOrder0120 [100];

       int a1,a2,b1,b2;

       fp=fopen(fileName,"r");

       fscanf(fp,"%s\n",inOrder0120);

    fscanf(fp,"%s\n",postOrder0120);

       fclose(fp);

    a1=strlen("inOrder0120:");   //中序序列第一个字符位置

       a2=strlen(inOrder0120)-1;;    //中序序列最后一个字符位置

    b1=strlen("postOrder0120:"); //后序序列第一个字符位置

       b2=strlen(postOrder0120)-1;     //后序序列最后一个字符位置

      

       if(createBiTree0120 (root,inOrder0120,a1,a2,postOrder0120,b1,b2)==ERROR)

              printf("初始化二叉树出错！\n\n请检查初始数据！\n\n");

       else

              printf("初始化二叉树成功！");

}

Status PreOrder0120 (BiTree p){  // 先序遍历二叉树

    if ( p!= NULL ) {

         printf("%c", p->data);

         PreOrder0120 ( p->lchild ) ;

         PreOrder0120 ( p->rchild) ;

    }

       return OK;

}

Status InOrder0120 (BiTree p){  // 中序遍历二叉树

    if( p!= NULL ) {

       InOrder0120 ( p->lchild ) ;

      printf("%c", p->data);

      InOrder0120 ( p->rchild) ;

    }

       return OK;

}

Status PostOrder0120 (BiTree p){  // 后序遍历二叉树

   if ( p!= NULL ) {

           PostOrder0120 ( p->lchild ) ;

         PostOrder0120 ( p->rchild) ;

         printf("%c", p->data);

    }

   return OK;

}

Status BTNodeDepth0120 (BiTree p){//求二叉树的深度

       int lchilddep,rchilddep;

       if(p==NULL)

              return 0;

       else{

        lchilddep=BTNodeDepth0120 (p->lchild);

        rchilddep=BTNodeDepth0120 (p->rchild);

              return(lchilddep>rchilddep)?(lchilddep+1):(rchilddep+1);

       }

       return OK;

}

Status LeafNodes0120 (BiTree p,int *i){//求二叉树的叶子结点

       int j;

       if(p!=NULL)

       {

              if(p->lchild!=NULL||p->rchild!=NULL)

              {

                     j = *i;

                     j++;

                     *i = j;

              }

              LeafNodes0120 (p->lchild,i);

              LeafNodes0120(p->rchild,i);

              return OK;

             

       }

}

Status BothNodes0120 (BiTree p,int *i){//求度为2的结点数

              int j;

       if(p!=NULL)

       {

           if(p->lchild!=NULL&&p->rchild!=NULL)

              {

                  j=*i;

                  j++;

                  *i = j;

              }

           BothNodes0120 (p->lchild,i);

          BothNodes0120(p->rchild,i);

           return OK;

       }

}

六、实验环境

1.环境：宿舍。

2.硬件：2048M内存，500G硬盘。

    3.系统：Windows 7  64位操作系统

4.软件平台：Microsoft Visual C++ 6.0简体中文版

七、相关文件列表如下

demo.cpp: 主程序文件

bitree.cpp: 操作实现的算法

bitree.h：函数声明

Mydef.h：存储结构的定义

八、程序的运行测试及结果

测试用例 1：构造二叉树

测试用例 2：先序遍历

测试用例 3：中序遍历

测试用例 4：后序遍历

测试用例 5：叶子结点个数

测试用例 6：深度

测试用例 7：度为2的结点的数

九、本次实习总结

1．总结本次实习的收获

通过本次实习，加强了对二叉树的认识与相关操作的算法、编程实现；

2．本系统的不足之处

（1）系统的健壮行不够强；

（2）代码不够优化。

3.遇到的困难

      对于一些不会编译的程序，通过百度会了求叶子结点数，然后仿照求叶子结点数的方法，自己编出了求度为2的结点数的算法，学会了很多东西，对编程更加有兴趣了。

十、参考材料

严蔚敏等．数据结构(C语言版)．北京：清华大学出版社，2006

老师给的“抽象数据类型定义”的资料

 

第二篇：二叉树基本操作的程序实现

二叉树基本操作的程序实现

作者：nuciewth 阅读人次：43966 文章来源：本站原创 发布时间：2007-6-13 网友评论(32)

条 原帖及讨论：/thread-137061-1-1.html

//Bintree.h

#include<stdio.h>

#include<malloc.h>

typedef struct Binnode{//二叉树结点结构体

char data;

struct Binnode *lchild;

struct Binnode *rchild;

};

typedef Binnode *Bintree ;

typedef struct stack{ //二叉树结点栈

Bintree data[100];

int flag[100];

int top;

};

typedef struct queue{ //二叉树结点队列

Bintree data[30];

int front;

int rear;

};

/*******************************************/

/* 按照前序遍历建立二叉树 */

/*******************************************/

void Creat_Bintree(Bintree *root)

{

char ch;

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

{

*root=NULL;

}

else

{

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

(*root)->data=ch;

Creat_Bintree(&(*root)->lchild);

Creat_Bintree(&(*root)->rchild);

}

}

/*******************************************/ /* 按照前序递归遍历二叉树 */ /*******************************************/ void Preorder1(Bintree t)

{

if(t!=NULL)

{

printf("%c",t->data);

Preorder1(t->lchild);

Preorder1(t->rchild);

}

}

/*******************************************/ /* 按照中序递归遍历二叉树 */ /*******************************************/ void Inorder1(Bintree t)

{

if(t!=NULL)

{

Inorder1(t->lchild);

printf("%c",t->data);

Inorder1(t->rchild);

}

}

/*******************************************/ /* 按照后序递归遍历二叉树 */ /*******************************************/ void Posorder1(Bintree t)

{

if(t!=NULL)

{

Posorder1(t->lchild);

Posorder1(t->rchild);

printf("%c",t->data);

}

}

/*******************************************/ /* 按照前序非递归遍历二叉树 */ /*******************************************/ void Preorder2(Bintree t)

{

Bintree pre=t;

stack s;

s.top=0;

printf("输出前序遍历序列:");

while(pre||s.top>0)

{

if(pre)

{

printf("%c",pre->data);

s.data[s.top++]=pre;

pre=pre->lchild;

}

else

{

pre=s.data[--s.top]->rchild;

}

}

printf("\n\n");

}

/*******************************************/ /* 按照中序非递归遍历二叉树 */ /*******************************************/ void Inorder2(Bintree t)

{

Bintree pre=t;

stack s;

s.top=0;

printf("输出中序遍历序列:");

while(pre||s.top>0)

{

if(pre)

{

s.data[s.top++]=pre;

pre=pre->lchild;

}

else

{

pre=s.data[--s.top];

printf("%c",pre->data);

pre=pre->rchild;

}

}

printf("\n\n");

}

/*******************************************/ /* 按照后序非递归遍历二叉树 */ /*******************************************/ void Posorder2(Bintree t)

{

stack s;

s.top=-1;

printf("输出后序遍历序列:");

while(t!=NULL||s.top!=-1)

{

while(t)

{

s.top++;

s.flag[s.top]=0;

s.data[s.top]=t;

t=t->lchild;

}

while(s.top>=0&&s.flag[s.top]==1) {

t=s.data[s.top];

printf("%c",t->data);

s.top--;

}

if(s.top>=0)

{

t=s.data[s.top];

s.flag[s.top]=1;

t=t->rchild;

}

else

{

t=NULL;

}

}

printf("\n\n");

}

/*******************************************/ /* 按照层次遍历二叉树 */ /*******************************************/

void Levelorder(Bintree t)

{

queue q;

q.data[0]=t;

q.front=0;q.rear=1;

printf("层次遍历二叉树结果:");

while(q.front<q.rear)

{

if(q.data[q.front])

{

printf("%c",q.data[q.front]->data);

q.data[q.rear++]=q.data[q.front]->lchild; q.data[q.rear++]=q.data[q.front]->rchild; q.front++;

}

else

{

q.front++;

}

}

printf("\n\n");

}

#include"Bintree.h"

/*******************************************/ /* 递归法将二叉树的左右子树互换 */ /*******************************************/ void Exchange1(Bintree t)

{

Bintree temp;

if(t)

{

Exchange1(t->lchild);

Exchange1(t->rchild);

temp=t->lchild;

t->lchild=t->rchild;

t->rchild=temp;

}

}

/*******************************************/ /* 非递归法将二叉树的左右子树互换 */ /*******************************************/ void Exchange2(Bintree t)

{

Bintree temp;

stack s;

s.top=0;

while(t||s.top)

{

if(t)

{

s.data[s.top++]=t;

temp=t->lchild;

t->lchild=t->rchild;

t->rchild=temp;

t=t->lchild;

}

else

{

t=s.data[--s.top]->rchild;

}

}

}

int main()

{

Bintree t;

Creat_Bintree(&t);

Exchange2(t);

Inorder2(t);

return 0;

}

#include"Bintree.h"

/*******************************************/

/* 递归法求叶子结点个数 */

/*******************************************/

int Leaves_Num1(Bintree t)

{

if(t)

{

if(t->lchild==NULL&&t->rchild==NULL)

{

return 1;

}

return Leaves_Num1(t->lchild)+Leaves_Num1(t->rchild); }

return 0;

}

/*******************************************/ /* 非递归法求叶子结点个数 */ /*******************************************/ int Leaves_Num2(Bintree t)

{

int count=0;

stack s;

s.top=0;

while(t||s.top>0)

{

if(t)

{

s.data[s.top++]=t;

if(t->lchild==NULL&&t->rchild==NULL) {

count++;

}

t=t->lchild;

}

else

{

t=s.data[--s.top]->rchild;

}

}

return count;

}

int main()

{

int count=0;

Bintree t;

Creat_Bintree(&t);

count=Leaves_Num2(t);

printf("该二叉树的叶子结点数为:%d\n",count); return 0;

}

#include"Bintree.h"

/**********************************************/ /* 求一棵树的高度 */ /**********************************************/ int Depth(Bintree t)

{

int lh , rh ;

if( NULL == t )

{

return 0 ;

}

else

{

lh = Depth( t->lchild ) ;

rh = Depth( t->rchild ) ;

return ( lh > rh ? lh : rh ) + 1 ;

}

}

int main()

{

Bintree t ;

Creat_Bintree( &t ) ;

printf( "树的高度是%d\n" , Depth( t ) ) ;

return 0 ;

}

#include"Bintree.h"

/*******************************************************/ /* 已知一课棵二叉树的中序和后序，建立这棵树 */ /*******************************************************/ void In_Pos_order(Bintree *t,char *s,char *r)

{

char La[30],Lb[30],Ra[30],Rb[30];

int i,len,length=strlen(r);

if(length>0&&r[length-1]!='\0')

{

*t=(Binnode *)malloc(sizeof(Binnode));

(*t)->data=r[length-1];

for(i=0;s[i]!=r[length-1];i++)

{

Ra[i]=s[i];

La[i]=r[i];

}

len=i;

Ra[len]='\0'; //左中

La[len]='\0'; //左后

for(i=len+1;i<strlen(s);i++)

{

Rb[i-len-1]=s[i];

}

Rb[i-len-1]='\0';

for(i=len;i<strlen(r)-1;i++)

{

Lb[i-len]=r[i];

}

Lb[i-len]='\0';

In_Pos_order(&(*t)->lchild,Ra,La);

In_Pos_order(&(*t)->rchild,Rb,Lb);

}

else

{

*t=NULL;

}

}

int main()

{

Bintree t;

char in[30]="ABCEFGHD",pos[30]="ABFHGEDC";//测试数据 printf("输入中序遍历序列:");

scanf("%s",in);

printf("输入后序遍历序列:");

scanf("%s",in);

In_Pos_order(&t,in,pos);

Preorder2(t);

}

#include"Bintree.h"

/*******************************************************/ /* 判断两棵是否等价 */ /*******************************************************/ int Is_equal( Bintree t1 , Bintree t2 )

{

int t=0;

if(NULL == t1 && NULL == t2)

{

t=1;

}

else

{

if(NULL !=t1 &&NULL != t2 )

{

if(t1->data == t2->data)

{

if(Is_equal(t1->lchild,t2->lchild))

{

t=Is_equal(t1->rchild,t2->rchild); }

}

}

}

return t;

}

int main()

{

Bintree t1,t2;

Creat_Bintree(&t1);

getchar();

Creat_Bintree(&t2);

if(Is_equal(t1,t2))

{

printf( "Yes!\n") ;

}

else

{

printf( "No!\n" ) ;

}

return 0 ;

}

#include"Bintree.h"

/****************************************************/ /* 查找某个信息是否在这棵树中 */ /****************************************************/ Bintree locale_x(Bintree t,char x)

{

Bintree p;

if(t==NULL) return NULL;

else

{

if( t -> data == x ) return t;

else

{

p = locale_x(t->lchild,x);

if(p)return p;

else

return locale_x(t->rchild,x);

}

}

}

int main()

{

Bintree root,p;

char ch;

Creat_Bintree(&root);

getchar();

printf("输入要查找的值:");

scanf("%c",&ch);

p=locale_x(root,ch);

if(p)printf( "YES!\n" ) ;

else printf( "NO!\n" ) ;

return 0;

}

#include"Bintree.h"

/****************************************************/ /* 树的结点个数 */ /****************************************************/ int num_of_node(Bintree t)

{

if(t==NULL)return 0 ;

else return num_of_node(t->lchild)+num_of_node(t->rchild)+1; }

int main()

{

Bintree root,p;

Creat_Bintree(&root);

printf("%d\n",num_of_node(root));

return 0;

}

#include"Bintree.h"

/*******************************************************/ /* 已知一课棵二叉树的中序和前序序列，建立这棵树 */

/*******************************************************/ void Pre_In_order(Bintree *t,char *s,char *r)

{

char La[30],Lb[30],Ra[30],Rb[30];

int i,len;

if(s[0]!='\0')

{

*t=(Binnode *)malloc(sizeof(Binnode));

(*t)->data=s[0];

for(i=0;r[i]!=s[0];i++)

{

Ra[i]=r[i];

}

len=i;

Ra[len]='\0'; //左中

for(i=0;i<len;i++)

{

La[i]=s[i+1];

}

La[len]='\0'; //左前

for(i=len+1;i<strlen(r);i++)

{

Rb[i-len-1]=r[i];

}

Rb[i-len-1]='\0';

for(i=len+1;i<strlen(s);i++)

{

Lb[i-len-1]=s[i];

}

Lb[i-len-1]='\0';

Pre_In_order(&(*t)->lchild,La,Ra);

Pre_In_order(&(*t)->rchild,Lb,Rb);

}

else

{

*t=NULL;

}

}

int main()

{

Bintree t;

char pre[30]="ABCDEF",in[30]="CBAEDF";//测试数据 printf("输入前序遍历序列:");

scanf("%s",pre);

printf("输入中序遍历序列:");

scanf("%s",in);

Pre_In_order(&t,pre,in);

Posorder1(t);

}

#include<stdio.h>

#include<malloc.h>

typedef struct node{

int data;

struct node *lchild,*rchild,*next;

}hufnode;

typedef hufnode *linkhuf;

/****************************************************/ /* huffman树 */ /****************************************************/ linkhuf Creat_Node(int n) //创建一单链表

{

linkhuf head,pre,p;

int x;

head=NULL;

while(n--)

{

scanf("%d",&x);

p=(linkhuf)malloc(sizeof(hufnode));

p->data=x;

p->lchild=NULL;

p->rchild=NULL;

if(NULL==head)

{

head=p;

pre=head;

}

else

{

p->next=pre->next;

pre->next=p;

pre=pre->next;

}

}

return head;

}

linkhuf insert(linkhuf root , linkhuf s)//将结点S插入到有序Huffman root中。 {

linkhuf p1,p2;

if(NULL == root ) root=s;

else

{

p1=NULL;

p2=root;

while(p2&&p2->data<s->data)

{

p1=p2;

p2=p2->next;

}

s->next=p2;

if(NULL==p1)

{

root=s;

}

else

{

p1->next=s;

}

}

return root;

}

void Preorder1(linkhuf t)

{

if(t!=NULL)

{

printf("%-6d",t->data);

Preorder1(t->lchild);

Preorder1(t->rchild);

}

}

void creathuffman(linkhuf *root)//构造Huffman树。

{

linkhuf s, rl,rr;

while(*root && (*root)->next)

{

rl=*root;

rr=(*root)->next;

*root=rr->next;

s=(linkhuf)malloc(sizeof(hufnode));

s->next=NULL;

s->data=rl->data+rr->data;

s->lchild=rl;

s->rchild=rr;

rl->next=rr->next=NULL;

*root=insert(*root,s);

}

}

int main()

{

linkhuf root;

int n;

scanf("%d",&n);

root=Creat_Node(n);

creathuffman(&root);

Preorder1(root);

printf("\n");

return 0;

}

/************************************************************/ /* 按层次顺序建立一棵二叉树 */ /************************************************************/ #include"Bintree.h"

Bintree Level_Creat()

{

Bintree root,p,s;

queue node;

node.front=node.rear=0;

char ch;

ch=getchar();

if(ch==' ')

{

return NULL;

}

root=(Binnode*)malloc(sizeof(Binnode)); //生成根结点

root->data=ch;

node.data[node.rear++]=root; //用队列实现层次遍历

while(node.front<node.rear)

{

p=node.data[node.front++];

ch=getchar(); //为了简化操作，分别对左右子结点进行赋值。 if(ch!=' ')//子树不空则进队列进行扩充。下同

{

s=(Binnode*)malloc(sizeof(Binnode));

s->data=ch;

p->lchild=s;

node.data[node.rear++]=s;

}

else

{

p->lchild=NULL;

}

ch=getchar();

if(ch!=' ')

{

s=(Binnode*)malloc(sizeof(Binnode));

s->data=ch;

p->rchild=s;

node.data[node.rear++]=s;

}

else

{

p->rchild=NULL;

}

}

return root;

}

int main()

{

Bintree root;

root=Level_Creat();

Inorder1(root);//测试，中序遍历

return 0;

}