数据结构之（六）之二叉排序树

二叉排序树定义：
①它的左子树非空，那么左子树的值要小于根节点的值。
②它的右子树非空，那么右子树的值要小于根节点的值。
③它的左右子树也为二叉排序数。
二叉排序数的初始化，创建较简单，直接贴上源代码。这篇博客主要探讨的是二叉排序树的删除操作。

#include<stdio.h>
#include<iostream>
#include<stdlib.h>
using namespace std;
int v=0;
typedef struct Node
{
	
	Node *left;
	Node *right;
	int key;
}BiNode,*BiTree;



void InserBT(BiTree &bst,int key)
 { BiTree s;
 	if(bst==NULL)
    {
       s=new BiNode;
       s->key=key;
       s->left=NULL;
       s->right=NULL;
       bst=s;
       
		 }
    else if(key>bst->key) 
	{
		InserBT(bst->right,key);
		
		}	
		else if(key<bst->key)
		{
			InserBT(bst->left,key);
		}
 	
 }
 void CreatBT(BiTree &bst)
{   
   
   int key;
  bst=NULL;
  scanf("%d",&key);
while(key!=0)
{  
       InserBT(bst,key);
       scanf("%d",&key);
}
   
}
void travel(BiTree bst)
{    
if(bst!=NULL)
  {  
	travel(bst->left);
	cout<<bst->key;
	printf("\n");
	travel(bst->right); 
	
  }
}
void Search(BiTree bst,int key)
{   
v++;
if(bst!=NULL)
   {
     if(bst->key==key) printf("经过%d次找到了",v);
     if(bst->key<key) 
	 {
	  Search(bst->right,key);
	  
     }
	 if(bst->key>key) {
	 Search(bst->left,key);  

   }
}
}

二叉排序数的删除：
删除操作查找要删除的结点，如果不在二叉排序树中，不做任何操作。若在二叉排序树中，设此节点为p，它的父节点为f，并假设p为f的左孩子。
①若p为叶子结点，直接删除。
②若p只有左子树或右子树，把p的左子树或右子树链在p的左子树上，删除p。
③若p又有左子树和右子树，找p的前驱节点s，把s的值赋给p节点，找到s的父节点p，若s有左子树，把s的左子树链在结点p的右子树上，删除结点s。
中序二叉树的前驱怎么找？
数据结构之（六）之二叉排序树
①若该节点有左子树，找到左子树中最右的结点就是该节点的前驱。如结点5的前驱是4
②若该节点无左子树分两种情况，若该节点为父节点的右子树，则该节点的前驱为父节点。例 7的前驱是6.
若该节点为父节点的左子树，则顺着父节点找，找到某个父节点（父节点的父节点…）的孩子结点为它某个父节点…中的右子树，则该节点的父节点为此节点的前驱。例 2的前驱节点是1
源代码

BiTree Delete(BiTree bst,int key)
{BiTree p,f,s,q;//
 p=bst;
 f=NULL;
while(p)
{
	if(p->key==key) break;
	f=p;//找p结点的父结点f 
	if(p->key>key) p=p->left;
	else p=p->right;	
}
if(p==NULL) return bst;//找不到p 
 if(p->left==NULL)//如果删除的结点的左子树为空
 { 
    if(f==NULL) bst=p->right;//找不到父节点，父节点为该节点的跟 
    else if(f->left==p)
    {
    	f->left=p->right;//如果当前父节点的左孩子为待删除的结点，直接把左孩子的左子树赋给父节点 
	}
    else f->right=p->right;//如果当前父节点的右孩子为待删除的结点，直接把右孩子的 
  }
  else
  { 
    q=p;//定义 q结点为s结点的父节点 
    s=p->left;//s节点为p节点的前驱，中序遍历p节点的前驱为左子树后一直右子树到头 
    while(s->right)
    {
    	q=s;
    	s=s->right; 
	}
	if(p==q) //q有左子树无右子树  前驱节点为相邻的左子树 
  	{    q->left=s->left;// 
  		q->key=s->key;		
	  }
	  else//q有左子树有右子树 前驱节点为左子树的右子树的最后一个右子树，此节点必然没有右子树了 
	  {   //此时删除s,把s的值赋给q. 
	     s->key=p->key;//此时q为p的前驱S的父节点 
	     q->right=s->left; //s必然只有左节点 
	  	
	  }
	  free(s);
}
 return bst;
  	
  	
  	
  }

数据结构之（六）之二叉排序树

相关推荐