nbsp; 二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：（1）若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；（2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；（3）它的左右子树也分别为二叉排序树。
程序中分别采用了“二插链表”和“一维数组”作为其存储结构。
二插链表存储结构中二插树的结点由一个数据元素和分别指向其左、右子树的两个分支构成。如：我的程序中采用的结构是：
typedef struct tnode{
int data; /*数据元素*/
struct tnode *lchild,*rchild；/*左右指针*/
}*node,bstnode;
一维数组顺序表存储结构是用一组地址连续的存储单元依次自上而下、自左而右存储完全二插树上的结点元素，即将完全二叉树上编号为i的结点元素存储在如上定义的一维数组中下标为i-1的分量中。利用顺序表作为存储结构：
typedef struct {
int *data; /*一维数组基址*/
int lenth; /*一维数组的长度*/
}bst;
一维数组存储结构中结点i的父母亲为|_i/2_|,左孩子为2i，右孩子为2i+1.
三、算法的设计思想
a)二插链表作存储结构：
建立二插排序树采用边查找边插入的方式。查找函数采用递归的方式进行查找。如果查找成功则不应再插入原树，否则返回当前结点的上一个结点。然后利用插入函数将该元素插入原树。
&nb
上一页 [1] [2] [3] [4] [5] [6] 下一页