二叉排序樹查找所在層次 與判斷是否為二叉排序樹

二叉排序樹

　二叉排序樹的遞回查找
　二叉排序樹的插入
　二叉排序樹的創建
　二叉排序樹的洗掉

提示：判斷是否為二叉排序樹時，根據二叉排序樹的性質，在進行中序遍歷的時候，當前結點的值總是大于前驅結點的值，
需要在遍歷時保存前驅結點的值，這樣有利于進行判斷，基于這樣的思路來進行解題，

#include <iostream>
using namespace std;
#define ENDFLAG -1
//char a[10]={'5','6','7','2','1','9','8','10','3','4','#'};//全域變數
typedef struct ElemType
{
	int key;
} ElemType;

typedef struct BSTNode
{
	ElemType data;			  //結點資料域
	BSTNode *lchild, *rchild; //左右孩子指標
} BSTNode, *BSTree;

//演算法7.4　二叉排序樹的遞回查找
BSTree SearchBST(BSTree T, int key)
{
	//在根指標T所指二叉排序樹中遞回地查找某關鍵字等于key的資料元素
	//若查找成功，則回傳指向該資料元素結點的指標，否則回傳空指標
	if ((!T) || key == T->data.key)
		return T; //查找結束
	else if (key < T->data.key)
		return SearchBST(T->lchild, key); //在左子樹中繼續查找
	else
		return SearchBST(T->rchild, key); //在右子樹中繼續查找
} // SearchBST

//非遞回實作查找成功時回傳指向該資料元素結點的指標和所在的層次
BSTree Searchlev(BSTree T, int k, int &lev)
{
	//統計查找次數

	// BSTree p = T; //p為二叉樹中作業指標
	
		lev++;
		while(T)
		{ 
			// cout<<lev;
			if(T->data.key==k) return T;
			if(k > T->data.key){
				T = T->lchild; //在左子樹查找
				lev++;
			} else{
				T = T->rchild; //在右子樹查找
				lev++;
			}
			// cout<<lev;
		}
		// cout<<"end";
	// return T;
	return NULL;

} // Searchlev
//演算法7.5　二叉排序樹的插入



// int  Level(BSTree T,int k){
// 	int height=0;
// 		k++;
// 	if(!T)
// 		return 0;
// 	while (T){

// 		if(T->data.key==k){
// 			height++;
// 			break;
// 		}
// 		else if(T->data.key>k){
// 			height++;
// 			T=T->lchild;
// 		}
// 		else{
// 			height++;
// 			T=T->rchild;
// 		}
// 	}
// 	return height;
// }

void InsertBST(BSTree &T, ElemType e)
{
	//當二叉排序樹T中不存在關鍵字等于e.key的資料元素時，則插入該元素
	if (!T)
	{								  //找到插入位置，遞回結束
		BSTree S = new BSTNode;		  //生成新結點*S
		S->data = https://www.cnblogs.com/ygjzs/p/e;				  //新結點*S的資料域置為e
		S->lchild = S->rchild = NULL; //新結點*S作為葉子結點
		T = S;						  //把新結點*S鏈接到已找到的插入位置
	}
	else if (e.key < T->data.key)
		InsertBST(T->lchild, e); //將*S插入左子樹
	else if (e.key > T->data.key)
		InsertBST(T->rchild, e); //將*S插入右子樹
} // InsertBST

//演算法7.6　二叉排序樹的創建
void CreateBST(BSTree &T)
{
	//依次讀入一個關鍵字為key的結點，將此結點插入二叉排序樹T中
	T = NULL;
	ElemType e;
	cin >> e.key; //???
	while (e.key != ENDFLAG)
	{					 //ENDFLAG為自定義常量，作為輸入結束標志
		InsertBST(T, e); //將此結點插入二叉排序樹T中
		cin >> e.key;	//???
	}					 //while
} //CreatBST

void DeleteBST(BSTree &T, int key)
{
	//從二叉排序樹T中洗掉關鍵字等于key的結點
	BSTree p = T;
	BSTree f = NULL; //初始化
	BSTree q;
	BSTree s;
	/*------------下面的while回圈從根開始查找關鍵字等于key的結點*p-------------*/
	while (p)
	{
		if (p->data.key == key)
			break; //找到關鍵字等于key的結點*p，結束回圈
		f = p;	 //*f為*p的雙親結點
		if (p->data.key > key)
			p = p->lchild; //在*p的左子樹中繼續查找
		else
			p = p->rchild; //在*p的右子樹中繼續查找
	}					   //while
	if (!p)
		return; //找不到被刪結點則回傳
	/*―考慮三種情況實作p所指子樹內部的處理：*p左右子樹均不空、無右子樹、無左子樹―*/
	if ((p->lchild) && (p->rchild))
	{ //被刪結點*p左右子樹均不空
		q = p;
		s = p->lchild;
		while (s->rchild) //在*p的左子樹中繼續查找其前驅結點，即最右下結點
		{
			q = s;
			s = s->rchild;
		}				   //向右到盡頭
		p->data = s->data; //s指向被刪結點的“前驅”
		if (q != p)
		{
			q->rchild = s->lchild; //重接*q的右子樹
		}
		else
			q->lchild = s->lchild; //重接*q的左子樹
		delete s;
	} //if
	else
	{
		if (!p->rchild)
		{ //被刪結點*p無右子樹，只需重接其左子樹
			q = p;
			p = p->lchild;
		} //else if
		else if (!p->lchild)
		{ //被刪結點*p無左子樹，只需重接其右子樹
			q = p;
			p = p->rchild;
		} //else if
		  /*――――――――――將p所指的子樹掛接到其雙親結點*f相應的位置――――――――*/
		if (!f)
			T = p; //被刪結點為根結點
		else if (q == f->lchild)
			f->lchild = p; //掛接到*f的左子樹位置
		else
			f->rchild = p; //掛接到*f的右子樹位置
		delete q;
	}
} //DeleteBST

//演算法 7.7　二叉排序樹的洗掉

//中序遍歷
void InOrderTraverse(BSTree &T)
{
	if (T)
	{
		InOrderTraverse(T->lchild);
		cout << T->data.key <<" ";
		InOrderTraverse(T->rchild);
	}
}
int predt=0;
int judgeBST(BSTree T)
{
	int b1, b2;
	if(T == NULL){
		return 1;
	}
	else{
		b1 = judgeBST(T->lchild);
		if(b1 == 0 || predt > T->data.key) return 0;
		predt = T->data.key;
		b2 = judgeBST(T->rchild);
		return b2;
	}
}

int main()
{
	BSTree T;
	int lev = 0;
	cout << "請輸入若干整數，用空格分開，以-1結束輸入" << endl;
	CreateBST(T);
	cout << "當前有序二叉樹中序遍歷結果為" << endl;
	InOrderTraverse(T);
	cout << endl;
	int key; //待查找或待洗掉內容
	cout << "請輸入待查找關鍵字（整數）" << endl;
	cin >> key;
	BSTree result = SearchBST(T, key);
	// int a=result->data.key;
	// cout<<"fghj"<< a;
	// }
	//求層數方法一
	result = Searchlev(T, key, lev);
	//方求層數法二
//    lev=Level(T,key);//沒判斷是否有這個節點，下面的result不用取非，建議用第一種

	if (!result)//這要取非
	{
		cout << "找到關鍵字" << key << "在" << lev << "層" << endl;
	}
	else
	{
		cout << "未找到" << key << endl;
	}
	//Searchpath( T, key);cout<<endl;
	cout << "請輸入待洗掉的關鍵字" << endl;
	cin >> key;
	DeleteBST(T, key);
	cout << "當前有序二叉樹中序遍歷結果為" << endl;
	InOrderTraverse(T);
	if(judgeBST(T))
	   cout<<" 是一棵排序樹"<<endl;
	else
	  cout<<" 不是一棵排序樹"<<endl;
	return 1;
}

標籤：其他

上一篇：實作有序表二分查找

下一篇：B-樹