二叉树基本函数
一.二叉树基本函数
1.宏定义：
#include
#include
#include
#define datatypebt char
#define MAXNODE 1024
#define BOTTOMNODE 1024
#define FULLNODE 1024
2.结构体：
typedef struct bitnode
{
datatypebt data;
struct bitnode *lchild,*rchild;
}Bitnode,*Bitree;
3.基本函数：
Bitree Initiate_Bitree()
/*初始化二叉树函数1.先决条件:无2.函数作用:初始化一棵空的带头结点的二叉树,返回头结点的地址*/
{
Bitnode *bt;
bt=(Bitnode *)malloc(sizeof(Bitnode));
bt->lchild=NULL;
bt->rchild=NULL;
return bt;
}
Bitnode *Create_Bitree(datatypebt x,Bitnode *lbt,Bitnode *rbt)
/*建立二叉树函数1.先决条件:无2.函数作用:生成一棵以x为根结点数据域信息,以lbt,rbt 为左右子树的二叉树,返回新二叉树的地址*/
{
Bitree p;
p=(Bitnode *)malloc(sizeof(Bitnode));
p->data=x;
p->lchild=lbt;
p->rchild=rbt;
return p;
}
void Precreate_Bitree(Bitree *T)
/*先序构建二叉树函数1.先决条件:T是子树根结点的地址2.函数作用:以先序遍历序列构造
二叉树链表存储的二叉树T*/
{
char ch;
scanf("%c",&ch);
if(ch=='0')
*T=NULL;
else
{
(*T)=(Bitnode *)malloc(sizeof(Bitnode));
(*T)->data=ch;
Precreate_Bitree(&(*T)->lchild);
Precreate_Bitree(&(*T)->rchild);
}
}
void Preinorder_Bitree(Bitree *t,char preod[],int i,int j,char inod[],int k,int h)
/*先中序恢复树函数1.先决条件:t是子树根结点的地址2.函数作用:preod[i..j]为先序子序列,inod[k..h]为中子序序列,根据先序序列和中序序列恢复二叉树t*/
{
int m;
*t=(Bitnode *)malloc(sizeof(Bitnode));
(*t)->data=preod[i];
m=k;
while(inod[m]!=preod[i])
m++;
if(m==k)
(*t)->lchild=NULL;
else
Preinorder_Bitree(&(*t)->lchild,preod,i+1,i+m-k,inod,k,m-1);
if(m==h)
(*t)->rchild=NULL;
else
Preinorder_Bitree(&(*t)->rchild,preod,i+m-k+1,j,inod,m+1,h);
}
int Recovery_Bitree(Bitree bt,char preod[],char inod[],int n)
/*先中序恢复树函数1.先决条件:初始化二叉树,bt为头结点,拥有Preinorder_Bitree()函数2.函数作用:根据先序和中序序列恢复二叉树bt,成功返回1*/
{
if(n<=0)
bt->lchild=NULL;
else Preinorder_Bitree(&bt->lchild,preod,0,n-1,inod,0,n-1);
return 1;
}
void Postfree_Bitree(Bitree p)
/*后序释放函数1.先决条件:p为子树根结点的地址2.函数作用:释放子树p的全部空间*/
if(p==NULL)
return ;
Postfree_Bitree(p->lchild);
Postfree_Bitree(p->rchild);
free(p);
}
int Empty_Bitree(Bitree bt)
/*判空函数1.先决条件:初始化二叉树,bt为头结点2.函数作用:若二叉树bt为空,则返回1,否则返回0*/
{
if(bt->lchild==NULL)
return 1;
else return 0;
}
Bitnode *Root_Bitree(Bitree bt)
/*求根函数1.先决条件:初始化二叉树,bt为头结点2.函数作用:求二叉树bt的根结点,返回根结点的地址,若bt为空二叉树,则函数返回NULL*/
{
return bt->lchild;
}
Bitnode *Search_Bitree(Bitree bt,datatypebt x)
/*查找函数1.先决条件:初始化二叉树,bt是子树根或头结点2.函数作用:在二叉树bt中查找值为x的数据元素,成功返回其地址,找不到返回NULL*/
{
Bitree p=NULL;
if(bt)
{
if(bt->data==x)
return bt;
if(bt->lchild)
p=Search_Bitree(bt->lchild,x);
if(p)
return p;
if(bt->rchild)
p=Search_Bitree(bt->rchild,x);
if(p)
return p;
}
return NULL;
}
int InsertL_Bitree(Bitnode *parent,datatypebt x)
/*左插入函数1.先决条件:无2.函数作用:在二叉树中的parent所指结点和其左子树之间插入数据元素为x的结点,成功返回1*/
Bitnode *p;
if(parent==NULL)
{
printf("插入出错.\n");/*此句可以根据情况删除*/
return 0;
}
p=(Bitnode *)malloc(sizeof(Bitnode));
p->data=x;
p->lchild=NULL;
p->rchild=NULL;
if(parent->lchild==NULL)
parent->lchild=p;
else
{
p->lchild=parent->lchild;
parent->lchild=p;
}
return 1;
}
int InsertR_Bitree(Bitnode *parent,datatypebt x)
/*右插入函数1.先决条件:无2.函数作用:在二叉树中的parent所指结点和其右子树之间插入数据元素为x的结点,成功返回1*/
{
Bitnode *p;
if(parent==NULL)
{
printf("插入出错.\n");/*此句可以根据情况删除*/
return 0;
}
p=(Bitnode *)malloc(sizeof(Bitnode));
p->data=x;
p->lchild=NULL;
p->rchild=NULL;
if(parent->rchild==NULL)
parent->rchild=p;
else
{
p->rchild=parent->rchild;
parent->rchild=p;
}
return 1;
}
int DeleteL_Bitree(Bitnode *parent)
/*左删除函数1.先决条件:parent为子树的根结点,拥有Postfree_Bitree()函数2.函数作用:在二叉树中删除parent的左子树,成功返回1*/
{
Bitnode *p;
if(parent==NULL||parent->lchild==NULL)
{
printf("删除出错.\n");/*此句可以根据情况删除*/
return NULL;
}
p=parent->lchild;
parent->lchild=NULL;
Postfree_Bitree(p);
return 1;
}
int DeleteR_Bitree(Bitnode *parent)
/*右删除函数1.先决条件:parent为子树的根结点,拥有Postfree_Bitree()函数2.函数作用:在二叉树中删除parent的右子树,成功返回1*/
{
Bitnode *p;
if(parent==NULL||parent->rchild==NULL)
{
printf("删除出错.\n");/*此句可以根据情况删除*/
return NULL;
}
p=parent->rchild;
parent->rchild=NULL;
Postfree_Bitree(p);
return 1;
}
Bitnode *Parent_Bitree(Bitree bt,Bitnode *x)
/*求双亲函数1.先决条件:初始化二叉树bt,bt是子树根或头结点;2.函数作用:求二叉树bt中结点x的双亲结点,若结点x是二叉树的根结点或二叉树bt中无结点x,则返回NULL*/ {
Bitnode *p=NULL;
if(bt)
{
if(bt->lchild==x||bt->rchild==x)
{
p=bt;
return p;
}
p=Parent_Bitree(bt->lchild,x);
if(p)
return p;
p=Parent_Bitree(bt->rchild,x);
if(p)
return p;
}
return NULL;
}
void Visit_Bitree(Bitnode *p)
/*访问函数1.先决条件:无2.函数作用:输出一个二叉树结点p的数据*/
{
if(p)
printf("%c ",p->data);
}
int Countleaf_Bitree(Bitree bt)
/*统计叶子数函数1.先决条件:初始化二叉树,bt是子树根或头结点2.函数作用:统计二叉树bt中叶子结点的个数,返回值为bt的叶子数*/
{
if(bt==NULL)
return 0;
if(bt->lchild==NULL&&bt->rchild==NULL)
return 1;
return Countleaf_Bitree(bt->lchild)+Countleaf_Bitree(bt->rchild);
}
void Preorder_Bitree(Bitree bt)
/*先序遍历函数1.先决条件:初始化二叉树,bt是子树根或头结点;2.函数作用:用递归方法先序遍历二叉树bt*/
{
if(bt==NULL)
return;
Visit_Bitree(bt);
Preorder_Bitree(bt->lchild);
Preorder_Bitree(bt->rchild);
}
void Inorder_Bitree(Bitree bt)
/*中序遍历函数1.先决条件:初始化二叉树,bt是子树根或头结点;2.函数作用:用递归方法中序遍历二叉树bt*/
{
if(bt==NULL)
return;
Inorder_Bitree(bt->lchild);
Visit_Bitree(bt);
Inorder_Bitree(bt->rchild);
}
void Postorder_Bitree(Bitree bt)
/*后序遍历函数1.先决条件:初始化二叉树,bt是子树根或头结点;2.函数作用:用递归方法后
序遍历二叉树bt*/
{
if(bt==NULL)
return ;
Postorder_Bitree(bt->lchild);
Postorder_Bitree(bt->rchild);
Visit_Bitree(bt);
}
int NRPreorder_Bitree(Bitree bt)
/*非递归先序遍历函数1.先决条件:初始化二叉树,bt是子树根或头结点2.函数作用:非递归先序遍历二叉树bt,空树返回0,非空树返回1,栈溢出返回-1*/
{
Bitnode *p,*s[MAXNODE];/*MAXNODE最少是二叉树的层数h*/
int top=-1;
if((p=bt)==NULL)
{
printf("此为空二叉树.\n");/*此句可以根据情况删除*/
return 0;
}
while(p!=NULL||top!=-1)
{
while(p!=NULL)
{
Visit_Bitree(p);
top++;
if(top>=MAXNODE)
{
printf("栈溢出.\n");
return -1;
}
s[top]=p;
p=p->lchild;
}
p=s[top];
top--;
p=p->rchild;
}
return 1;
}
int NRInorder_Bitree(Bitree bt)
/*非递归中序遍历函数1.先决条件:初始化二叉树,bt是子树根或头结点2.函数作用:非递归中序遍历二叉树bt,空树返回0,非空树返回1,栈溢出返回-1*/
{
Bitnode *p,*s[MAXNODE];/*MAXNODE最少是二叉树的层数h*/
int top=-1;
if((p=bt)==NULL)
{
printf("此为空二叉树.\n");/*此句可以根据情况删除*/
return 0;
}
while(p!=NULL||top!=-1)
{
while(p!=NULL)
{
top++;
if(top>=MAXNODE)
{
printf("栈溢出.\n");
return -1;
}
s[top]=p;
p=p->lchild;
}
p=s[top];
Visit_Bitree(p);
top--;
p=p->rchild;
}
return 1;
}
int NRPostorder_Bitree(Bitree bt)
/*非递归后序遍历函数1.先决条件:初始化二叉树,bt是子树根或头结点2.函数作用:非递归后序遍历二叉树bt,p为当前结点指针,q为前驱结点指针,空树返回0,非空树返回1,栈溢出返回-1*/
{
Bitnode *s[MAXNODE];/*MAXNODE最少是二叉树的层数h*/
int top;
Bitnode *p,*q;
q=NULL;
p=bt;
if(!p)
return 0;
top=-1;
while(p!=NULL||top!=-1)
{
while(p!=NULL)
{
top++;
if(top>=MAXNODE)
{
printf("栈溢出.\n");
return -1;
}
s[top]=p;
p=p->lchild;
}
if(top>-1)
{
p=s[top];
if(p->rchild==NULL||p->rchild==q)
{
Visit_Bitree(p);
q=p;
top--;
p=NULL;
}
else
p=p->rchild;
}
}
return 1;
}
int Levelorder_Bitree(Bitree bt)
/*层次遍历二叉树函数1.先决条件:bt是子树根结点2.函数作用:层次遍历二叉树bt,队满溢出返回-1,空树返回0,非空树返回1*/
{
Bitnode *sq[BOTTOMNODE];/*MAXNODE最少是2^(h-1),其中h为层数*/
int front=-1,rear=0,num=0;
if(bt==NULL)
return 0;
if(num { sq[rear]=bt; num++; } else { printf("队满.\n");/*可视情况删除此句*/ return -1; } while(num) { front=(front+1)%MAXNODE; num--; Visit_Bitree(sq[front]); if(sq[front]->lchild) if(num==MAXNODE) { printf("队满.\n");/*可视情况删除此句*/ return -1; } else { rear=(rear+1)%MAXNODE; sq[rear]=sq[front]->lchild; num++; } if(sq[front]->rchild) if(num==MAXNODE) { printf("队满.\n");/*可视情况删除此句*/ return -1; } else { rear=(rear+1)%MAXNODE; sq[rear]=sq[front]->rchild; num++; } } return 1; } int Posttreedepth_Bitree(Bitree bt) /*后序二叉树高度函数1.先决条件:bt为子树根结点2.函数作用:通过后序遍历求二叉树bt 的高度,返回二叉树的高度*/ { int hl,hr,max; if(bt!=NULL) { hl=Posttreedepth_Bitree(bt->lchild); hr=Posttreedepth_Bitree(bt->rchild); max=hl>hr?hl:hr; return max+1; } else return 0; } void Pretreedepth_Bitree(Bitree bt,int h,int *depth) /*前序二叉树高度函数1.先决条件:bt是子树根结点,h为bt结点所在层次,初值为1,depth为当前求得的最大层次,调用前初值为0; 2.函数作用:通过先序遍历求二叉树bt高度*/ { if(bt!=NULL) { if(h>*depth) *depth=h; Pretreedepth_Bitree(bt->lchild,h+1,depth); Pretreedepth_Bitree(bt->rchild,h+1,depth); } } void Pretreelevel_Bitree(Bitree bt,int h) /*前序二叉树打印层号函数1.先决条件:bt是子树根结点,h为bt结点所在层次,初值为1;2.函数作用:通过先序遍历打印二叉树bt中结点和层号*/ { if(bt!=NULL) { printf("%d %c\n",h,bt->data); Pretreelevel_Bitree(bt->lchild,h+1); Pretreelevel_Bitree(bt->rchild,h+1); } } void Pretreenode_Bitree(Bitree bt,int *num) /*前序二叉树结点函数1.先决条件:bt是子树根结点,num为累计的结点数,调用前初值为0;2.函数作用:通过先序遍历求二叉树的结点数目num*/ { if(bt!=NULL) { *num=*num+1; Pretreenode_Bitree(bt->lchild,num); Pretreenode_Bitree(bt->rchild,num); } } int Print1_Bitree(Bitree bt) /*按树状打印二叉树函数1.先决条件:bt是子树根结点,拥有Posttreedepth_Bitree()函数2.函数作用:按树状打印二叉树bt*/ { int i,j,k,n,flag=1,kongge,chuduigeshu=1; Bitnode *sq[FULLNODE],*temp;/*FULLNODE最少为满二叉树结点数+1*/ int rear,front,num; if(bt==NULL) return 0; front=rear=FULLNODE-1; num=0; if(num==FULLNODE) { printf("队满.\n");/*可视情况删除此句*/ return -1; } else { rear=(rear+1)%FULLNODE; sq[rear]=bt; num++; } n=Posttreedepth_Bitree(bt); for(i=1,kongge=1;i kongge=kongge*2; for(i=1;i<=n;i++) { j=1; while(j<=chuduigeshu) { if(flag==1) { for(k=1;k printf(" ");/*因树结点的数据长度不同而不同*/ front=(front+1)%FULLNODE; temp=sq[front]; num--; if(temp) { printf("%c",temp->data);/*因二叉树数据类型不同而不同*/ if(num==FULLNODE-1) { printf("队满.\n");/*可视情况删除此句*/ return -1; } else { rear=(rear+1)%FULLNODE; sq[rear]=temp->lchild; rear=(rear+1)%FULLNODE; sq[rear]=temp->rchild; num=num+2; } } else { printf(" ");/*因树结点的数据长度不同而不同*/ if(num==FULLNODE-1) { printf("队满.\n");/*可视情况删除此句*/ return -1; } else { rear=(rear+1)%FULLNODE; sq[rear]=NULL; rear=(rear+1)%FULLNODE; sq[rear]=NULL; num=num+2; } } j++; } else for(k=1;k<=kongge;k++) printf(" ");/*因树结点的数据长度不同而不同*/ flag=-flag; } printf("\n"); kongge=kongge/2; chuduigeshu=chuduigeshu*2; flag=1; } return 1; } void Print2_Bitree(Bitree bt,int nlayer) /*按竖向树状打印二叉树函数1.先决条件:bt为子树根结点,nlayer为bt指向结点所在层次,初值为0;2.函数作用:按竖向树状打印二叉树bt*/ { if(bt==NULL) return ; Print2_Bitree(bt->rchild,nlayer+1); for(int i=0;i printf(" ");/*因树结点的数据长度不同而不同*/ printf("%c\n",bt->data);/*因树结点的数据类型不同而不同*/ Print2_Bitree(bt->lchild,nlayer+1); } 4.主函数 int main() { Bitree bt; bitnode *node,*node2; int choice,length,yezhi,high,num; char s1[1024],s2[1024]; datatypebt ch,ch2; do{ printf("********************************************************************* *****\n"); printf("1.初始化二叉树 2.建立二叉树 3.先序构建二叉树 4.先中序恢复树\n"); printf("5.后续释放树 6.判空二叉树7.求二叉树根8.查找二叉结点\n"); printf("9.左插二叉结点10.右插二叉结点11.删左二叉结点12.删右二叉结点\n"); printf("13.查找双亲结点14.访问二叉结点15.统计叶结点数16.先序遍历二叉树\n"); printf("17.中序遍历二叉树18.后序遍历二叉树19.非递归先序遍历20.非递归中序遍历\n"); printf("21.非递归后序遍历22.层次遍历二叉树23.后序求高度24.前序求高度\n"); printf("25.树状输出树26.倒树状输出树27.打印结点和层号28.求结点数\n"); printf("29.退出\n"); printf("********************************************************************* *****\n"); printf("请输入选择(1~29):"); scanf("%d",&choice); getchar(); switch(choice) { case 1:if(bt=Initiate_Bitree()) printf("初始化成功!\n"); else printf("初始化失败!\n");break; case 2:printf("请输入新二叉树结点的数据:"); scanf("%c",&ch); printf("至于指针域暂时设为NULL.\n"); node=Create_Bitree(ch,NULL,NULL); printf("新生成的二叉树结点数据和地址分别为:%c,%x\n",node->data,node); break; case 3:printf("请输入要构建的二叉树的先序序列,以'0'表示空:"); Precreate_Bitree(&bt->lchild); printf("构建成功!\n"); break; case 4:printf("请输入要恢复的二叉树的先序序列:"); gets(s1); printf("请输入要恢复的二叉树的中序序列:"); gets(s2); length=strlen(s1); if(Recovery_Bitree(bt,s1,s2,length)) printf("已恢复二叉树.\n"); break; case 5:printf("此函数在'删左二叉结点'和'删右二叉结点'里实现.\n"); break; case 6:if(Empty_Bitree(bt)) printf("二叉树为空.\n"); else printf("二叉树不为空.\n"); break; case 7:if(node=Root_Bitree(bt)) printf("根结点的数据为:%c\n",node->data); else printf("根结点为空.\n"); break; case 8:printf("请输入要查找的二叉树的数据:"); scanf("%c",&ch); if(node=Search_Bitree(bt,ch)) printf("该结点在:%x,%c\n",node,node->data); else printf("无该二叉树!\n"); break; case 9:printf("请输入要插入的数据:"); scanf("%c",&ch); getchar(); printf("请输入要插入的位置的数据:"); scanf("%c",&ch2); getchar(); if(node=Search_Bitree(bt,ch2)) if(InsertL_Bitree(node,ch)) printf("插入成功.\n"); else; else printf("插入位置出错.\n"); case 10:printf("请输入要插入的数据:"); scanf("%c",&ch); getchar(); printf("请输入要插入的位置的数据:"); scanf("%c",&ch2); getchar(); if(node=Search_Bitree(bt,ch2)) if(InsertR_Bitree(node,ch)) printf("插入成功.\n"); else; else printf("插入位置出错.\n"); break; case 11:printf("请输入要删除的位置的数据:"); scanf("%c",&ch2); if(node=Search_Bitree(bt,ch2)) if(DeleteL_Bitree(node)) printf("删除成功.\n"); else; else printf("插入位置出错.\n"); break; case 12:printf("请输入要删除的位置的数据:"); scanf("%c",&ch2); if(node=Search_Bitree(bt,ch2)) if(DeleteR_Bitree(node)) printf("删除成功.\n"); else; else printf("插入位置出错.\n"); break; case 13:printf("请输入要求孩子的结点的数据:"); scanf("%c",&ch); if(node=Search_Bitree(bt,ch)) if(node2=Parent_Bitree(bt,node)) printf("双亲结点为:%c\n",node2->data); else printf("无\n"); else printf("孩子位置出错.\n"); break; case 14:printf("此函数在后面的'遍历'实现.\n"); break; case 15:yezhi=Countleaf_Bitree(bt); printf("叶子的数目为:%d\n",yezhi); break; case 16:Preorder_Bitree(bt->lchild); printf("\n"); case 17:Inorder_Bitree(bt->lchild); printf("\n"); break; case 18:Postorder_Bitree(bt->lchild); printf("\n"); break; case 19:NRPreorder_Bitree(bt->lchild); printf("\n"); break; case 20:NRInorder_Bitree(bt->lchild); printf("\n"); break; case 21:NRPostorder_Bitree(bt->lchild); printf("\n"); break; case 22:Levelorder_Bitree(bt->lchild); printf("\n"); break; case 23:high=Posttreedepth_Bitree(bt->lchild); printf("树的高度为:%d\n",high); break; case 24:high=0; Pretreedepth_Bitree(bt->lchild,1,&high); printf("树的高度为:%d\n",high); break; case 25:Print1_Bitree(bt->lchild); break; case 26:Print2_Bitree(bt->lchild,0); break; case 27:Pretreelevel_Bitree(bt->lchild,1); break; case 28:num=0; Pretreenode_Bitree(bt->lchild,&num); printf("结点数为:%d\n",num); break; case 29:printf("谢谢使用!\n");break; default :printf("输入错误，请重新输入!\n");break; } }while(choice!=29); return 0; } 全国计算机等级考试二级公共基础之树与二叉树 1.6 树与二叉树 1.6.1 树的基本概念 树是一种简单的非线性结构。在树这种结构中，所有元素之间的关系具有明显的层次关系。用图形表示树这种数据结构时，就象自然界中的倒长的树，这种结构就用“树”来命名。如图： 在树结构中，每个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称为树的根（如R）。 在树结构中，每一个结点可以有多个后件，它们都称为该结点的子结点。没有后件的结点称为叶子结点（如W，Z，A ，L，B，N，O，T，H，X）。 在树结构中，一个结点拥有的后件个数称为结点的度（如R的度为4，KPQDEC 结点度均为2）。 树的结点是层次结构，一般按如下原则分层：根结点在第1层；同一个层所有结点的所有子结点都在下一层。树的最大层次称为树的深度。如上图中的树深度为4。R结点有4棵子树，KPQDEC结占各有两棵子树；叶子没有子树。 在计算机中，可以用树结构表示算术运算。在算术运算中，一个运算符可以有若干个运算对象。如取正（+）与取负（-）运算符只有一个运算对象，称为单目运算符；加（+）、减（-）、乘（*）、除（/）、乘幂（**）有两个运算对象，称为双目运算符；三元函数f(x,y,z)为 f函数运算符，有三个运算对象，称为三目运算符。多元函数有多个运算对象称多目运算符。 用树表示算术表达式原则是： (1)表达式中的每一个运算符在树中对应一个结点，称为运算符结点 (2)运算符的每一个运算对象在树中为该运算结点的子树(在树中的顺序从 左到右) (3)运算对象中的单变量均为叶子结点 根据上面原则，可将表达式：a*(b+c/d)+c*h-g*f表示如下的树。 树在计算机中通常用多重链表表示，多重链表的每个结点描述了树中对应结点的信息，每个结点中的链域（指针域）个数随树中该结点的度而定。 1.6.2 二叉树及其基本性质 1. 什么是二叉树 二叉树是很有用的非线性结构。它与树结构很相似，树结构的所有术语都可用到二叉树这种结构上。 二叉树具有以下两个特点： （1）非空两叉树只有一个根结点 （2）每个结点最多有两棵子树，且分别称该结点的左子树与右子树。 也就是说，在二叉树中，每一个结点的度最大为2，而且所有子树也均为二叉树。二叉树中的每一个结点可以有左子树没有右子树，也可以有右子树没有左子树，甚至左右子树都没有。 二叉树的基本操作实现及其应用 一、实验目的 1．熟悉二叉树结点的结构和对二叉树的基本操作。 2．掌握对二叉树每一种操作的具体实现。 3．学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。 4.会用二叉树解决简单的实际问题。 二、实验内容 设计程序实现二叉树结点的类型定义和对二叉树的基本操作。该程序包括二叉树结构类型以及每一种操作的具体的函数定义和主函数。 1 按先序次序建立一个二叉树， 2按（A:先序 B:中序 C:后序）遍历输出二叉树的所有结点 以上比做，以下选做 3求二叉树中所有结点数 4求二叉树的深度 三、实验步骤 ㈠、数据结构与核心算法的设计描述 /* 定义DataType为char类型 */ typedef char DataType; /* 二叉树的结点类型 */ typedef struct BitNode { DataType data; struct BitNode *lchild,*rchild; }*BitTree; 相关函数声明： 1、/* 初始化二叉树，即把树根指针置空 */ void BinTreeInit(BitTree *BT) { BT=(BitTree)malloc(sizeof(BitNode)); BT->data=NULL; cout<<"二叉树初始化成功!"< //二叉树的基本操作 #include 实验三二叉树的基本运算 一、实验目的 1、使学生熟练掌握二叉树的逻辑结构和存储结构。 2、熟练掌握二叉树的各种遍历算法。 二、实验内容 [问题描述] 建立一棵二叉树，试编程实现二叉树的如下基本操作： 1. 按先序序列构造一棵二叉链表表示的二叉树T； 2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列； 3. 求二叉树的深度/结点数目/叶结点数目；(选做) 4. 将二叉树每个结点的左右子树交换位置。（选做） [基本要求] 从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立）， [测试数据] 如输入：ABCффDEфGффFффф（其中ф表示空格字符） 则输出结果为 先序：ABCDEGF 中序：CBEGDFA 后序：CGEFDBA 层序：ABCDEFG [选作内容] 采用非递归算法实现二叉树遍历。 三、实验前的准备工作 1、掌握树的逻辑结构。 2、掌握二叉树的逻辑结构和存储结构。 3、掌握二叉树的各种遍历算法的实现。 一实验分析 本次试验是关于二叉树的常见操作，主要是二叉树的建立和遍历。二叉树的遍历有多种方法，本次试验我采用递归法，递归法比较简单。 二概要设计 功能实现 1.int CreatBiTree(BiTree &T) 用递归的方法先序建立二叉树, 并用链表储存该二叉树 2.int PreTravel(BiTree &T) 前序遍历 3. int MidTravel(BiTree &T) 中序遍历 4.int PostTravel(BiTree &T) 后序遍历 5.int Depth(BiTree &T) //计算树的深度 6.int howmuch(BiTree T,int h) 采用树节点指针数组，用于存放遍历到的元素地址，如果有左孩子，存入地址，j加一，否则没操作，通过访问数组输出层次遍历的结果。k计算叶子数，j为总节点。 7. int exchang(BiTree &T) 交换左右子树，利用递归，当有左右孩子时才交换 三详细设计 #include /*二叉树的基本参数计算*/ #include t=(BiTNode*)malloc(sizeof(BiTNode)); t->data=T->data; t1=swap(T->lchild); //交换左右子树 t2=swap(T->rchild); t->lchild=t2; t->rchild=t1; } return(t); } //求树的叶子结点数 int leafs(BiTree T) { int num1,num2; if(T==NULL) return 0; else if(T->lchild==NULL&&T->rchild==NULL) return 1; else { num1=leafs(T->lchild); num2=leafs(T->rchild); return (num1+num2); } } //求二叉树的深度 int Depth(BiTNode *T) { int dep1,dep2; if(T==NULL) return(0); else { dep1=Depth(T->lchild); dep2=Depth(T->rchild); if(dep1>dep2) return(dep1+1); else return(dep2+1); } } //按广义表形式输出二叉树 void Disptree(BiTNode *T) 数据结构二叉树基本操作 (1). // 对二叉树的基本操作的类模板封装 //------------------------------------------------------------------------------------------------------------------------ #include 实验6.1 实现二叉树各种基本运算的算法 编写一个程序algo6-1.cpp，实现二叉树的各种运算，并在此基础上设计一个主程序完成如下功能（T为如图所示的一棵二叉树）： （1）以括号表示法输出二叉树T。 （2）输出H结点的左、右孩子结点值。 （3）输出二叉树T的叶子结点个数。 （4）输出二叉树T的深度。 （5）输出对二叉树T的先序遍历序列。 （6）输出对二叉树T的中序遍历序列。 （7）输出对二叉树T的后序遍历序列。 提示：创建二叉树的算法参见书上131页的算法6.4。按先序序列输入二叉树中结点的值（一个字符），#字符表示空树。输入序列： ABD##EHJ##KL##M#N###CF##G#I## 以括号表示法输出二叉树的结果为： A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I))) 程序段 #include 实验六：二叉树及其应用 一、实验目的 树是数据结构中应用极为广泛的非线性结构，本单元的实验达到熟悉二叉树的存储结构的特性，以及如何应用树结构解决具体问题。 二、问题描述 首先，掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。其次，以二叉树表示算术表达式的基础上，设计一个十进制的四则运算的计算器。 如算术表达式：a+b*(c-d)-e/f 三、实验要求 如果利用完全二叉树的性质和二叉链表结构建立一棵二叉树，分别计算统计叶子结点的个数。求二叉树的深度。十进制的四则运算的计算器可以接收用户来自键盘的输入。由输入的表达式字符串动态生成算术表达式所对应的二叉树。自动完成求值运算和输出结果。四、实验环境 PC微机 DOS操作系统或 Windows 操作系统 Turbo C 程序集成环境或 Visual C++ 程序集成环境 五、实验步骤 1、根据二叉树的各种存储结构建立二叉树； 2、设计求叶子结点个数算法和树的深度算法； 3、根据表达式建立相应的二叉树，生成表达式树的模块； 4、根据表达式树，求出表达式值，生成求值模块； 5、程序运行效果，测试数据分析算法。 六、测试数据 1、输入数据：*（+）3 正确结果： 2、输入数据：(1+2)*3+(5+6*7); 正确输出：56 七、表达式求值 由于表达式求值算法较为复杂，所以单独列出来加以分析： 1、主要思路：由于操作数是任意的实数，所以必须将原始的中缀表达式中的操作数、操作符以及括号分解出来，并以字符串的形式保存；然后再将其转换为后缀表达式的顺序，后缀表达式可以很容易地利用堆栈计算出表达式的值。 例如有如下的中缀表达式： a+b-c 转换成后缀表达式为： ab+c- 然后分别按从左到右放入栈中，如果碰到操作符就从栈中弹出两个操作数进行运算，最后再将运算结果放入栈中，依次进行直到表达式结束。如上述的后缀表达式先将a 和b 放入栈中，然后碰到操作符“+”，则从栈中弹出a 和b 进行a+b 的运算，并将其结果d（假设为d）放入栈中，然后再将c 放入栈中，最后是操作符“-”，所以再弹出d和c 进行d-c 运算，并将其结果再次放入栈中，此时表达式结束，则栈中的元素值就是该表达式最后的运算结果。当然将原始的中缀表达式转换为后缀表达式比较关键，要同时考虑操作符的优先级以及对有括号的情况下的处理，相关内容会在算法具体实现中详细讨论。 2、求值过程 一、将原始的中缀表达式中的操作数、操作符以及括号按顺序分解出来，并以字符串的 形式保存。 二、将分解的中缀表达式转换为后缀表达式的形式，即调整各项字符串的顺序，并将括 号处理掉。 三、计算后缀表达式的值。 3、中缀表达式分解 DivideExpressionToItem()函数。分解出原始中缀表达式中的操作数、操作符以及括号，保存在队列中，以本实验中的数据为例，分解完成后队列中的保存顺序如下图所示： 《数据结构与数据库》 实验报告 实验题目 二叉树的基本操作及运算 一、需要分析 问题描述： 实现二叉树（包括二叉排序树）的建立，并实现先序、中序、后序和按层次遍历，计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目，以及二叉树常用运算。 问题分析： 二叉树树型结构是一类重要的非线性数据结构，对它的熟练掌握是学习数据结构的基本要求。由于二叉树的定义本身就是一种递归定义，所以二叉树的一些基本操作也可采用递归调用的方法。处理本问题，我觉得应该： 1、建立二叉树； 2、通过递归方法来遍历（先序、中序和后序）二叉树； 3、通过队列应用来实现对二叉树的层次遍历； 4、借用递归方法对二叉树进行一些基本操作，如：求叶子数、树的深度宽度等； 5、运用广义表对二叉树进行广义表形式的打印。 算法规定： 输入形式：为了方便操作，规定二叉树的元素类型都为字符型，允许各种字符类型的输入，没有元素的结点以空格输入表示，并且本实验是以先序顺序输入的。 输出形式：通过先序、中序和后序遍历的方法对树的各字符型元素进行遍历打印，再以广义表形式进行打印。对二叉树的一些运算结果以整型输出。 程序功能：实现对二叉树的先序、中序和后序遍历，层次遍历。计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目。对二叉树的某个元素进行查找，对二叉树的某个结点进行删除。 测试数据：输入一：ABC□□DE□G□□F□□□（以□表示空格）,查找5,删除E 预测结果：先序遍历ABCDEGF 中序遍历CBEGDFA 后序遍历CGEFDBA 层次遍历ABCDEFG 广义表打印A（B（C,D（E（,G）,F））） 叶子数3 深度5 宽度2 非空子孙数6 度为2的数目2 度为1的数目2 查找5，成功，查找的元素为E 删除E后，以广义表形式打印A（B（C,D（,F））） 输入二：ABD□□EH□□□CF□G□□□（以□表示空格）,查找10,删除B 预测结果：先序遍历ABDEHCFG 中序遍历DBHEAGFC 后序遍历DHEBGFCA 层次遍历ABCDEFHG 广义表打印A（B(D,E(H)),C(F(,G))） 叶子数3 深度4 宽度3 非空子孙数7 度为2的数目2 度为1的数目3 查找10，失败。 浙江大学城市学院实验报告 课程名称数据结构 实验项目名称实验十二叉树的基本操作 学生姓名专业班级学号 实验成绩指导老师（签名）日期 一.实验目的和要求 1、掌握二叉树的链式存储结构。 2、掌握在二叉链表上的二叉树操作的实现原理与方法。 3、进一步掌握递归算法的设计方法。 二.实验内容 1、按照下面二叉树二叉链表的存储表示，编写头文件binary_tree.h，实现二叉链表的定义与基本操作实现函数；编写主函数文件test10.cpp，验证头文件中各个操作。 二叉树二叉链表存储表示如下： typedef struct BiTNode { TElemType data ; struct BiTNode *lchild , *rchild ; }BiTNode,*BiTree ; 基本操作如下： ①void InitBiTree(BiTree &T ) //初始化二叉树T ②void CreateBiTree(BiTree &T) //按先序遍历序列建立二叉链表T ③bool BiTreeEmpty (BiTree T); //检查二叉树T是否为空，空返回1，否则返回0 ④int BiTreeDepth(BiTree T); //求二叉树T的深度并返回该值 ⑤void PreOrderTraverse (BiTree T); //先序遍历二叉树T ⑥void InOrderTraverse (BiTree T); //中序遍历二叉树T ⑦void PostOrderTraverse (BiTree T); //后序遍历二叉树T ⑧void DestroyBiTree(BiTree &T) //销毁二叉树T 二 叉 树 基 本 运 算 班级：计科112 姓名：张航 学号：201100814205辅导老师：高艳霞 二叉树的各种基本运算 一、实验目的 1、使学生熟练掌握二叉树的逻辑结构和存储结构。 2、熟练掌握二叉树的各种遍历算法。 二、实验内容 [问题描述] 建立一棵二叉树，试编程实现二叉树的如下基本操作： 1. 按先序序列构造一棵二叉链表表示的二叉树T； 2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历， 分别输出结点的遍历序列； 3. 求二叉树的深度/结点数目/叶结点数目；(选做) 4. 将二叉树每个结点的左右子树交换位置。（选做） [基本要求] 从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立）， [测试数据] 如输入：ABCффDEфGффFффф（其中ф表示空格字符）则输出结果为 先序：ABCDEGF 中序：CBEGDFA 后序：CGEFDBA 层序：ABCDEFG [选作内容] 采用非递归算法实现二叉树遍历。 三、实验步骤 1.程序源码 #include 本程序由SOGOF完成 该完整程序主要是递归函数的使用及模板的使用，完成了对二叉树基本的链表操作，主要有二叉树的建立，前序、中序、后序遍历，求树的高度，每层结点数（包含树的最大宽度），左右结点对换，二叉树的内存释放，求解树的叶子数。 #include 二叉树的基本操作及实现 二叉树的基本操作及实现的代码如下： #include 创作编号： GB8878185555334563BT9125XW 创作者：凤呜大王* //二叉树的基本操作 #include cout<<"--------------请选择------------"< [1996] 设t 为一棵二叉树的根结点地址指针，试设计一个非递归算法完成把二叉树中每个结点的左右孩子位置交换。 int swithLRChild(BiTree *t) { BiTree *stack[100] = {0}; int stack_length = 0; if (NULL == t){ return 0; } stack[stack_length++] = t; while (stack_length > 0){ //pop stack BiTree *node = stack[stack_length - 1]; stack_length -= 1; BiTree *temp = node ->lchild; node->lchild = node ->rchild; node->rchild = temp; if (NULL != node ->rchild){ stack[stack_length++] = node ->rchild;} if (NULL != node ->lchild){ stack[stack_length++] = node ->lchild; } } return 1; } [1998]一棵高度为K 且有n个结点的二叉排序树，同时又是一棵完全二叉树存于向量t 中，试设计删除树中序号为i 且具有左右孩子的一个结点，而不使存储量增加保证仍为二叉排序树(不一定是完全二叉树)的算法。 //存数据的位置是从 1 的索引开始的，避免需要访问索引为0 的空间，避免需要频繁的索引 转换 void delNodeInSortedBiTree(int *sorted_bitree, int *last_index,int i) { //因为题目中描述具有左右孩子，所以直接从左孩子的最右边叶子节点开始//分两种情况，左孩子没有右孩子，那么左孩子之后的节点都移动一个位子//左孩子存在右孩子，则从右孩子的左孩子一直走，到叶子节点停止，因为是叶子节点//就不需要移动元素了 int del_node_index = 2*i; if (2*del_node_index + 1 >= *last_index) 二叉树的创建与遍历 一、实验目的 1．学会实现二叉树结点结构和对二叉树的基本操作。 2．掌握对二叉树每种操作的具体实现，学会利用递归和非递归方法编写对二叉树这种递归数据结构进行处理的算法。 二、实验要求 1．认真阅读和掌握和本实验相关的教材内容。 2．编写完整程序完成下面的实验内容并上机运行。 3．整理并上交实验报告。 三、实验内容 1．编写程序任意输入二叉树的结点个数和结点值，构造一棵二叉树，采用三种递归和非递归遍历算法(前序、中序、后序)对这棵二叉树进行遍历。 四、实验步骤 源程序代码1 #include 二项式期权定价模型 1.实验名称： 二项式期权定价模型 2.实验目的： 利用二叉树期权定价模型公式Excel 模板计算期权价格。 3.基本原理 计算到期时资产价值的分布，求出资产的期望值，用适当的贴现率计算现值，得到资产的当前价值。 （1） 计算n 期中上升i 次的概率： ()(1)i i n i i n P n C p p -=-； （2） 计算在终期时的价格分布： ()0i n i ni S S u d -= （3） 计算期权的价值： ()0max(,0)i n i ni Call S u d K -=-，()0max(,0)i n i ni Put K S u d -=-； （4）计算终期时的期望值：0 ()n n ni i ECall P i Call ==∑， ()n n ni i EPut P i put ==∑； （5）计算期权在起初时刻的价值： ()00 (1)max(,0)n RT RT i i n i i n i n i Call e ECall e C p p S u d K ----===--∑ ()00 (1)max(,0)n RT RT i i n i i n i n i Put e EPut e C p p K S u d ----===--∑。 4. 实验数据域内容 已知股票价格为50，执行价格为50，时间为半年，无风险利率为5%，波动率为20%， 分为10个时间段，利用二叉树定价模型计算看涨看跌期权的价格。 5. 操作过程与结果 （1）定义变量的符号 在单元格B2—B14中分别输入S 、K 、T 、R 、VOL 、n 、dt 、u 、d 、G-factor 、D-factor 、p 分别表示股票价格、期权执行价格、期权有效期、无风险利率、股价波动率、时段数、时段、上升因子、下降因子、增长因子、贴现因子、风险中性概率。如图： 实验五-二叉树基本操作的编程实现实验报告 ————————————————————————————————作者：————————————————————————————————日期： HUBEI UNIVERSITY OF AUTOMOTIVE TECHNOLOGY 数据结构 实验报告 这里一定填 写清楚自己 实验项目实验五实验类别基础篇 学生姓名朱忠栋学生学号20120231515 完成日期2014-12-16 指导教师付勇智 实验成绩评阅日期 评阅教师 实验五二叉树基本操作的编程实现 【实验目的】 内容：二叉树基本操作的编程实现 要求： 二叉树基本操作的编程实现（2学时，验证型），掌握二叉树的建立、遍历、插入、删除等基本操作的编程实现，也可以进一步编程实现查找等操作，存储结构主要采用顺序或链接结构。也鼓励学生利用基本操作进行一些应用的程序设计。 【实验性质】 验证性实验（学时数：2H） 【实验内容】 以下的选题都可以作为本次实验的推荐题目 1.建立二叉树，并以前序遍历的方式将结点内容输出。 2.将一个表示二叉树的数组结构转换成链表结构。 3.将表达式二叉树方式存入数组，以递归方式建立表达式之二叉树状结构，再分别输出前序、中序 及后序遍历结果，并计算出表达式之结果。 【注意事项】 1.开发语言：使用C。 2.可以自己增加其他功能。 【实验分析、说明过程】 页面不够，可续页。 根据自己选择的层次不同的实验内容，完善程序代码，调试通过后，分析说明该问题处理的详细算法过程。不需要写出详细的代码，只表达清楚详细的处理算法即可。可以采用流程图、形式语言或者其他数学表达方式来说明。 这次实验考查的主要是：递归建立二叉树，递归输出先序，中序和后序遍历的结果；非递归建立二叉树，再以非递归方式分别输出先序，中序和后序遍历的结果。 而对于基础篇考查的主要是：递归建立二叉树，递归输出先序，中序和后序遍历的结果，是以填空的方式进行考查的。 对于第一空：递归实现的先序遍历，其实现方法是： printf("%d",p->data); if(p->lchild!=NULL) preorder(p->lchild); if(p->rchild!=NULL) preorder(p->rchild); 对于第二空：递归实现的中序遍历，其实现方法是： if(p->lchild!=NULL) inorder(p->lchild); printf("%d",p->data); if(p->rchild!=NULL) inorder(p->rchild); 对于第三空：递归实现的后序遍历，其实现方法是： if(p->lchild!=NULL) postorder(p->lchild); if(p->rchild!=NULL) postorder(p->rchild); printf("%d",p->data); 【思考问题】 页面不够，可续页。 1.二叉树是树吗？它的定义为什么是递归的？ 答：最多有两棵子树的有序树，称为二叉树。二叉树是一种特殊的树。具有n个结点的完全二叉树的深度为log2n +1 ！！！二叉树的计算方法：若一棵二叉树为空,则其深度为0, 二叉树的基本操作实验报告 学号姓名实验日期 2012-12-26 实验室计算机软件技术实验指导教师设备编号 401 实验内容二叉树的基本操作 一实验题目 实现二叉树的基本操作的代码实现 二实验目的 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， // (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的叶子结点数。全国计算机等级考试二级公共基础之树与二叉树1
实验三 二叉树的基本操作实现及其应用
二叉树的基本 操作
二叉树的基本操作实验
二叉树的基本参数计算
数据结构——二叉树基本操作源代码
二叉树课程设计
数据结构实验二叉树
数据结构实验三——二叉树基本操作及运算实验报告
实验10 二叉树的基本操作
二叉树运算实验报告
二叉树基本操作经典实例
二叉树的基本操作及实现.cpp
二叉树的基本 操作
东北大学计算机初试历年二叉树算法题目及解答
C++二叉树的创建与遍历实验报告
二叉树定价模型
实验五-二叉树基本操作的编程实现实验分析报告
二叉树的基本操作实验报告