实验三二叉树及其操作算法实现.ppt

《实验三二叉树及其操作算法实现.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验三二叉树及其操作算法实现一、实验目的理解二叉树的概念掌握二叉树的构造与存储了解二叉排序树的查找二、实验原理树型结构是一类很重要的非线性数据结构，元素结点之间存在明显的分支和层次关系。树型结构在客观世界中广泛存在。数是由n个（n>=0）结点组成的有限集合，其中有且仅有一个结点称为根结点（root）,其余结点构成根结点的子树或叶子。二叉树是由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成。满二叉树种类：完全二叉树、非完全二叉树平衡二叉树、非平衡二叉树二叉树的性质1、二叉树的第i层上至多有2i-1(i>=1)个结点。

2、2、深度为h的二叉树中至多含有2h-1个结点。3、在任意二叉树中，若有n0个叶子结点，n2个度为2的结点，则必有：n0=n2+1三、实验要求：产生10个0到100之间的随机整数，依次构造一棵二叉树，并输出。四、方法说明：用三个一维数组V[n]、L[n]、R[n]存储二叉树，其中V[i]、L[i]、R[i]分别表示二叉树中某一结点的值、左子树、右子树。因此，这三个数组中的元素共同构成了二叉树中的一个结点i。在输出二叉树时，只要输出此三个数组就行了。五、算法构造算法：1、读入一个数据元素，建立一个新结点；2、若二叉树为空，则新结点为

3、根结点；3、若二叉树非空，则将新结点与根结点值比较，如果小于根结点值，则插入到左子树中，否则插入到右子树中。具体算法如下：TH←0FORK=1TOnDO{READX;V(k)←X;L(k)←R(k)←0;i=THIFi=0THENTH←kELSE{WHILE(L(i)!=k)AND(R(i)!=k)DO{IFX

4、dio.h>#include#defineN10main(){inti,j,k,tree;inta[N],v[N],l[N],r[N];for(j=1;j<=N;j++){a[j]=rand()%100;}printf("Thenumbersare:");for(j=1;j<=N;j++){printf("%d,",a[j]);}printf("");tree=0;for(k=1;k<=N;k++){v[k]=a[k];l[k]=0;r[k]=0;i=tree;if(i==0)tree=k;else{wh

5、ile((l[i]!=k)&(r[i]!=k)){if(v[k]