数据结构实验报告

实验题目 二叉树的基本操作

一、 实验目的与要求

实验目的：

1、实现二叉树的各种运算。

2、实现二叉树的各种遍历。

实验要求：

完成课本实验题7.1、实验题7.2要求实现的各项功能。

二、 实验方案

实验7-1

//文件名：algo7-1.cpp

#include

#include

#define MaxSize 100

typedef char ElemType;

typeder struct node

{ ElemType data;

struct node*lchild;

struct node*rchild;

}BTNode;

void CreateBTNode(BTNode *&b,char *str)

{ BTNode *St[MaxSize]，*p=NULL;

int top=-1,k,j=0;

char ch;

b=NULL;

ch=str[j];

while(ch!='\\0')

{ switch(ch)

{

case '(':top++;St[top]=p;k=1;break;

case')':top--;break;

case',':k=2;break;

default:p=(BTNode*)malloc(sizeof(BTNode));

p->data=ch;p->lchild=p->rchild=NULL;

if(b==NULL)

b=p;

else

{ switch(k)

{

case1:St[top]->lchild=p;break;

case2:St[top]->rchild=p;break;

}

}

}

j++;

ch=str[j];

}

}

BTNode*FindNode(BTNode*b,ElemType x)

{ BTNode*p;

if(b==NULL)

return NULL;

else if(b->data==x)

return b;

else

{ p=FindNode(b->lchild,x);

if(p!=NULL)

return b;

else

return FindNode(b->rchild,x);

}

}

BTNode*LchildNode(BTNode *p)

{

return p->lchild;

}

BTNode*RchildNode(BTNode *p)

{

return p->rchild;

}

int BTNodeDepth(BTNode *b)

{ int lchilddep,rchilddep;

if (b==NULL)

return(0);

else

{ lchilddep=BTNodeDepth(b->lchild);

rchilddep=BTNodeDepth(b->rchild);

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

}

}

void DispBTNode(BTNode*b)

{ if(b!=NULL)

{ printf(\"%c\",b->data);

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

{ printf(\"(\");

DispBTNode(b->lchild);

if(b->rchild!=NULL) printf(\);

DispBTNode(b->rchild);

printf(\")\");

}

}

}

int BTWidth(BTNode*b)

{struct

{ int lno;

BTNode*p;

}Qu[MaxSize];

int front,rear;

int lnum,max,i,n;

front=rear=0;

if(b!=NULL)

{ rear++;

Qu[rear].p=b;

Qu[rear].lno=1;

while(rear!=front)

{ front++;

b=Qu[front].p;

lnum=Qu[front].lno;

if(b->lchild!=NULL)

{ rear++;

Qu[rear].p=b->lchild;

Qu[rear].lno=lnum+1;

}

if(b->rchild!=NULL)

{ rear++;

Qu[rear].p=b->rchild;

Qu[rear].lno=lnum+1;

}

}

max=0;lnum=1;i=1;

while(i<=rear)

{ n=0;

while(i<=rear&&Qu[i].lno==lnum)

{

n++;i++;

}

lnum=Qu[i].lno;

if(n>max)max=n;

}

return max;

}

else

return 0;

}

int Nodes(BTNode*b)

{ int num1,num2;

if(b==NULL)

return 0;

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

return 1;

else

{ num1=Nodes(b->lchild);

num2=Nodes(b->rchild);

return (num1+num2+1);

}

}

int LeafNodes(BTNode*b)

{ int num1,num2;

if(b==NULL)

return 0;

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

return 1;

else

{ num1=LeafNodes(b->lchild);

num2=LeafNodes(b->rchild);

return(num1+num2);

}

}

void DestroyBTNode(BTNode*&b)

{ if(b!=NULL)

{ DestroyBTNode(b->lchild);

DestroyBTNode(b->rchild);

free(b);

}

}

//文件名：exp7-1.cpp:

#include

typedef char ElemType;

typeder struct node

{ ElemType data;

struct node*lchild;

struct node*rchild;

}BTNode;

extern void CreateBTNode(BTNode *&b,char *str);

extern BTNode*FindNode(BTNode*b,ElemType x);

extern BTNode*LchildNode(BTNode *p);

extern BTNode*RchildNode(BTNode *p);

extern int BTNodeDepth(BTNode *b);

extern void DispBTNode(BTNode*b);

extern int BTWidth(BTNode*b);

extern int Nodes(BTNode*b);

extern int LeafNodes(BTNode*b);

extern void DestroyBTNode(BTNode*&b);

void main()

{ BTNode *b,*p,*lp,*rp;

CreateBTNode(b,\"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))\");

printf(\"二叉树的基本运算如下：\\n\");

printf(\"(1)输出二叉树:\");DispBTNode(b);printf(\"\\n\");

printf(\"(2)H节点:\");

p=FindNode(b,'H');

if(p!=NULL)

{ lp=LchildNode(p);

if(lp!=NULL)

printf(\"左孩子为%c\",lp->data);

else

printf(\"无左孩子\");

rp=RchildNode(p);

if(rp!=NULL)

printf(\"右孩子为%c\",rp->data);

else

printf(\"无右孩子\");

}

printf(\"\\n\");

printf(\" (3)二叉树b的深度：%d\\n\",BTNodeDepth(b));

printf(\" (4)二叉树b的宽度：%d\\n\",BTWidth(b));

printf(\" (5)二叉树b的节点个数：%d\\n\",Nodes(b));

printf(\" (6)二叉树b的叶子节点个数：%d\\n\",LeafNodes(b));

printf(\" (7)释放二叉树b\\n\");

DestroyBTNode(b);

}

实验7-2

/*文件名:exp7-2.cpp*/

#include

#include

#define MaxSize 100

typedef char ElemType;

typedef struct node

{

ElemType data; /*数据元素*/

struct node *lchild; /*指向左孩子*/

struct node *rchild; /*指向右孩子*/

} BTNode;

extern void CreateBTNode(BTNode *&b,char *str);

extern void DispBTNode(BTNode *b);

void PreOrder(BTNode *b) /*先序遍历的递归算法*/

{

if (b!=NULL)

{

printf(\"%c \访问根结点*/

PreOrder(b->lchild); /*递归访问左子树*/

PreOrder(b->rchild); /*递归访问右子树*/

}

}

void PreOrder1(BTNode *b)

{

BTNode *p;

struct

{

BTNode *pt;

int tag;

} St[MaxSize];

int top=-1;

top++;

St[top].pt=b;St[top].tag=1;

while (top>-1) /*栈不空时循环*/

{

if (St[top].tag==1) /*不能直接访问的情况*/

{

p=St[top].pt;

top--;

if (p!=NULL)

{

top++; /*右孩子进栈*/

St[top].pt=p->rchild;

St[top].tag=1;

top++; /*左孩子进栈*/

St[top].pt=p->lchild;

St[top].tag=1;

top++; /*根结点进栈*/

St[top].pt=p;

St[top].tag=0;

}

}

if (St[top].tag==0) /*直接访问的情况*/

{

printf(\"%c \

top--;

}

}

}

void PreOrder2(BTNode *b)

{

BTNode *St[MaxSize],*p;

int top=-1;

if (b!=NULL)

{

top++; /*根结点入栈*/

St[top]=b;

while (top>-1) /*栈不为空时循环*/

{

p=St[top]; /*退栈并访问该结点*/

top--;

printf(\"%c \

if (p->rchild!=NULL) {

top++;

St[top]=p->rchild;

}

if (p->lchild!=NULL) {

top++;

St[top]=p->lchild;

}

}

printf(\"\\n\");

/*右孩子入栈*/

/*左孩子入栈*/

}

}

void InOrder(BTNode *b) /*中序遍历的递归算法*/

{

if (b!=NULL)

{

InOrder(b->lchild); /*递归访问左子树*/

printf(\"%c \访问根结点*/

InOrder(b->rchild); /*递归访问右子树*/

}

}

void InOrder1(BTNode *b)

{

BTNode *p;

struct

{

BTNode *pt;

int tag;

} St[MaxSize];

int top=-1;

top++;

St[top].pt=b;St[top].tag=1;

while (top>-1) /*栈不空时循环*/

{

if (St[top].tag==1) /*不能直接访问的情况*/

{

p=St[top].pt;

top--;

if (p!=NULL)

{

top++; /*右孩子进栈*/

St[top].pt=p->rchild;

St[top].tag=1;

top++; /*根结点进栈*/

St[top].pt=p;

St[top].tag=0;

top++; /*左孩子进栈*/

St[top].pt=p->lchild;

St[top].tag=1;

}

}

if (St[top].tag==0) /*直接访问的情况*/

{

printf(\"%c \

top--;

}

}

}

void InOrder2(BTNode *b)

{

BTNode *St[MaxSize],*p;

int top=-1;

if (b!=NULL)

{

p=b;

while (top>-1 || p!=NULL)

{

while (p!=NULL)

{

top++;

St[top]=p;

p=p->lchild;

}

if (top>-1)

{

p=St[top];

top--;

printf(\"%c \

p=p->rchild;

}

}

printf(\"\\n\");

}

}

void PostOrder(BTNode *b) /*后序遍历的递归算法*/

{

if (b!=NULL)

{

PostOrder(b->lchild); /*递归访问左子树*/

PostOrder(b->rchild); /*递归访问右子树*/

printf(\"%c \访问根结点*/

}

}

void PostOrder1(BTNode *b)

{

BTNode *p;

struct

{

BTNode *pt;

int tag;

} St[MaxSize];

int top=-1;

top++;

St[top].pt=b;St[top].tag=1;

while (top>-1) /*栈不空时循环*/

{

if (St[top].tag==1) /*不能直接访问的情况*/

{

p=St[top].pt;

top--;

if (p!=NULL)

{

top++; /*根结点进栈*/

St[top].pt=p;

St[top].tag=0;

top++; /*右孩子进栈*/

St[top].pt=p->rchild;

St[top].tag=1;

top++; /*左孩子进栈*/

St[top].pt=p->lchild;

St[top].tag=1;

}

}

if (St[top].tag==0) /*直接访问的情况*/

{

printf(\"%c \

top--;

}

}

}

void PostOrder2(BTNode *b)

{

BTNode *St[MaxSize];

BTNode *p;

int flag,top=-1; if (b!=NULL)

/*栈指针置初值*/

{

do

{

while (b!=NULL) /*将t的所有左结点入栈*/

{

top++;

St[top]=b;

b=b->lchild;

}

p=NULL; /*p指向当前结点的前一个已访问的结点*/

flag=1; /*设置b的访问标记为已访问过*/

while (top!=-1 && flag)

{

b=St[top]; /*取出当前的栈顶元素*/

if (b->rchild==p) /*右子树不存在或已被访问,访问之*/

{

printf(\"%c \访问*b结点*/

top--;

p=b; }

else

{

b=b->rchild; flag=0; }

}

} while (top!=-1);

printf(\"\\n\");

/*p指向则被访问的结点*/

/*t指向右子树*/

/*设置未被访问的标记*/

}

}

void TravLevel(BTNode *b)

{

BTNode *Qu[MaxSize]; int front,rear; front=rear=0; if (b!=NULL)

printf(\"%c \

rear++; Qu[rear]=b;

while (rear!=front) {

front=(front+1)%MaxSize;

/*定义循环队列*/

/*定义队首和队尾指针*/

/*置队列为空队列*/

/*结点指针进入队列*/

/*队列不为空*/

b=Qu[front]; /*队头出队列*/

if (b->lchild!=NULL) /*输出左孩子,并入队列*/

{

printf(\"%c \

rear=(rear+1)%MaxSize;

Qu[rear]=b->lchild;

}

if (b->rchild!=NULL) /*输出右孩子,并入队列*/

{

printf(\"%c \

rear=(rear+1)%MaxSize;

Qu[rear]=b->rchild;

}

}

printf(\"\\n\");

}

void main()

{

BTNode *b;

CreateBTNode(b,\"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))\");

printf(\" 二叉树b:\");DispBTNode(b);printf(\"\\n\\n\");

printf(\" 层次遍历序列:\");

TravLevel(b);

printf(\"\\n\");

printf(\" 先序遍历序列:\\n\");

printf(\" 递归算法:\");PreOrder(b);printf(\"\\n\");

printf(\" 非递归算法1:\");PreOrder1(b);printf(\"\\n\");

printf(\" 非递归算法2:\");PreOrder2(b);printf(\"\\n\");

printf(\" 中序遍历序列:\\n\");

printf(\" 递归算法:\");InOrder(b);printf(\"\\n\");

printf(\" 非递归算法1:\");InOrder1(b);printf(\"\\n\");

printf(\" 非递归算法2:\");InOrder2(b);printf(\"\\n\");

printf(\" 后序遍历序列:\\n\");

printf(\" 递归算法:\");PostOrder(b);printf(\"\\n\");

printf(\" 非递归算法1:\");PostOrder1(b);printf(\"\\n\");

printf(\" 非递归算法2:\");PostOrder2(b);printf(\"\\n\");

}

三、 实验结果

实验7-1程序的运行结果如图所示：

实验7-2程序的运行结果如图所示：

四、 结论

（1）.在实验7-1中，程序的运行结果分为6个部分，输出二叉树用的是括号表示法；求H节点的左孩子和右孩子分别是J和K；二叉树b的深度，即是二叉树的高度，总共有7层；节点个数，包括根节点、孩子节点和叶子节点，由二叉树的图形可以直接看出是14个；二叉树的叶子节点个数，即是最下一层的节点个数，共有6个。最后一个步骤是释放二叉树，即释放存储空间。

（2）.在实验7-2中，程序的运行结果分为5大部分，首先是输入二叉树b,然后分别采用层次遍历、先序遍历、中序遍历和后序遍历二叉树，层次遍历算法是访问根节点（第1层），然后从左到右访问第2层的所有节点，最后从左到右访问第3层的所有节点、……、第h层的所有节点。先序遍历算法是先访问根节点，然后先序遍历左子树，最后先序遍历右子树。中序遍历算法是中序遍历左子树，然后访问根节点，最后中序遍历右子树。后序遍历算法则是后序遍历左子树，然后后序遍历右子树，最后访问根节点。

其中，先序、中序和后序遍历算法都运用了递归和非递归算法。

五、 问题与讨论

在完成本次实验7-1,7-2的过程中，大多数算法是课本上有源代码的，不过为了更好地锻炼和培养自己的动手能力和逻辑思维能力，我尝试着一边画图，在调试的时候不断修改程序，以便使运行结果更加可靠和准确。2个实验大量地运用到了循环体语句，如if……else循环，while循环等，这些都是基础知识，但在很多程序中不可避免地要用到，之前的Ｃ＋＋课程知识的积累在学习数据结构这一门课程中大有帮助，由此也看出牢固地掌握基础知识并在其他地方中加以运用，不断修正和创新才会有更大的收获。