二叉排序树(急啊)

来源:百度知道 编辑:UC知道 时间:2024/05/11 23:58:15
谁帮我看看这个程序啊,每个编译没问题,可是运行就有错误了,谁帮我改掉这个错误啊,十分感谢!
#ifndef BINARYTREENODE_CLASS
#define BINARYTREENODE_CLASS
#ifndef NULL
const int NULL=0;
#endif
enum boolean{FALSE,TRUE};
template<class T>
class BinaryTreeNode
{
public:
T data;
BinaryTreeNode<T> *LeftChild, //指向左子树根结点的指针
*RightChild; //指向右子树根结点的指针
BinaryTreeNode(void){LeftChild=RightChild=0;}
BinaryTreeNode(const T&e)
{
data=e;
LeftChild=RightChild=NULL;
}
BinaryTreeNode(const T&e,BinaryTreeNode *l,BinaryTreeNode *r)
{
data=e;
LeftChild=l;
RightChild=r;
}
void FreeBTreeNode(BinaryTreeNode<T> *p){delete p;}
BinaryTreeNode<T> *GetBTreeNode(T item,BinaryTreeNode<T> *lptr=NULL,
BinaryTreeNode<T> *rptr=NULL)
{
BinaryTreeNode<T> *p;
p=new BinaryTreeNode<

当用线性表作为表的组织形式时,可以有三种查找法。其中以二分查找效率最高。但由于二分查找要求表中结点按关键字有序,且不能用链表作存储结构,因此,当表的插入或删除操作频繁时,为维护表的有序性,势必要移动表中很多结点。这种由移动结点引起的额外时间开销,就会抵消二分查找的优点。也就是说,二分查找只适用于静态查找表。若要对动态查找表进行高效率的查找,可采用下面介绍的几种特殊的二叉树或树作为表的组织形式。不妨将它们统称为树表。下面将分别讨论在这些树表上进行查找和修改操作的方法。

二叉排序树

1、二叉排序树的定义
二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。其定义为:二叉排序树或者是空树,或者是满足如下性质的二叉树:
①若它的左子树非空,则左子树上所有结点的值均小于根结点的值;
②若它的右子树非空,则右子树上所有结点的值均大于根结点的值;
③左、右子树本身又各是一棵二叉排序树。
上述性质简称二叉排序树性质(BST性质),故二叉排序树实际上是满足BST性质的二叉树。

2、二叉排序树的特点
由BST性质可得:
(1) 二叉排序树中任一结点x,其左(右)子树中任一结点y(若存在)的关键字必小(大)于x的关键字。
(2) 二叉排序树中,各结点关键字是惟一的。
注意:
实际应用中,不能保证被查找的数据集中各元素的关键字互不相同,所以可将二叉排序树定义中BST性质(1)里的"小于"改为"大于等于",或将BST性质(2)里的"大于"改为"小于等于",甚至可同时修改这两个性质。
(3) 按中序遍历该树所得到的中序序列是一个递增有序序列。
【例】下图所示的两棵树均是二叉排序树,它们的中序序列均为有序序列:2,3,4,5,7,8。

3、二叉排序树的存储结构
typedef int KeyType; //假定关键字类型为整数
typedef struct node { //结点类型