如何使用非递归算法完成二进制排序树的创建

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是探查指针，探查指针是什么，意味着判断当前值的大小和插入值的大小，而跟随指针则保留当前的pre，因为pre在进行大小比较之后，需要将其更改为指向左或右子树的指针. 但是，当我们插入值时，我们将按照以下步骤进行操作. [跟随者被命名为跟随指针]

（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）直接修改温度是否正确？不需要进行临时的价值保护吗？ --->您需要申请一个指向bt的指针，而不是直接使用它

（2）在while（）循环中，如果添加了右子树的叶节点，则if（temp-> data> da）在这里将是错误的！ [因为temp-> data不存在，即temp == null]

（3）当然，最关键的错误是我们没有使用以下指针，导致每次结果为temp == null时，就不可能建立完整的数字，从而导致失败输出.

6. 该程序的源代码如下所示

本文来自本站，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-250949-1.html