如何使用非递归算法实现二叉排序树的建立

1.如何使用非递归算法实现二叉排序树的建立?

2.我们都知道二叉排序树就是二叉树，而二叉树其实就是带有双指针的链表，那么链表是怎么做插入的？下面我们来看一段链表插入值算法：

#include <stdio.h>
#define null NULL
typedef struct Node{
	struct Node *next;//下一指针
	int data;//数据域 
}Node ;

//将数据插入到单链表中 
void insertData(Node *&L,int data){
	Node *r;//新建一个指针 
	Node *q ;
	r = L;//赋值 
	while(r->next!=null){
		if(r->next->data > data ){//找到第一个大于值的节点 			
			q = new Node;//指向一个新的结点
			q->data = data;
			r->next = q;
			q->next = r->next->next; 
		}
		else	r = r->next	;
	} 
	if(r->next == null){
		q = new Node;//指向一个新的结点
		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;//这一步，非常重要！指向一个具体结点！
	L->next = null; 
	int number;
	printf("请输入插入的数据个数！\n");	
	scanf("%d",&number);
	int data;
	for(int i = 0;i<number;i++){
		scanf("%d",&data);//输入数据
		insertData(L,data);//往单链表中插入数据 
	}
	//遍历输出 
	traverseLinkList(L);
} 
/*
4
1 2 3 4
*/
 

3.我们来看一下这个插入值的insertData函数

void insertData(Node *&L,int data){
	Node *r;//新建一个指针 
	Node *q ;
	r = L;//赋值 
	while(r->next!=null){
		if(r->next->data > data ){//找到第一个大于值的节点 			
			q = new Node;//指向一个新的结点
			q->data = data;
			r->next = q;
			q->next = r->next->next; 
		}
		else	r = r->next	;
	} 
	if(r->next == null){
		q = new Node;//指向一个新的结点
		q->data = data;
		r->next = q;
		q->next = null; 
	}	
}

（1）我们需要新建一个Node* r,与Node* q；r是为了防止直接使用L导致L成为了指向最后的节点的指针（从而导致不能直接输出了）。故需要使用一个指针r来暂存L的值

（2）这里的指针q是干嘛的呢？是新建插入结点做准备，因为我们需要对插入的值放到节点中，这个q就是指向这个插入的结点。

（3）插入过程是怎么样的？是在判断while（r->next!=null）的基础上，因为我们需要的是对当前的结点判断，而对当前节点的上一结点末尾插入，这就是跟随指针！
但是这里我并没有使用跟随指针，但是跟随指针的思想，大家得有！因为这个在后面二叉树的建树过程中则是至关重要的。

4.现在回到主题，我们来看看这个二叉排序树非递归手法的实现函数

void insertBiTree_2(BiTree *&bt,int da){	
	//先判断树是否为空-->如果为空，则建树，直接返回 
	if(bt==null){	
		bt = new BiTree;//因为在main函数中，bt是null，所以需要先让其指向一个节点，才能在该节点上赋值操作！ 
		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 ) {//需要循环测试是否为null
			follow = pre;//暂存值 
			pre = pre->rChild; //变化的是follow!!
			flag = 1;
		}
		else if( pre != null && pre->data > da ){//需要循环测试是否为null 
			follow = pre;//暂存值 
			pre = pre->lChild;//变化的是follow!!
			flag = -1;
		}		
	}
	//注意！！如果说是跟随指针发现孩子为null,则添加节点，且将当前指针（pre）的孩子设成temp 
	if(pre == null){
		//下面是新建一个BiTree节点，并将其修改成标志的二叉树节点（左右子树均赋为空） 
		BiTree *temp;	
		temp = new BiTree; 
		temp->data = da;//插入数据
		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就是探索指针，什么是探索指针，意思就是判断当前值的大小与插入值大小的判断，而follow指针就是保留当前这个pre，因为pre在做出大小比较之后，需要将其改变成指向左子树或者是右子树的指针。但是我们在插入值的时候，是对follow操作的。【follow名为跟随指针】

（2）下面给出一段典型的错误代码，当然这个代码也是由作者本人写出来的。。。。

//插入数据-->建立一棵二叉树
//如果你硬要使用这种方式来创建一棵二叉树，那么你需要一个头结点 
void insertBiTree_2(BiTree *&temp,int da){	
	//BiTree *temp;
	//temp = bt;
		
	//先找到合适的位置--->如果说temp不为null 
	//这里是一个while(temp!=null)循环的原因：可能是在左子树，也可能是右子树 
	while(temp!=NULL){	
		if(temp->data < da ) {//需要循环测试是否为null
			temp = temp->rChild;
		}
		else if( temp != null && temp->data > da ){//需要循环测试是否为null 
			temp = temp->lChild;
		}		
	}
	if(temp == null){
		temp = new BiTree; 
		temp->data = da;//插入数据
		temp->lChild = null;
		temp->rChild = null;	
	}	
} 

这里的错误有很多：

（1）难道是真的直接对temp做修改？而不需要做一个暂存值的保护？--->需要另行申请一个指针，指向bt，而不是直接使用

（2）在while()循环里面，如果添加的是右子树的叶子结点，那么这里的if(temp->data > da)将会出现错误！【因为这里的temp->data不存在，即temp==null】

（3）当然，最关键的错误在于，我们没有使用跟随指针，导致每次出现的结果都是temp  == null，然后无法建立一棵完整的数，从而导致无法输出。

6.下面给出该程序的源代码

#include <stdio.h>
#define null NULL
typedef struct BiTree{
	struct BiTree *lChild,*rChild;//左右子指针
	int data;//数据域 
}BiTree;

//先序遍历二叉树
void preOrderBiTree(BiTree *T){
	if(T!=null){
		printf("%d ",T->data);	
	}
	else	return ;//否则终止递归--->递归结束边界 
	preOrderBiTree(T->lChild);//递归左子树 
	preOrderBiTree(T->rChild);//递归右子树 
}

void insertBiTree_2(BiTree *&bt,int da){	
	//先判断树是否为空-->如果为空，则建树，直接返回 
	if(bt==null){	
		bt = new BiTree;//因为在main函数中，bt是null，所以需要先让其指向一个节点，才能在该节点上赋值操作！ 
		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 ) {//需要循环测试是否为null
			follow = pre;//暂存值 
			pre = pre->rChild; //变化的是follow!!
			flag = 1;
		}
		else if( pre != null && pre->data > da ){//需要循环测试是否为null 
			follow = pre;//暂存值 
			pre = pre->lChild;//变化的是follow!!
			flag = -1;
		}		
	}
	//注意！！如果说是跟随指针发现孩子为null,则添加节点，且将当前指针（pre）的孩子设成temp 
	if(pre == null){
		//下面是新建一个BiTree节点，并将其修改成标志的二叉树节点（左右子树均赋为空） 
		BiTree *temp;	
		temp = new BiTree; 
		temp->data = da;//插入数据
		temp->lChild = null;
		temp->rChild = null;
		
		if(flag == 1){
			follow->rChild = temp;	
			flag = -1; 
		}
		else if(flag == -1){
			follow->lChild = temp;
			flag = -1;
		}
	}	
} 

int main(){ 
	BiTree *bt;//新建一个BiTree型头指针 
	bt = null;//初始化为null 
	
	int number;//表示节点数
	scanf("%d",&number);//输入number
	int i;
	int da;
	for(i = 0;i< number;i++){
		scanf("%d",&da);		
		insertBiTree_2(bt,da);//从bt的左子树中插入值到树中 
	} 	
	//遍历输出二叉树 
	preOrderBiTree(bt);
}
/**
7
8 6 5 7 10 8 11
*/