ChenGen
          

          一切歸零，重新開始
          

          

          

          隨筆 - 13, 文章 - 10, 評論 - 21, 引用 - 0
          

          


          		
	
          

          

          
	
          
		
			
          
				數(shù)據(jù)加載中……
			
          
		          		
		
			
          
				
					
	
          
		
          
			復習二叉排序樹
		
          
		
          
		
		
          ???二叉排序數(shù)是一種很重要的數(shù)據(jù)結(jié)構(gòu)，今天復習了一下如何創(chuàng)建一棵二叉排序數(shù)＆二叉排序數(shù)的兩種中序遍歷方法——遞歸中序遍歷＆非遞歸的中序遍歷。

          ???宏定義＆頭文件：
          
		
          
				
				#include?
				"
				stdio.h
				"
				
						
          
						#include?          
				"
				stdlib.h
				"
				?
				/*
				內(nèi)存分配*/
				
						
          
						
				          
				#include?
				"
				ctype.h
				"
				?
				/*
				字符操作*/
				
						
          
						
				          
				#define?MAXNUM?
				100
				?
				/*
				非遞歸時的棧的大小*/
		
          
		
          
				
          ???數(shù)據(jù)結(jié)構(gòu)：
          
		
          
				
				
				typedef?struct?node
				
				
						{
          ????          
						int
						?data;
          ????struct?node?          
						*
						left;
          ????struct?node?          
						*
						right;
          }          
				          
				?Node;
		
          
		
          ???生成一棵二叉排序數(shù)：??? 

          Node?*CreateTree()
          {
          ????          int?p,data;
          ????          char?buffer[100],ch;
          ????Node?          *head;
          ????head          =NULL;????/*This?is?very?important!*/
          ????          while((ch=getchar())!=EOF){
          ????????p          =0;
          ????????          if(isspace(ch))?/*過濾空格*/
          ????????????          continue;
          ????????          else?if(isdigit(ch)){
          ????????????buffer[p          ++]=ch;
          ????????????          for(ch=getchar();isdigit(ch);ch=getchar())
          ????????????????buffer[p          ++]=ch;
          ????????????ungetc(ch,stdin);
          ????????????buffer[p]          ='\0';
          ????????????data          =atoi(buffer);?/*將字符串轉(zhuǎn)化為整數(shù)*/
          ????????}
          ????????InsertNode(          &head,data);/*向樹中插入一個結(jié)點*/
          ????}
          ????          return?head;
          }

          void?InsertNode(Node?**head,int?data)
          {
          ????          if(*head==NULL){?/*如果結(jié)點為空，正是要插入的位置*/
          ????????          *head=(Node?*)malloc(sizeof(Node));
          ????????(          *head)->data=data;
          ????????(          *head)->left=NULL;
          ????????(          *head)->right=NULL;
          ????}
          ????          else{
          ????????          if(data<(*head)->data)?InsertNode(&((*head)->left),data);/*插入左子樹*/
          ????????          else?InsertNode(&((*head)->right),data);/*插入右子樹*/
          ????}
          }

          ???二叉排序數(shù)的遞歸中序遍歷： 

          void?MidTravel(Node?*head)
          {
          ????          if(head){
          ????????MidTravel(head          ->left);?/*遍歷左子樹*/
          ????????printf(          "%d\t",head->data);?/*輸出結(jié)點值*/
          ????????MidTravel(head          ->right);?/*遍歷又子樹*/
          ????}
          }

          ???二叉排序數(shù)的非遞歸遍歷： 

          void?MidTravel2(Node?*p)
          {
          ????Node?          *a[MAXNUM];?/*棧*/
          ????          int?top;?/*棧頂*/
          ????top          =0;
          ????          while(p?||?top){
          ????????          while(p){
          ????????????          if(top==MAXNUM)?{
          ????????????????printf(          "over?flow\n");
          ????????????????exit(          -1);
          ????????????}
          ????????????a[top          ++]=p;?/*入棧*/
          ????????????p          =p->left;?/*遍歷左子樹*/
          ????????}
          ????????          if(top){
          ????????????p          =a[--top];?/*出棧*/
          ????????????printf(          "%d\t",p->data);?/*輸出結(jié)點值*/
          ????????????p          =p->right;?/*遍歷右子樹*/?
          ????????}
          ????}
          }
          
		
          
		
          
			posted on 2006-09-27 14:33 ChenGen 閱讀(1680) 評論(2)  編輯  收藏  所屬分類: 數(shù)據(jù)結(jié)構(gòu)復習 
		
          
	
          
	
	


	


          
	    
    


          

          評論
          
	
	
			
          
				
          
					# re: 復習二叉排序樹  回復  更多評論
					  
				
          
				又有沙發(fā)座了
				
          
					2006-09-27 11:05 | 壞男孩1
				
          
			
          
		
			
          
				
          
					# re: 復習二叉排序樹  回復  更多評論
					  
				
          
				呵呵，支持下！
				
          
					2006-09-28 08:37 | 冰川
				
          
			
          
		

          





          








          

				
			
          
		          		
	
          
	
          
		
			

		
	
          

          


    







          
        
	




主站蜘蛛池模板：
民权县|
乌海市|
博湖县|
太保市|
金堂县|
泗洪县|
姚安县|
临夏市|
县级市|
伊宁市|
武平县|
安福县|
安义县|
桑植县|
湘潭市|
汉寿县|
夏邑县|
苏州市|
大庆市|
福海县|
黔江区|
敦化市|
响水县|
拉孜县|
垦利县|
额尔古纳市|
慈利县|
饶河县|
钟山县|
松阳县|
江门市|
涞水县|
慈利县|
昂仁县|
伊春市|
玉环县|
长汀县|
凌源市|
泰和县|
永新县|
衡南县|