首页 > 代码库 > 二叉排序树(C与Python分别实现)

二叉排序树(C与Python分别实现)

1.      什么是二叉排序树?

二叉排序树是一种特殊的二叉树,可以是一棵空树,也可以是具有下列性质的二叉树:

1.      若左子树不为空,那么左子树所有结点的值都小于它的根结点的值。

2.      若右子树不为空,那么右子树所有结点的值都大于它的根节点的值。

3.      它的左右子树也分别是二叉排序树。

二叉排序树又称二叉查找树,是一种动态查找表,所谓动态查找表是指除了查询检索操作以外,还可以进行插入、删除操作的结构;与之相对应的就是静态查找表,只能进行查询检索操作。

2.      二叉排序树的操作

对于二叉排序树的实现就是对查找、插入、删除操作的实现,因为要进行插入删除操作,所以要用链表结构来实现,操作介绍如下:

1.   查找key:从根结点出发,若key大于根结点则向根结点的右侧走,跟这个根结点的右结点比较,若key小于根结点则向根结点的左侧走,跟这个根结点做结点比较,该根结点的左右子树分别都是二叉排序树,所以重复上面的步骤,直到找到key,或者到NULL(叶子结点的子结点为空)。

2.   插入key:跟查找key步骤相同,找到key时返回,不进行插入,未找到时,在最后一个查找叶子结点下插入key值,若key大于该叶子结点的值则插入该叶子结点的右侧,作为该叶子结点的右子树,否则作为左子树。

3.   删除key:跟查找key步骤相同,若查找最终为NULL(未找到),则返回,若在结点p处找到key,则进行一下判断:

    a.      若p为叶子结点,先找到p的父节点q,若p为q的左子树,则将q的左子树指针至NULL,若p为q的右子树,则将q的右子树指针至NULL,删除p

    b.      若p的左子树不为空,右子树为空,则找到p的父节点q,若p是q的左子树,则将q的左子树指针指向p的左子树,若p是q的右子树,则将q的右子树指针指向p的左子树,删除p

    c.      若p的右子树不为空,左子树为空,则找到p的父节点q,若p是q的左子树,则将q的左子树指针指向p的右子树,若p是q的右子树,则将q的右子树指针指向p的右子树,删除p

    d.      若p的左右子树都不为空,则找到p的父节点q,将p的左子树作为p右子树的最左结点的子结点,然判断p是q的右子树还是q的左子树,若p是q的左子树,则将q的左子树指针指向p的右子树,若p是q的右子树,则将q的右子树指针指向p的右子树,删除p

3.      二叉排序树代码实现:

C代码

注意:下面的查找操作使用的是递归方式实现,既然是递归就有递归深度的问题,太深容易造成堆栈溢出,在我电脑上最多可以进行10357次递归;可用循环替代递归。

#include <stdio.h>
typedef struct  TNode
{
	int nKey;
	struct TNode* lchild;
	struct TNode* rchild;
	struct TNode* parent;
}TNode;
//++++++++++++++++++++++++++查找检索操作++++++++++++++++++++++++++/
bool SearchBST(TNode* BST,int key,TNode* &pSearch,TNode* &pParent)
{
	if ( !BST )
	{
		pSearch = pParent;
		return false;
	}
	if ( BST->nKey == key )
	{
		pSearch = BST;
		pParent = pSearch->parent;
		return true;
	}
	else if ( BST->nKey>key )
	{
		pParent = BST;
		return SearchBST(BST->lchild,key,pSearch,pParent);
	}
	else
	{
		pParent = BST;
		return SearchBST(BST->rchild,key,pSearch,pParent);
	}
	return false;
}
//++++++++++++++++++++++++++结点插入操作++++++++++++++++++++++++++/
bool InsertNode(TNode* &BST,int key,TNode* &pSearch)
{
	TNode* pParent = NULL;
	if ( SearchBST(BST,key,pSearch,pParent) )
		return false;
	TNode* pNode = new TNode;
	pNode->nKey = key;
	pNode->parent = pParent;
	pNode->lchild = NULL;
	pNode->rchild = NULL;
	if ( !pParent )
		BST = pNode;
	else if ( key>pParent->nKey )
		pParent->rchild = pNode;
	else 
		pParent->lchild = pNode;
	pSearch = pNode;
	return true;
}
//++++++++++++++++++++++++++删除结点操作++++++++++++++++++++++++++/
bool DeleteNode(TNode* BST,int key)
{
	TNode* pSearch = NULL;
	TNode* pParent = NULL;
	if ( !SearchBST(BST,key,pSearch,pParent) )
		return false;
	if ( NULL!=pSearch->lchild && NULL!=pSearch->rchild )
	{
		TNode *pTmp = pSearch->rchild;
		while(pTmp->lchild) pTmp = pTmp->lchild;
		pTmp->lchild = pSearch->lchild;
		pSearch->lchild->parent = pTmp->lchild;
		if ( pParent->lchild == pSearch )
			pParent->lchild = pSearch->rchild;
		else
			pParent->rchild = pSearch->rchild;
		pSearch->rchild->parent=pParent;
	}
	else if ( NULL!=pSearch->lchild )
	{
		if( pParent->lchild == pSearch )
			pParent->lchild = pSearch->lchild;
		else
			pParent->rchild = pSearch->lchild;
	}
	else if ( NULL!=pSearch->rchild )
	{
		if ( pParent->lchild == pSearch )
			pParent->lchild = pSearch->rchild;
		else
			pParent->rchild = pSearch->rchild;
	}
	else
	{
		if( pParent->lchild == pSearch )
			pParent->lchild = NULL;
		else
			pParent->rchild = NULL;
	}
	delete pSearch;
	pSearch = NULL;
	return true;
}
//++++++++++++++++++++++++++释放内存操作++++++++++++++++++++++++++/
void DeleteBST(TNode* BST)
{
	if( !BST )return;
	if ( !BST->lchild && !BST->rchild )
	{
		if( !BST->parent && BST->parent->lchild == BST )
			BST->parent->lchild = NULL;
		else if( !BST->parent && BST->parent->rchild == BST ) 
			BST->parent->rchild = NULL;
		delete BST;
		BST = NULL;
		return;
	}
	DeleteBST(BST->lchild);
	DeleteBST(BST->rchild);	
}
//++++++++++++++++++++++++++main测试++++++++++++++++++++++++++/
int main(int argc, char* argv[])
{
	TNode* BST = NULL;
	TNode* pNode = NULL;
	TNode* pParent = NULL;
	int nCount = 10358;
	for ( int i=0;i<nCount;i++ )
	{
		if( InsertNode(BST,i,pNode) )
			printf("插入%d成功\n",i);
	}
	if ( SearchBST(BST,nCount-1,pNode,pParent) )
	{
		printf("查找成功\n");
	}
	DeleteNode(BST,1);
	if ( !SearchBST(BST,1,pNode,pParent) )
	{
		printf("查找失败");
	}
	DeleteBST(BST);
	getchar();
	return 0;
}

Python代码

第一次学习Python,代码中肯定有许多不足之处,希望指正,暂时实现如下:

#BST.py
_Debug = False
#+++++++++++++++++++++struct realized by class+++++++++++++++++++++#
class TNode:
    def __init__(self,key,left,right,parent):
        self.key=key
        self.lchild=left
        self.rchild=right
        self.parent=parent
class PTNode:
    def __init__(self,TNode):
        self.TNode=TNode
#+++++++++++++++++++++++++search operation+++++++++++++++++++++++++#
def SearchBST(BST,key,search,parent):
    if None==BST or None==BST.key:
        return False
    if key==BST.key:
        parent.TNode=BST.parent
        search.TNode=BST
        return True
    elif key<BST.key:
        parent.TNode=BST
        return SearchBST(BST.lchild,key,search,parent)
    else:
        parent.TNode=BST
        return SearchBST(BST.rchild,key,search,parent)
    return False
#+++++++++++++++++++++++++Insert operation+++++++++++++++++++++++++#
def InsertNode(BST,key,search):
    Pparent=PTNode(BST)
    Psearch=PTNode(BST)
    if _Debug==True:
        import pdb
        pdb.set_trace()
    if SearchBST(BST,key,Psearch,Pparent):
       return False
    parent=Pparent.TNode
    search=Psearch.TNode
    Node=TNode(key,None,None,None)
    if None==parent or None==parent.key:
        BST=Node
        return True
    if key>parent.key:
        parent.rchild=Node
    else:
        parent.lchild=Node
    Node.parent=parent
    search=Node
    return True
#+++++++++++++++++++++++++Delete operation+++++++++++++++++++++++++#
def DeleteNode(BST,key):
    Pparent=PTNode(BST)
    Psearch=PTNode(BST)
    if False==SearchBST(BST,key,Psearch,Pparent):
        return False
    parent=Pparent.TNode
    search=Psearch.TNode
    if None!=search.lchild and None!=search.rchild:
        tmp=search
        while(None!=tmp.lchild):
            tmp=tmp.lchild
        tmp.lchild=search.lchild
        if None!=parent and search==parent.lchild:

            parent.lchild=search.rchild
            search.rchild.parent=parent
        elif None!=parent and search==parent.rchild:
            parent.rchild=search.rchild
            search.rchild.parent=parent

    elif None!=search.lchild:
        if None!=parent and search==parent.lchild:
            parent.lchild=search.lchild
            search.lchild.parent=parent
        elif None!=parent and search==parent.rchild:
            parent.rchild=search.lchild
            search.lchild.parent=parent
    elif None!=search.rchild:
        if None!=parent and search==parent.lchild:
            parent.lchild=search.rchild
            search.rchild.parent=parent
        elif None!=parent and search==parent.rchild:
            parent.rchild=search.rchild
            search.rchild.parent=parent
    else:
        parent.lchild=None
        parent.rchild=None
    del search
    search=None
    return True
#+++++++++++++++++++++++++Release operation+++++++++++++++++++++++++#
def DeleteBST(BST):
    if None!=BST:
        if None==BST.lchild and None==BST.rchild:
            tmp=BST.parent
            if tmp!=None and tmp.lchild==BST:
                tmp.lchild=None
            elif tmp!=None and tmp.rchild==BST:
                tmp.rhicld=None
            del BST
            BST=None
            return
        DeleteBST(BST.lchild)
        DeleteBST(BST.rchild)
    
#+++++++++++++++++++++++++Print  operation+++++++++++++++++++++++++#
def PrintBST(BST):
    if None==BST:
        return
    print BST.key
    PrintBST(BST.lchild)
    PrintBST(BST.rchild)
#++++++++++++++++++++++++++Test operation++++++++++++++++++++++++++#
if __name__=='__main__':
    BST=TNode(0,None,None,None)
    Pparent=PTNode(BST)
    Psearch=PTNode(BST)
    for i in range(1,4):
        if False==InsertNode(BST,i,Psearch.TNode):
            print 'Insert Number %d Failed.'%(i)
    print 'print BST:'
    PrintBST(BST)
    if True==SearchBST(BST,1,Psearch,Pparent):
        print 'Find 1 in BST Sucess.'
    if True==DeleteNode(BST,1):
            print 'Delete 1 Success.'
    if False==SearchBST(BST,1,Psearch,Pparent):
        print 'Find 1 in BST Failed.'

    DeleteBST(BST)
    print 'Done'

4.      二叉排序树的查找复杂度

最坏复杂度为O(n),最好为O(1)

参考:《数据结构(C语言版)》严蔚敏 吴为民

 

 

二叉排序树(C与Python分别实现)