数据结构之二叉树C源代码_第1页
数据结构之二叉树C源代码_第2页
数据结构之二叉树C源代码_第3页
数据结构之二叉树C源代码_第4页
数据结构之二叉树C源代码_第5页
已阅读5页,还剩16页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

数据结构之二叉树C源代码数据结构之二叉树C源代码全文共21页,当前为第1页。玩转算法与数据结构之数据结构之二叉树C源代码全文共21页,当前为第1页。—HIT2000鲁天伟前面介绍了各种形式的链表,栈,队列,数据都是采用线性的存储结构。本文开始介绍一种新数据存储结构,树形存储结构。先从简单的二叉树开始讲解。如上面的三个二叉树图,数据的存储是按这种树型结构存放,把最左面的图倒过来看,是不是像一棵树,树从A结点处开始分叉,分成A-B,A-C两个分枝;分枝又在B结点处分叉,分成B-D,B-E两个分枝;分枝在C结点处分叉,分成C-F,C-G两个分枝。如此还可以继续在D,E,F,G上继续分下云。A称根结点,同时A是B和C的父结点。B和C是A的子结点,同时也叫分支结点。B又是D和E的父结点,D和E是B的子结点,同时由于D和E下面不再有分支,又称叶结点。一棵二叉树,只有一个根结点,下面没有分支的结点叶结点,其它的结点叫分支结点,有分支的结点最多有两个分支。树的深度指树分几层,如上面最左面这棵二叉树像一个塔形,A处于第1层;B,C处于第2层;D,E,F,G处于第3层。每一层的最多的结点数是2k-1个,K代表第几层,处于同一层的结点互为兄弟结点。一颗二叉树如果有M层深,则最多有2M-1个结点,有最多结点的叫满二叉树,例上面最左边的图。上面中间的图为普通二叉树。最右边的图是完全二叉树,树深为M层,1至M-1层每层都达到最大结点数,M层所有结点都连续集中在左侧。根据二叉树数据布局方式,我们可以用数组和链表的方式来实现。用数组方式来实现:下图为结点记录的数组存储位置图。如上最左图,数组中定位根结点的存储位置为1,找规律,父结点位置为k,则左子结点位置为2*k,右子结点的位置为2*k+1。除根结点外,每个结点,根据其父结点的存储位置来确定自己在数组中的存储位置。如此,再看上面中间和最右边的图,每个结点在数组中有固定的位置,不会因同层兄弟结点的缺失而改变。因为二叉树存在分支,那么在处理数据时,数据如何去存储放呢?树是有根才能生长,树是从根开始发芽,一节一节长出来的。假定我们用二叉树去存一组整型数据,例{8,6,3,2,11},我们按顺序取数,首先要确定根,以8为根,那么6放在哪,是作为8的左子数据,还是作为右子数据呢,这点要明确,让人或计算机处理事情,必须要定个规则,才好快速执数据结构之二叉树C源代码全文共21页,当前为第2页。行。我们定义左子结点数据要小于等于父结点数据,右子结点数据要大于父结点数据。新入数据从根结点开始,以根结点为父结点比对,比对结果确定左右分支结数据结构之二叉树C源代码全文共21页,当前为第2页。下面举一个数组实现二叉树存储的源代码实例:/*====================begin===========================*/#include<stdio.h>#include<stdlib.h>intdata[32];/*二叉树的存储数组*//*===递归插入数据======*/insert(int*data,inta,inti){if(i>31){/*递归出口1,超出数组最大边界*/printf("Thedata%dyouput,it'streeposition%disoutofthearraybounds\n",a,i);}else{if(data[i]==0){/*递归出口2,所处位置为空*/data[i]=a;/*数据写入*/}else{/*所处位置不为空*/if(a<=data[i]){/*插入数据小于等于当前位置数据*/insert(data,a,2*i);/*递归插入当前位置左子位置*/}else{/*插入数据大于当前位置数据*/insert(data,a,2*i+1);/*递归插入当前位置右子位置*/}}}}/*===递归中序打印二叉树======*/voidprintTree(int*data,inti){if(data[i]!=0&&i<32){printTree(data,2*i);/*递归打印左子数据*/printf("%d",data[i]);/*打印当前结点数据*/printTree(data,2*i+1);/*递归打印右子数据*/}}/*===建立二叉树======*/voidcreatetree(int*data,int*nodelist,intlen){inti;intlevel;数据结构之二叉树C源代码全文共21页,当前为第3页。data[1]=nodelist[1数据结构之二叉树C源代码全文共21页,当前为第3页。i=2;while(i<len){level=1;while(data[level]!=0&&level<32){if(nodelist[i]<=data[level])level=level*2;elselevel=level*2+1;}if(level<32)data[level]=nodelist[i];elseprintf("Thedata%dinnodelistposition[%d],it'snewposition%dinnewtreeisoutoftherangeoftreearraybounds\n",nodelist[i],i,level);i++;}}voidmain(){inta;inti;intnodelist[16]={0,100,90,110,80,95,105,91,106,94,109,108,120,0,0,0};printf("Thenodelistarrayis:\n");for(i=0;i<16;i++){printf("%d",nodelist[i]);}printf("\n");for(i=0;i<32;i++)data[i]=0;printf("Usecreatetreefunction\n");createtree(data,nodelist,16);printf("Thetreemiddleorderprintis:\n");printTree(data,1);printf("\n***************\n");printf("Useinsertfuntiontobuildanewtree.Ifyouwanttofinishsearchinput-1\n");for(i=0;i<32;i++)data[i]=0;do{printf("Pleaseinputdata\n");scanf("%d",&a);数据结构之二叉树C源代码全文共21页,当前为第4页。if(a==-1数据结构之二叉树C源代码全文共21页,当前为第4页。break;else{printTree(data,1);printf("\n");insert(data,a,1);printTree(data,1);printf("\n");}}while(1);getch();}/*=====================end============================*/二叉树的结构,我们亦可以用链表来实现。所使用的链表我们也可以称为二叉链表。structtree{/*定义树结点结构体*/structtree*left;/*左子结点指针(地址)变量*/intdata;/*结点数据变量*/structtree*right;/*右子结点指针(地址)变量*/};typedefstructtreetreeNode;/*二叉树结点结构体别名*/typedeftreeNode*btree;/*二叉树结点指针(地址)类型别名*/看二叉树结点结构体的定义和双向链表结点的结构体定义一样。但是由于组织方式不同,最终对外的表现形体也不同。双向链表的指针向外指向左右两个结点,同时还有左右两个结点的指针指回。而二叉树的结点指针向外指向左右两上结点,但所指向的两个结点的指针不指回。二叉树根据根结点地址,可以遍历整棵树。下面举一个二叉树链表实现二叉树存储的源代码实例:/*====================begin===========================*/#include<stdio.h>#include<stdlib.h>structtree{/*定义树结点结构体*/structtree*left;/*左子结点指针(地址)变量*/intdata;/*结点数据变量*/structtree*right;/*右子结点指针(地址)变量*/};typedefstructtreetreeNode;/*二叉树结点结构体别名*/typedeftreeNode*btree;/*二叉树结点指针(地址)类型别名*//*======递归插入法======*/btreeinsertTreeDG(btreeroot,intdata){btreenewNode=(btree)malloc(sizeof(treeNode));newNode->data=data;newNode->left=NULL;newNode->right=NULL;if(root==NULL)root=newNode;数据结构之二叉树C源代码全文共21页,当前为第5页。elseif(data<=root->data数据结构之二叉树C源代码全文共21页,当前为第5页。root->left=insertTreeDG(root->left,data);elseroot->right=insertTreeDG(root->right,data);returnroot;}/*===逐个递归插入式建树======*/btreecreateTreeDG(btreeroot,int*nodelist,intlen){inti;for(i=0;i<len;i++){root=insertTreeDG(root,nodelist[i]);}returnroot;}/*===递归中序遍历======*/voidprintInorderTree(btreeroot){if(root!=NULL){printInorderTree(root->left);printf("%d",root->data);printInorderTree(root->right);}}/*===递归前序遍历======*/voidprintPreTree(btreeroot){if(root!=NULL){printf("%d",root->data);printPreTree(root->left);printPreTree(root->right);}}/*===递归后序遍历======*/voidprintPostTree(btreeroot){if(root!=NULL){printPostTree(root->left);printPostTree(root->right);printf("%d",root->data);}}/*===打印中序数据,结点地址,结点内左子和右子地址======*/voidprintInorderaddress(btreeroot){if(root!=NULL){printInorderaddress(root->left);printf("Nodeaddress[%8d]leftaddress[%8d]data%3drightaddress[%8d]\n",root,root->left,root->data,root->right);数据结构之二叉树C源代码全文共21页,当前为第6页。printInorderaddress(root->right数据结构之二叉树C源代码全文共21页,当前为第6页。}}voidmain(){intnodelist[9]={6,4,8,2,5,7,9,1,3};btreeroot=NULL;root=createTreeDG(root,nodelist,9);printf("PreTree\n");printPreTree(root);printf("\nPostTree\n");printPostTree(root);printf("\nmiddleTree\n");printInorderTree(root);printf("\nmiddleTreeandaddress\n");printInorderaddress(root);getch();}/*=====================end============================*/一次执行结果如下:将上图的运算结果绘成二叉树图,展示所有结点里面三个数据元素的值。如下图。数据结构之二叉树C源代码全文共21页,当前为第7页。数据结构之二叉树C源代码全文共21页,当前为第7页。二叉树的链表实现源码如下:/*====================begin===========================*//*功能:二叉树的递归插入,顺序插入法,递归建树,顺序建树,*//*数组转链表存储,链表转数组存储,计算树深度,递归前中后序打印,*//*二分法递归查找结点,全遍历递归查找,递归查找父结点,删除结点,*//*递归复制二叉树,递归比较两棵二叉树,递归释放树,递归树映相*/#include<stdio.h>#include<stdlib.h>structtree{/*定义二叉树结点结构体*/structtree*left;/*定义左子结点指针(地址)变量*/intdata;/*定义结点数据变量*/structtree*right;/*定义右子结点指针(地址)变量*/};typedefstructtreetreeNode;/*二叉树结点结构体别名*/typedeftreeNode*btree;/*二叉树结点指针(地址)类型别名*//*======递归插入法======*/btreeinsertTreeDG(btreeroot,intdata){btreenewNode=(btree)malloc(sizeof(treeNode));newNode->data=data;newNode->left=NULL;newNode->right=NULL;if(root==NULL)root=newNode;elseif(data<=root->data)root->left=insertTreeDG(root->left,data);elseroot->right=insertTreeDG(root->right,data);returnroot;}/*===顺序插入法======*/btreeinsertTree(btreeroot,intdata){btreenewNode=(btree)malloc(sizeof(treeNode));btreep;btreeparent;newNode->data=data;newNode->left=NULL;newNode->right=NULL;数据结构之二叉树C源代码全文共21页,当前为第8页。if(root==NULL数据结构之二叉树C源代码全文共21页,当前为第8页。root=newNode;else{p=root;while(p!=NULL){parent=p;if(data<=p->data){p=p->left;}else{p=p->right;}}if(data<=parent->data)parent->left=newNode;elseparent->right=newNode;}returnroot;}/*===逐个顺序插入式建树======*/btreecreateTree(btreeroot,int*nodelist,intlen){inti;for(i=0;i<len;i++){root=insertTree(root,nodelist[i]);}returnroot;}/*===逐个递归插入式建树======*/btreecreateTreeDG(btreeroot,int*nodelist,intlen){inti;for(i=0;i<len;i++){root=insertTreeDG(root,nodelist[i]);}returnroot;}/*===树的数组形式存储转为链表形式存储======*/btreecreateTreeArrayToList(btreeroot,int*nodelist,intlen,intindex){if(nodelist[index]!=0&&index<len){root=(btree)malloc(sizeof(treeNode));数据结构之二叉树C源代码全文共21页,当前为第9页。root->data=nodelist[index数据结构之二叉树C源代码全文共21页,当前为第9页。root->left=createTreeArrayToList(root->left,nodelist,len,2*index);root->right=createTreeArrayToList(root->right,nodelist,len,2*index+1);returnroot;}elsereturnNULL;}/*===树的链表形式存储转为数组形式存储======*/voidcreateTreeListToArray(btreeroot,int*nodelist,intlevel){if(root!=NULL){nodelist[level]=root->data;createTreeListToArray(root->left,nodelist,2*level);createTreeListToArray(root->right,nodelist,2*level+1);}}/*===递归计算树的深度======*/voiddeepTree(btreeroot,inti,int*maxaddr){if(root!=NULL){i++;if(*maxaddr<i){*maxaddr=i;}deepTree(root->left,i,maxaddr);deepTree(root->right,i,maxaddr);}}/*===递归中序遍历======*/voidprintInorderTree(btreeroot){if(root!=NULL){printInorderTree(root->left);printf("%d",root->data);printInorderTree(root->right);}}/*===递归前序遍历======*/voidprintPreTree(btreeroot){if(root!=NULL){printf("%d",root->data);数据结构之二叉树C源代码全文共21页,当前为第10页。printPreTree(root->left数据结构之二叉树C源代码全文共21页,当前为第10页。printPreTree(root->right);}}/*===递归后序遍历======*/voidprintPostTree(btreeroot){if(root!=NULL){printPostTree(root->left);printPostTree(root->right);printf("%d",root->data);}}/*===打印中序数据的地址======*/voidprintInorderaddress(btreeroot){if(root!=NULL){printInorderaddress(root->left);printf("[%d]->%d",root,root->data);printInorderaddress(root->right);}}/*===全遍历递归查找======*/btreesearch(btreeroot,intdata){btreep=NULL;if(root!=NULL){if(root->data==data)returnroot;else{p=search(root->left,data);if(p==NULL)p=search(root->right,data);returnp;}}elsereturnNULL;}/*===二分法递归查找======*/btreebinarySearch(btreeroot,intdata){btreep;数据结构之二叉树C源代码全文共21页,当前为第11页。if(root!=NULL数据结构之二叉树C源代码全文共21页,当前为第11页。if(root->data==data)p=root;elseif(data<=root->data)p=binarySearch(root->left,data);elsep=binarySearch(root->right,data);returnp;}elsereturnNULL;}/*===递归查找父结点======*/voidsearchParent(btreeroot,btreechild,btree*parentadd,int*situationadd){if(root!=NULL){if(root==child){*parentadd=NULL;*situationadd=0;}else{if(root->left==child){*situationadd=1;*parentadd=root;}elseif(root->right==child){*situationadd=2;*parentadd=root;}else{searchParent(root->left,child,parentadd,situationadd);if(*situationadd==-1)searchParent(root->right,child,parentadd,situationadd);}}}}/*===删除结点方法======*/btreedeleteNode(btreeroot,intdata){btreep,q,m,k;btreeparent=NULL;数据结构之二叉树C源代码全文共21页,当前为第12页。btreechild数据结构之二叉树C源代码全文共21页,当前为第12页。intsituation=-1;if(root==NULL){printf("Thetreeisempty\n");}p=search(root,data);if(p==NULL){printf("%disnotinthetree\n",data);}else{searchParent(root,p,&parent,&situation);if(p->left==NULL&&p->right==NULL){/*无左子无右子*/switch(situation){case0:free(root);root=NULL;break;case1:parent->left=NULL;free(p);break;case2:parent->right=NULL;free(p);break;}}elseif(p->left!=NULL&&p->right==NULL){/*有左子无右子*/switch(situation){case0:q=root;root=root->left;free(q);break;case1:parent->left=p->left;free(p);break;case2:parent->right=p->left;free(p);break;}数据结构之二叉树C源代码全文共21页,当前为第13页。数据结构之二叉树C源代码全文共21页,当前为第13页。elseif(p->left==NULL&&p->right!=NULL){/*有右子无左子*/switch(situation){case0:q=root;root=root->right;free(q);break;case1:parent->left=p->right;free(p);break;case2:parent->right=p->right;free(p);break;}}else{q=p->left;while(q->right!=NULL){/*有左子有右子*/k=q;q=q->right;}p->data=q->data;if(q==p->left){p->left=q->left;}else{k->right=q->left;}free(q);}}returnroot;}/*===递归复制二叉树======*/btreecopy(btreeroot){btreenewNode;if(root!=NULL){newNode=(btree)malloc(sizeof(treeNode));newNode->data=root->data;newNode->left=copy(root->left);数据结构之二叉树C源代码全文共21页,当前为第14页。newNode->right=copy(root->right数据结构之二叉树C源代码全文共21页,当前为第14页。returnnewNode;}elsereturnNULL;}/*===递归比较两棵二叉树======*/intcompare(btreeroot1,btreeroot2){intp=1;if(root1==NULL&&root2==NULL)return1;elseif(root1!=NULL&&root2!=NULL){if(root1->data!=root2->data)return0;else{p=compare(root1->left,root2->left);if(p==1)p=compare(root1->right,root2->right);returnp;}}else{return0;}}/*===递归释放树======*/voidfreeTree(btreeroot){if(root!=NULL){freeTree(root->left);freeTree(root->right);free(root);}}/*===递归树的映相======*/btreeswap(btreeroot){btreenewNode;if(root!=NULL){newNode=(btree)malloc(sizeof(treeNode));newNode->data=root->data;newNode->left=swap(root->right);newNode->right=swap(root->left);数据结构之二叉树C源代码全文共21页,当前为第15页。returnnewNode数据结构之二叉树C源代码全文共21页,当前为第15页。}elsereturnNULL;}voidmain(){intnodelist[20];intindex=0;inta;inti;intb;intselect;intc;intq;intnodelist1[16]={0,5,2,9,1,4,7,0,0,0,3,0,6,8,0,0};/*用来建二叉树的数组*/btreeroot1=NULL;btreeroot2=NULL;btreeroot3=NULL;btreeroot4=NULL;btreeroot5=NULL;btreep=NULL;btreetDdeleteHead;intmax=0;printf("TreeArraycoverttoList,printTree1\n");root1=createTreeArrayToList(root1,nodelist1,16,1);/*二叉树的数组形式存储转为链表形式存储*/printInorderTree(root1);/*二叉树中序打印*/printf("\n");deepTree(root1,0,&max);/*树的深度计算*/printf("TheTree1deepis%d\n",max);printf("TreeListofTree1coverttoarry\n");for(i=0;i<16;i++){nodelist1[i]=0;}createTreeListToArray(root1,nodelist1,1);/*树的链表形式存储转为数组形式存储*/for(i=0;i<16;i++){printf("%d",nodelist1[i]);}printf("\n");do{数据结构之二叉树C源代码全文共21页,当前为第16页。printf("Treemanagement:\n1.search\n2.insert\n3.delete\n4.copy\n5.buildtree\paretree1andtree2\n7.swap\n8.quit\n"数据结构之二叉树C源代码全文共21页,当前为第16页。scanf("%d",&select);if(select==8)break;switch(select){case1:printInorderaddress(root1);printf("\n");printf("Inputthedatayouwanttofind.Ifyouwanttofinishsearchinput-1\n");do{p=NULL;scanf("%d",&a);if(a==-1)break;p=search(root1,a);if(p==NULL)printf("Notfound\n");elseprintf("Found%disinaddress%d\n",a,p);}while(1);break;case2:do{printInorderTree(root1);printf("\n");printf("InsertnewtreeNodedatatoTree1.Ifyouwanttofinishinsertinput-1\n");scanf("%d",&c);if(c==-1)break;root1=insertTreeDG(root1,c);printInorderTree(root1);printf("\n");}while(1);break;case3:do{printInorderTree(root1);printf("\n");数据结构之二叉树C源代码全文共21页,当前为第17页。printf("Inputthedatayouwanttodelete.Ifyouwanttofinishdeleteinput-1\n"数据结构之二叉树C源代码全文共21页,当前为第17页。scanf("%d",&b);if(b==-1)break;else{root1=deleteNode(root1,b);printInorderTree(root1);printf("\n");}}while(1);break;case4:root2=copy(root1);printf("*****copyTree1*******printTree2*************\n");printInorderTree(root2);printf("\n");break;case5:printf("InputdatatocreateanewTree3.Ifyouwanttofinishinsertinput-1\n");index=0;do{scanf("%d",&a);if(a==-1)break;elsenodelist[index++]=a;}while(index<20);root3=createTree(root3,nodelist,index);printf("PreTreeprint\n");printPreTree(root3);printf("\n");printf("MiddleTreeprint\n");printInorderTree(root3);printf("\n");printf("PostTreeprint\n");printPostTree(root3);printf("\n");freeTree(root3);root3=NULL;break;数据结构之二叉树C源代码全文共21页,当前为第18页。case6数据结构之二叉树C源代码全文共21页,当前为第18页。index=0;printf("InputdatatocreateanewTree4.Input-1tofinish.Inputnumberoftreenodelittlethan20\n");do{scanf("%d",&a);if(a==-1)break;elsenodelist[index++]=a;}while(index<20);root4=createTree(root4,nodelist,index);printf("Tree1areasfollows:\n");printInorderTree(root1);printf("\n");printf("Tree4newbuiltareasfollows:\n");printInorderTree(root4);printf("\n");q=compare(root1,root4);if(q==1)printf("Theyarethesame\n");elseprintf("Theyarenotsame\n");freeTree(root4);root4=NULL;break;case7:printf("Swapatreefromlefttorightandrighttoleftlikeamirror\n");root5=swap(root1);printf("PrintTree1\n");printInorderTree(root1);printf("\n");printf("PrintTree5whichswapTree1\n");printInorderTree(root5);printf("\n");freeTree(root5);root5=NULL;break;}}while(1);getch();}数据结构之二叉树C源代码全文共21页,当前为第19页。/*=====================end============================*数据结构之二叉树C源代码全文共21页,当前为第19页。上面的代码大量使用了一个算法叫递归算法。在数据结构这门课里,递归是要掌握的一个非常好的算法,递归就是多次嵌套循环,重要的是找到出口。利用指令栈来理解递归算法就会非常理想。在这里再写一个二叉树的结构体数组实现。是一种模仿动态链表的实现。只是这种实现方式导致树的大小受到数组大小的限制,对于指定结点个数的二叉树可以使用。相当于把链表结点压在了一起。用数组的标置位来寻址,就不用指针(地址)来找结点了。实现如下:/*====================begin===========================*//*程序名称:treestructArray.c*//*功能:二叉树,用结构体数组实现顺序打印,中序遍历打印功能*//*author:HIT2000软件学院鲁天伟微信同电话/#include<stdio.h>#include<stdlib.h>structtree{/*定义二叉树结点结构体*/intleft;/*定义左子在数组中的位置*/intdata;/*定义结点数据变量*/intright;/*

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论