1. 如何使用非遞歸算法構(gòu)建二進(jìn)制排序樹？

2. 我們都知道二進(jìn)制排序樹是二進(jìn)制樹建立二叉排序樹，而二進(jìn)制樹實(shí)際上是帶有雙指針的鏈表，那么如何插入鏈表？我們來(lái)看一下在鏈表中插入值的算法:

#include <stdio.h>
#define null NULL
typedef struct Node{
	struct Node *next;//下一指針
	int data;//數(shù)據(jù)域 
}Node ;
//將數(shù)據(jù)插入到單鏈表中 
void insertData(Node *&L,int data){
	Node *r;//新建一個(gè)指針 
	Node *q ;
	r = L;//賦值 
	while(r->next!=null){
		if(r->next->data > data ){//找到第一個(gè)大于值的節(jié)點(diǎn) 			
			q = new Node;//指向一個(gè)新的結(jié)點(diǎn)
			q->data = data;
			r->next = q;
			q->next = r->next->next; 
		}
		else	r = r->next	;
	} 
	if(r->next == null){
		q = new Node;//指向一個(gè)新的結(jié)點(diǎn)
		q->data = data;
		r->next = q;
		q->next = null; 
	}	
}
//遍歷單鏈表
void traverseLinkList(Node *L){	
	L = L->next;
	while(L!=null){
		printf("%d ",L->data);
		L = L->next;
	}
} 
int main(){
	Node *L;//單鏈表的表頭
	L = new Node;//這一步，非常重要！指向一個(gè)具體結(jié)點(diǎn)！
	L->next = null; 
	int number;
	printf("請(qǐng)輸入插入的數(shù)據(jù)個(gè)數(shù)！\n");	
	scanf("%d",&number);
	int data;
	for(int i = 0;i<number;i++){
		scanf("%d",&data);//輸入數(shù)據(jù)
		insertData(L,data);//往單鏈表中插入數(shù)據(jù) 
	}
	//遍歷輸出 
	traverseLinkList(L);
} 
/*
4
1 2 3 4
*/
 

3. 讓我們看一下此插入值的insertData函數(shù)

void insertData(Node *&L,int data){
	Node *r;//新建一個(gè)指針 
	Node *q ;
	r = L;//賦值 
	while(r->next!=null){
		if(r->next->data > data ){//找到第一個(gè)大于值的節(jié)點(diǎn) 			
			q = new Node;//指向一個(gè)新的結(jié)點(diǎn)
			q->data = data;
			r->next = q;
			q->next = r->next->next; 
		}
		else	r = r->next	;
	} 
	if(r->next == null){
		q = new Node;//指向一個(gè)新的結(jié)點(diǎn)
		q->data = data;
		r->next = q;
		q->next = null; 
	}	
}

（1）我們需要?jiǎng)?chuàng)建一個(gè)新的Node * r和Node * q； r是為了防止直接使用L導(dǎo)致L成為指向最后一個(gè)節(jié)點(diǎn)的指針（因此導(dǎo)致無(wú)法直接輸出）. 因此，您需要使用指針r臨時(shí)存儲(chǔ)L的值

（2）此處的指針q是什么？這是準(zhǔn)備一個(gè)新的插入節(jié)點(diǎn)，因?yàn)槲覀冃枰獙⒉迦氲闹捣湃朐摴?jié)點(diǎn)，因此q指向此插入的節(jié)點(diǎn).

（3）插入過(guò)程是什么？它基于判斷while（r-> next！= null），因?yàn)槲覀冃枰�判斷�?dāng)前節(jié)點(diǎn)，并在當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)的末尾插入建立二叉排序樹，這就是跟隨指針！

但是這里我不使用以下指針，而是遵循指針的想法，每個(gè)人都必須擁有它！因?yàn)檫@在構(gòu)建二叉樹的過(guò)程中至關(guān)重要.

4. 現(xiàn)在回到主題，讓我們看一下該二進(jìn)制排序樹的非遞歸方法的實(shí)現(xiàn)功能

void insertBiTree_2(BiTree *&bt,int da){	
	//先判斷樹是否為空-->如果為空，則建樹，直接返回 
	if(bt==null){	
		bt = new BiTree;//因?yàn)樵趍ain函數(shù)中，bt是null，所以需要先讓其指向一個(gè)節(jié)點(diǎn)，才能在該節(jié)點(diǎn)上賦值操作！ 
		bt->data = da;
		bt->lChild = null;
		bt->rChild = null;
		return ;
	} 	
	BiTree *pre;//探索指針
	pre = bt;
	
	BiTree *follow;//跟隨指針
	follow = bt;
			
	int flag = -1; 
	while(pre!=NULL){	
		if(pre->data <= da ) {//需要循環(huán)測(cè)試是否為null
			follow = pre;//暫存值 
			pre = pre->rChild; //變化的是follow!!
			flag = 1;
		}
		else if( pre != null && pre->data > da ){//需要循環(huán)測(cè)試是否為null 
			follow = pre;//暫存值 
			pre = pre->lChild;//變化的是follow!!
			flag = -1;
		}		
	}
	//注意！！如果說(shuō)是跟隨指針發(fā)現(xiàn)孩子為null,則添加節(jié)點(diǎn)，且將當(dāng)前指針（pre）的孩子設(shè)成temp 
	if(pre == null){
		//下面是新建一個(gè)BiTree節(jié)點(diǎn)，并將其修改成標(biāo)志的二叉樹節(jié)點(diǎn)（左右子樹均賦為空） 
		BiTree *temp;	
		temp = new BiTree; 
		temp->data = da;//插入數(shù)據(jù)
		temp->lChild = null;
		temp->rChild = null;
		
		if(flag == 1){
			follow->rChild = temp;	
			flag = -1; 
		}
		else if(flag == -1){
			follow->lChild = temp;
			flag = -1;
		}
	}	
} 

（1）Pre是探查指針，探查指針是什么，意味著判斷當(dāng)前值的大小和插入值的大小，而跟隨指針則保留當(dāng)前的pre，因?yàn)閜re在進(jìn)行大小比較之后，需要將其更改為指向左或右子樹的指針. 但是，當(dāng)我們插入值時(shí)，我們將按照以下步驟進(jìn)行操作. [跟隨者被命名為跟隨指針]

（2）以下是典型的錯(cuò)誤代碼. 當(dāng)然，此代碼也是由作者本人編寫的. . .

//插入數(shù)據(jù)-->建立一棵二叉樹
//如果你硬要使用這種方式來(lái)創(chuàng)建一棵二叉樹，那么你需要一個(gè)頭結(jié)點(diǎn) 
void insertBiTree_2(BiTree *&temp,int da){	
	//BiTree *temp;
	//temp = bt;
		
	//先找到合適的位置--->如果說(shuō)temp不為null 
	//這里是一個(gè)while(temp!=null)循環(huán)的原因：可能是在左子樹，也可能是右子樹 
	while(temp!=NULL){	
		if(temp->data < da ) {//需要循環(huán)測(cè)試是否為null
			temp = temp->rChild;
		}
		else if( temp != null && temp->data > da ){//需要循環(huán)測(cè)試是否為null 
			temp = temp->lChild;
		}		
	}
	if(temp == null){
		temp = new BiTree; 
		temp->data = da;//插入數(shù)據(jù)
		temp->lChild = null;
		temp->rChild = null;	
	}	
} 

這里有很多錯(cuò)誤:

（1）直接修改溫度是否正確？不需要進(jìn)行臨時(shí)的價(jià)值保護(hù)嗎？ --->您需要申請(qǐng)一個(gè)指向bt的指針，而不是直接使用它

（2）在while（）循環(huán)中，如果添加了右子樹的葉節(jié)點(diǎn)，則if（temp-> data> da）在這里將是錯(cuò)誤的！ [因?yàn)閠emp-> data不存在，即temp == null]

（3）當(dāng)然，最關(guān)鍵的錯(cuò)誤是我們沒(méi)有使用以下指針，導(dǎo)致每次結(jié)果為temp == null時(shí)，就不可能建立完整的數(shù)字，從而導(dǎo)致失敗輸出.

6. 該程序的源代碼如下所示

本文來(lái)自本站，轉(zhuǎn)載請(qǐng)注明本文網(wǎng)址：
http://www.pc-fly.com/a/jisuanjixue/article-250949-1.html