二叉排序树的删除算法_二叉排序树的删除 代码_二叉排序树的删除

最近写了点题目，用到平衡二叉树，以后看过，但是现在完全不记得了......可能以后去面试也要写到平衡二叉树的....重新学习一下.....

平衡二叉树是在二叉排序树的基础上成立的，所以先来弄一下二叉排序树。二叉排序树的删除二叉排序树的删除

#include "stdio.h"

#include "stdlib.h"

//定义二叉排序树的结构

typedef struct BNODE

{

int data;//结点的数据

struct BNODE *lchild, *rchild;//左子树指针和右子树指针

}BNODE,*BTree;

//二叉排序树的查找

bool FindTree(BTree T, int key, BTree f, BTree *p)//指针f指向T的父结点，如果查找成功，p指向该查找的结点，返回true。查找失败p就指向查找路径上时所访问的最后一个结点，返回false

{

if (!T)//查找不成功

{

*p = f;

return false;

}

else if (T->data == key)//查找成功

{

*p = T;

return true;

}

else if (T->data>key)

{

FindTree(T->lchild, key, T, p);//大于就在左子树继续查找

}

else

{

FindTree(T->rchild, key, T, p);//小于就在右子树继续查找

}

}

//二叉排序树的插入操作

bool InsetTree(BTree T, int key)//当二叉排序树T中不存在关键字等于key的数据时，插入key并返回true,否则返回false

{

BTree s, p;

if (!FindTree(T, key, NULL, &p))//查找不成功,插入

{

s = (BTree)malloc(sizeof(BNODE));//创建结点s

s->data = key;

s->lchild = s->rchild = NULL;

if (!p)

T = s;

else if (p->data > key)

p->lchild = s;//插入s为左结点

else

{

p->rchild = s;//插入s为右结点

}

return true;

}

return false;

}

//创建一个二叉排序树，这样就可以创建出上图所示的那个二叉排序树了，各位自己抽象地想象一下

void main()

{

int i;

int a[9] = { 8, 3, 1, 6, 4, 7, 10, 14, 13 };

BTree T = NULL;

for (i = 0; i < 9;i)

{

InsetTree(T, a[i]);

}

}

//从查找到创建二叉排序树挺简单的，但请神容易送神难，二叉排序树的删除操作就难了

//因为根据二叉排序树的结构特点，小的插左边，大的插右边，随便删除一个数据都会导致结构混乱

//解决的方法就是寻找被删除结点数据的前驱或后继来继承被删除结点（就是和被删除结点数据的最接近的那两个结点数据，一大一小）

//最近的结点说我继承了遗产，哇哈哈哈哈

//好了，废话不多说，下面是二叉排序树的删除操作

//如果二叉排序树中存在和key相等的结点，就删除该结点并返回true，否则返回false

bool DeleteTree(BTree *T, int key)

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