构造二叉排序树_序列构造二叉排序树_构造二叉排序树代码(3)

若查找成功，则返回指向该元素节点的指针，否则返回NULL

*/

BSTreesearch(BSTreepTree,intkey)

{

if(!pTree||pTree->data==key)//查找到时返回的pTree为该元素节点，没查找到时为NULL

returnpTree;

elseif(key<pTree->data)//如果key小于当前节点的值，则在其左子树中递归查找

returnsearch(pTree->lchild,key);

else//如果key大于当前节点的值，则在其右子树中递归查找

returnsearch(pTree->rchild,key);

}

/*

在指针pTree所指的二叉排序树中递归查找关键字为key的元素，

若查找成功，则返回ture，并查找到的数据对应的节点指针保存在p中，

否则返回false，并将查找路径问的最后一个节点指针保存在p中。

这里的参数parent指向每次递归遍历的子树的根节点的父节点，即始终是参数pTree的父节点，

它的初始值为NULL，其目的是跟踪查找路径问的当前节点的父节点（即上一个访问节点）

该函数用来被后面的插入函数调用。

*/

boolsearch_BSTree(BSTreepTree,intkey,BSTreeparent,BSTree&p)

{

if(!pTree)//如果pTree为NULL，则查找不成功

{//这里包含了树空，即pTree为NULL的情况

p=parent;

returnfalse;

}

else//否则，继续查找

{

if(key==pTree->data)//如果相等，则查找成功

{

p=pTree;

returntrue;

}

elseif(key<pTree->data)//在左子树中递归查找

returnsearch_BSTree(pTree->lchild,key,pTree,p);

else//在右子树中递归查找

returnsearch_BSTree(pTree->rchild,key,pTree,p);

}

}

/*

当在pTree所指向的二叉排序树中查找不到关键字为key的数据元素时，

将其插入该二叉排序树，并返回ture，否则返回false。

树空时插入会改变根节点的值，因此要传入引用。构造二叉排序树

*/

boolinsert(BSTree&pTree,intkey)

{

BSTreep;

if(!search_BSTree(pTree,key,NULL,p))//如果查找失败，则执行插入操作

{

//为新节点分配空间，并对各域赋值

BSTreepNew=(BSTree)malloc(sizeof(NODE));

pNew->data=key;

pNew->lchild=pNew->rchild=NULL;

if(!p)//如果树空，则直接置pNew为根节点

pTree=pNew;

elseif(key<p->data)//作为左孩子插入p的左边

p->lchild=pNew;//作为右孩子插入p的右边

else

p->rchild=pNew;

}

else

returnfalse;

}

/*

采用第一种算法从二叉排序树中删除指针p所指向的节点,

并在保持二叉排序树有序的情况下，将其左右子树重接到该二叉排序树中.

该函数主要用来被后面的删除函数调用

*/

voiddelete_Node1(BSTree&p)

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-24246-3.html