ChenGen
          

          一切歸零，重新開始
          

          

          

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

          


          		
	
          

          

          
	
          
		
			
          
				數據加載中……
			
          
		          		
		
			
          
				
					
	
          
		
          
			復習二叉排序樹
		
          
		
          
		
		
          ???二叉排序數是一種很重要的數據結構，今天復習了一下如何創建一棵二叉排序數＆二叉排序數的兩種中序遍歷方法——遞歸中序遍歷＆非遞歸的中序遍歷。

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

          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);?/*將字符串轉化為整數*/
          ????????}
          ????????InsertNode(          &head,data);/*向樹中插入一個結點*/
          ????}
          ????          return?head;
          }

          void?InsertNode(Node?**head,int?data)
          {
          ????          if(*head==NULL){?/*如果結點為空，正是要插入的位置*/
          ????????          *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);/*插入右子樹*/
          ????}
          }

          ???二叉排序數的遞歸中序遍歷： 

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

          ???二叉排序數的非遞歸遍歷： 

          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);?/*輸出結點值*/
          ????????????p          =p->right;?/*遍歷右子樹*/?
          ????????}
          ????}
          }
          
		
          
		
          
			posted on 2006-09-27 14:33 ChenGen 閱讀(1671) 評論(2)  編輯  收藏  所屬分類: 數據結構復習 
		
          
	
          
	
	


	


          
	    
    


          

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

          





          








          

				
			
          
		          		
	
          
	
          
		
			

		
	
          

          


    







          
        
	




主站蜘蛛池模板：
荣成市|
舒城县|
雷波县|
贵南县|
宣汉县|
南皮县|
遂昌县|
通化县|
锡林浩特市|
高邑县|
新闻|
楚雄市|
大荔县|
中江县|
登封市|
江西省|
宝坻区|
托克托县|
高雄县|
晋州市|
莱州市|
伊金霍洛旗|
绥滨县|
茂名市|
泾川县|
尼勒克县|
广灵县|
宜城市|
化州市|
滁州市|
察雅县|
福安市|
灵台县|
华阴市|
舞钢市|
公主岭市|
临西县|
新宾|
县级市|
恩平市|
肇源县|