二叉树.txt

二叉数

数据结构课程设计报告
班级：计算机032班		   姓名：彭福原 		 学号：19


题目 : 排序二叉树的应用


一、设计任务
1、	程序在运行时，可以执行有关排序二叉树的操作：如插入一个元素、删除一个元素、查找一个元素、打印一个元素等。
2、	用递归算法遍历二叉树。


二 、设计分析

1 、 二叉树是n（n>=0）个结点的有限集合，它或为空树（n=0），或由一个根结点和两棵分别称为根的左子树和右子树的互不相交的二叉树组成。二叉树是一个递归定义。一棵深度为k且有2k-1个结点的二叉树称为满二叉树。对满二叉树的结点进行连续编号，约定编号从根结点起，自上而下，自左而右。

2 、 二叉树的存储结构
1） 顺序存储结构：二叉树可以采用顺序存贮结构，即用一维数组来存放二叉树的数据元素。它是按照满二叉树的结点层次编号层次来依次存放二叉树中的数据元素。
2）链式存储结构：设计不同的结点结构可构成不同形式的链式存储结构。
在本程序中，采用顺序存储结构，对二叉树进行插人、删除、查找、遍历等操作。

3 、 二叉树的建立
已知一棵二叉树，共有n个结点，建立的方法如下：
1）	照完全二叉树的编号方法，对该二叉树进行编号。
2）	次输入一个结点的值x和该结点的编号k，动态申请一块空间来存放该结点，空间的地址为p。
3）	把p值赋给adr[k]中。
4）	如果k=1，转到5；否则，把p的值填入其父结点的指针域中。p的父结点地址为adr[k/2]，若k为偶数，则做adr[k/2]->lc=p；若为奇数，则做adr[k/2]->rc=p。
5）	重复2~4，直到全部顶点数据输入完为止。

4 、 遍历二叉树，即如何按某条搜索路径寻访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。
一棵非空二叉树是由根结点（D）、左子树（L）和右子树（R）三个基本部分组成。要遍历这三个基本部分，可以有六种可能的顺序。若限定先左后右，则只有三种情况：先序遍历（DLR）、中序遍历（LDR）、后序遍历（LRD）。
在本程序中，遍历二叉树函数的核心是以一个简单的case语句来实现的。

5 、 二叉树的插入操作：这个操作首先生成一个新的结点结构，把数据存入新结点，然后搜索二叉树寻找插入结点的位置，再把新结点连接到二叉树。把这个操作定义为一个函数，其函数名为instree。

6 、 二叉树中元素的查找：在许多情况下，我们需要在一棵已知的二叉树中查找某个元素，以确定树中是否存在这个元素。这种查找与链表数据结构中查找成员的情况极类似。查找函数名字定义为membertree。

7 、 从二叉树中删除一个成员：进行成员删除操作时，首先必须用递归函数遍历这棵树，找到这个元素。当找到这个元素之后，还要考虑以下四种不同的情况：删除一个终端结点；删除只有一个左孩子的结点；删除只有一个右孩子的结点；删除带有两个孩子的结点。删除函数名字定义为deltree。

8 、 在主函数main( )中，除了初始化指针tp之外，用循环语句while(1)在屏幕上显示出主菜单：
				I ——Insert an element into tree
				D——Delete an element from the tree
F——Find a member in the tree
P——Print the tree
Q——Quit
用户可以根据自己的需要，从键盘键入不同的合法字母（例如‘I’），而进入不同的树处理函数进行处理。
不同树处理函数的选择是通过简单的switch－case语句来实现，其中包括了若错技术。如果用户从键盘输入的不是’I’，’D’，’F’，’P’，’Q’这些合法字符，则程序会先告诉用户输入出错，让用户重新输入，直到输入选择正确为止。


三 、设计思路
1 、主函数main() ：由case语句组成，支持程序选择，当运行时，可以执行有关二叉树的操作：如插入一个元素、删除一个元素、查找一个元素、打印一个元素等。

2 、主要的树函数的说明部分
1）void prttree(treeptr tnode,int t)；//打印树。该函数在屏幕上打印出存放在树中的元素，如果是空树，则无输出。
参数：tnode-指向根结点的指针；
      t-打印方式：0：前序  	1：中序 	2：后序（用递归算法遍历二叉树）。
	  
2）treeptr instree(char *s,int key,treeptr tnode)；//插入一个元素。该函数把一个元素插入到二叉树中。
参数：s,key-接收插入数据；
      tnode-是指向根结点的指针。

3）treeptr membertree(char *s,treeptr tnode)；//查找一个元素。该函数测定树中的指定元素，如果元素是树中的成员，则函树返回该元素，否则返回NULL指针.。
参数：s-指向要找的那个串的指针；
tnode-指向树根结点的指针。

4）treeptr deltree(char *s,treeptr tnode)；//删除一个元素。该函数删除一个结点。
参数：s-要删除的结点的数据域的值；
      tnode-指向根结点的指针。

5）treeptr findinspos(char *s,treeptr tnode)；//该函数寻找一个元素要插入的位置。










四 、流程图
1、main( ) 函 数




                        ‘I’          ‘P’  ‘D ’     ‘F’              ‘Q’
                                                            其
                                                               它
	输   入	输   入 s
                                             s                 
		         printf        

	          tp==deltree
          Y    	N		       (s,tp)       	t==membe       
                                              	-tree(s,tp)

                         
    printf                  printf	         break               
                                         	Y	t!=NULL	N
                           
    	
输     入                           printf                 printf
任 意 数	输 入 i


               break	输   入
                                                        任  意  数
	prttree(tp,i)
		break

	输入任意数	
	

	break

	



	



        
2、主 要 树 函 数

1）	prttree( ) 函 数
                              开 始


                                  tnode
                      Y      !=NULL         N


t

          ‘0’      ‘1’      ‘2’

	prttree(tnod	prttree(tnode
printf	-e->left,t)              ->left,t)


prttree(tnod            printf	prttree(tnod
-e->left,t)	-e->right,t)


prttree(tnod 	prttree(tnod
-e->right,t)           -e->right,t)	printf





	结  束













2) instree( ) 函 数
 



	为t1分配
空  间

                          
Y      t1==NULL     N
                       

printf                     t1->right
	=NULL

	
	printf		t1->left=NULL
	

	return		t1->key
(tnode)	        =key
                                           

strcpy(t1->data,s)


	Y	tnode==NULL  N
		  

	return		t2=findinspos(s,tonde)
                                   (t1)

                                          Y     (strcmp(t2-data,s))<=0  N


	t2->right=t1                 t2->left=t1



	return(tnode)


	结 束
3) membertree( ) 函 数
                           开 始 


	t=tnode

                                               N
t!=NULL
                               Y

	cmp=strcmp(t->data,s)



Y     cmp==0     N

	return(t)	Y    cmp<0       N

	t=t->right              t=t->left




                           return(NULL)


	结 束

4) findinspos( ) 函 数

	开 始


	Y	(strcmp(tnode->data,s))>=0	N

Y  tnode->left==NULL   N	Y	tnode->right==NULL	 N
       
return(tnode)       findinspos(s,tnode->left)		return(tnode)     findinspos(s,tnode->right)




                             结 束

5) deltree( ) 函 数
                                             开 始


tnode==NULL
    
                                                Y

	return(NULL)


	ch=strcmp(tnode->data,s)


Y                        ch==0      N
       
ch>0    N

free(tno    Y     无左孩子      N                      tnode->left=del    tnode 
-de-> 	-tree(s,tnode->left)   -right
data)	                  =deltree
         t1=tnode->      Y       无右孩子    N                        (s,tnode
          right                                                        ->right)                                                                     
                       t1=tno              t1=tnode                                   
free(tn                 -de->                ->righ
-ode)    free(tno        left
        -de->da
         -ta)	               t2=tnode
return	free                ->right
(NULL)               (tnode->
         free          data)
         (tnode)	t2->left!=NULL   N

                    free                  Y
        return      (tnode)
        (t1)	          t2=t2->left

	return
(t1)	           t2->left=
               tnode->left