【数据结构】4. 树与二叉树

二叉排序树作为一种动态集合，其特点是树的结构通常不是一次生成的，而是在査找过程中，当树中不存在关键字等于给定值的结点时再进行插入。
由于二叉排序树是递归定义的，插入结点的过程是，若原二叉排序树为空，则直接插入结点；否则，若关键字 k 小于根结点关键字，则插入到左子树中，若关键字 k 大于根结点关键字，则插入到右子树中。

int BST_Insert(BiTree &T,KeyType k) {
//在二叉奋序树 T 中插入一个关键字为 k 的结点
    if(T == NULL){ //原树为空，新插入的记录为根结点
        T=(BiTree)malloc(sizeof(BSTNode));
        T->key = k;
        T->lchild = T->rhild = NULL;
        return 1; //返回 1，表示成功
    } else if(k == T->key) //树中存在相同关键字的结点
        return 0;
    else if(k<T->key) //插入到 T 的左子树中
        return BST_Insert(T->lchild,k);
    else //插入到 T 的右子树中
        return BST_Insert(T->rchild,k);
}

由此可见，插入的新结点一定是某个叶结点。
如图 4-21 所示，在一个二叉排序树先后依次插入结点 28 和结点 58,虚线表示的边是其査找的路径。

（4）二叉排序树的构造

（编辑：南平站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!