- 二叉树排序树--kuan -

2007-04-12 晴

int Find(BTreeNdoe *BST, ElemType &item)//从二叉树中查找关键字等于给定值item的元素　时间O(log2n) ~ O(n) 空间O(log2n)
{
if(BST == NULL)
{
return 0;//查找　失败返回0
}
else
{
if(item == BST->data)
{
item = BST->data;
return 1;
}
else if(item < BST->data)
{
return Find(BST->left, item);//向左子树继续查找
}
else
{
return Find(BST->right, item);//向右子树继续查找
}

}
}

int Find(BTreNode *BST, ElemType &item)//进行二叉排序树查找的非递归算法时间O(log2n) ~ O(n)　空间O(1)
{
while(BST != NULL)
{
if(item == BST->data)
{
item = BST->data;
return 1;
}
else if(item < SBT->data)
BST = BST->left;
else
BST = BST->right;
}
return 0;
}

void Insert(BTreeNode *&BST, const ElemType &item)//插入
{
if(BST == NULL)
{
BtreeNode *p = new BTreeNode;
p->data = item;
p->left = p->right = NULL;
BST=p;
}
else if(item < BST->data)
Insert(BST->left, item);
else
Insert(BST->right, item);
}

void Insert(BTreeNode *& BST, const ElemType &item)//非递归插入
{
BTreeNode *t=BST,*parent = NULL;
while(t != NULL)
{
parent=t;
if(item < t->data)
t=t->left;
else
t=t->right;
}

BTreeNode *p=new BTreeNode;
p->data = item;
p->left = p->right = NULL;

if(parent == NULL)
BST=p;
else if(item < parent->data)
parent->left = p;//小的插在左边
else
parent->right = p;//在的插在右边
}

void CreateBSTree(BTreeNode *&BST, ElemType a[], int n)//利用数组元素建立二叉排序树的算法
{
BST=NULL;
for(int i=0; i<n; i++)
Insert(BST, a);
}

int Delete(BTreeNode *&BST, const ElemType &item)//从二叉排序树中删除关键字为item的第一个结点
{
BTreeNode *t=BST, *s=NULL;//指针t指向等比较的结点，指针s指向t的双亲结点，从树根结点开始比较
while(t != NULL)
{
if(item == t->data)
break;
else if(item < t->data)
{
s=t;
t = t->left;
}
else
{
s=t;
t = t->right;
}
}

if(t == NULL)
return 0;//没找到返回0

//分三种不同情况删除已找到的t结点
if(t->left == NULL && t->right == NULL)//t结点为叶子结点
{
if(t == BST)
BST=NULL;
else if(t == s->left)
s->left = NULL;
else
s->right = NULL;
delete t;
}
else if(t->left == NULL || t->right == NULL)//t结点为单分支结点
{
if(t == BST)//根结点
{
if(t->left == NULL)
BST = t->right;
else
BST = t->left;
}
else //删除非树根结点，分四种
{
if(t == s->left && t->left != NULL)
s->left = t->left;
else if(t == s->left && t->right != NULL)
s->left = t->right;
else if(t == s->left && t->right != NULL)
s->right = t->left;
else if(t == s->right && t->right != NULL)
s->right = t->right;
}
delete t;
}
else if(t->left != NULL && t->right != NULL)//t结点为双分支结点
{
BTreeNode *p=t,*q=t->left;//p初始指向t结点，q初始指向p结点的左子树的根结点

//查找t结点的中序前驱结点，查找结束后q结点为t 结点
//的中序前驱结点，p结点为q结点的双亲结点
while(q->right != NULL)
{
p=q;
q = q->right;//向右下

}
//q结点的值赋给t结点
t->data = q->data;
//删除右子树为空的q 结点，使它的左子树链接到它所在的链接位置
if(p == t)
t->left = q->left;
else
p->right = q->left;
delete q;
}
return 1;

}.

[全部]

# posted by kuan @ 2007-04-12 12:55:39 评论(0)

笔名：

评论：

最多1000字。当前字数：0
*

联系方式：