实验树和叉树的操作.doc

实验四树和二叉树的操作一、实验题目:用菜单驱动的手法,编写一个完整的程序,生成一棵二叉树,求二叉树的高度,求二叉树的叶子结点数,输出二叉树的所有结点。二、实验算法描述:二叉树的生成是指如何在内存中建立二叉树的存储结构。建立顺序存储结构的问题较简单,这里仅讨论如何建立二叉链表。要建立二叉链表,就需要按照某种方式输人二叉树的结点及其逻辑信息。注意到对二叉树遍历时,不仅得到了结点信息,而且由序列中结点的先后关系还可获得一定的逻辑信息,如果这些信息足够,就可根据遍历序列生成相应的二叉树资料个人收集整理,勿做商业用途二叉树的生成方法就是基于遍历序列的,相当于遍历问题的逆问题,即由遍历序列反求二叉树,这需要分析和利用二叉树遍历序列的特点。在下列两种方法中任选一种。资料个人收集整理,勿做商业用途**以下的(一)(二)要编写在一个完整的程序中。如果你不能编在一个程序中,则可以用两个完整的程序来实现。资料个人收集整理,勿做商业用途(一)用先根序列建立二叉树二叉树的结点就按相应的遍历过程逐个生成。类似层次遍历,如果不对遍历序列作些补充,是不能完整反映结点间的逻辑关系的,也就不能得到正确的结果。补充的方法也是增加虚结点,但这里只需对空指针对应的位置进行补充,而不必补充到完全二叉树的形式。以先根遍历上图为例,二叉树的先根输入序列为:资料个人收集整理,勿做商业用途******@G@@***@CE@***@FH@@@其中@表示虚结点,这里不需要结束符。算法过程为,先生成根结点,再生成左子树,然后是右子树,左右子树的生成采用递归。在具体作本实验时,还需编写一个主函数调用这个函数来生成二叉树,最后输出二叉树的结点序列。资料个人收集整理,勿做商业用途(二)按完全二叉树的层次顺序,依次输入结点信息来建立二叉链表这是因为完全三叉树的层次遍历序列中,结点间的序号关系可反映父子关系即逻辑关系。对一般的二又树,要补充若干个虚结点使其成为完全二叉树后,冉按其层次顺序输入。例如,仅含3个结点A、B、C的右单支树(见下图2),按完全二叉树的形式输入的结点序列为:******@B@@***@C#,其中@表示虚结点,#表示输入结束。资料个人收集整理,勿做商业用途算法的基本思想是:依次输入结点信息,若输入的结点不是虚结点,则建立一个新结点:若新结点是第1个结点,则令其为根结点;否则将新结点作为孩子链接到它的双亲结点上。如此重复下去,直至输入字符“#”为止。资料个人收集整理,勿做商业用途这里的关键是新结点与其双亲的链接。由于是按层次自左至右输入结点的,所以先输入的结点,其孩子也必定较先输入。即结点与其孩子具有先进先出的特点,于是可设置一个队列,保存已输人结点的地址。这样,队尾是当前正输入的结点,队头是其双亲结点。当队头结点的两个孩子都输入完毕后,出队,新的队头是下一个要输入孩子的双亲结点。如此下去,直到输入结束符为止。资料个人收集整理,勿做商业用途双亲与孩子的链接方法是:若当前输入的结点编号是偶数,则该结点作为左孩子与其双亲链接;否则作为右孩子与其双亲链。若双亲结点或孩子结点为虚结点,则无需链接。资料个人收集整理,勿做商业用途实验程序如下:#include<>#include<>#include<>#include<>intcmp(constvoid*a,constvoid*b){return*(int*)a-*(int*)b;}typedefchardatatype;typedefstructtreenode{datatypedata;structtreenode*leftchild,*rightchild;}treenode,*bitree;treenode*t;intcount=0;//建立二叉树方法1treenode*creattree_1(){treenode*t,*p,*v[100]; inti,j; datatypee; t=NULL;printf("\n请输入初始二叉树各结点的编号和对应的值(如1,a):");scanf("%d,%c",&i,&e);while(i!=0&&e!='#'){p=(treenode*)malloc(sizeof(treenode));p->data=e; p->leftchild=NULL; p->rightchild=NULL;v[i]=p;if(i==1){t=p;}else {j=i/2;if(i%2==0){v[j]->leftchild=p;} else{v[j]->rightchild=p;}}printf("\n请继续输入(以0,#结束):");scanf("%d,%c",&i,&e);}return(t);}//建立二叉树方法2treenode*creattree_2(){treenode*t