二叉排序树查找算法 基本概念顺序查找二分查找分块索引查找二叉排序树的查找.ppt(3)

② 若k小于根结点的值,则在根的左子树中插入值为k的结点。③ 若k大于根结点的值,则在根的右子树中插入值为k的结点。④ 若k等于根结点的值,表明二叉排序树中已有此关键字,则无须插入。 void BiSortTree::InsertBiNode *&ptr, int k//在以ptr为根的二叉排序树中插入值为k的结点if ptrNULLptrnew BiNode;ptr-keyk;ptr-lchildptr-rchildNULL;elseif kptr-key Insertptr-lchild, k;else ifkptr-key Insertptr-rchild, k;void BiSortTree::Insertint kInsertroot,k; 二叉排序树的建立算法 BiSortTree::BiSortTreeinta[ ], int nroot NULL; for int i 0; i n; i++ Insert root, a[i];3.二叉排序树的查找过程 查找给定值k的过程如下:① 若二叉排序树为空,则表明查找失败,返回空指针;否则,若给定值k等于根结点的值,则表明查找成功,返回根结点;② 若给定值k小于根结点的值,则继续在根的左子树中查找;③ 若给定值k大于根结点的值,则继续在根的右子树中查找。

这是一个递归查找过程。BiNode* BiSortTree::SearchBiNode *ptr, intk//在以ptr为根的二叉排序树中查找关键字为k的结点if ptrNULL return NULL; else if ptr-keyk return ptr;else if kptr-keyreturn Search ptr-lchild, k; else return Searchptr-rchild, k;bool BiSortTree::Searchint k//查找return Searchroot, k!NULL; 非递归算法: 循环实现BiNode* BiSortTree::Search2BiNode *ptr, intk//在以ptr为根的二叉排序树中查找值为k的结点while ptr if kptr-key return ptr;else if kptr-key ptrptr-lchild; else ptrptr-rchild;return NULL;bool BiSortTree::Search2int k//查找return Search2root,k!NULL;4.二叉排序树的删除操作4.二叉排序树的删除操作分三种情况 :(1)删除叶子结点? (2)删除单支结点? (3)删除双支结点递归删除算法的步骤如下:① 若二叉排序树为空,则表明不存在删除的结点,不进行删除操作。

② 若给定值 k小于根结点的值,则继续在根的左子树中删除。③ 若给定值 k大于根结点的值,则继续在根的右子树中删除。④ 若给定值 k等于根结点的值,则根结点即为要删除的结点,此时需要根据上述分析的三种结点情况:叶子结点、单支结点或双支结点,执行相应的删除操作。? void BiSortTree::DeleteBiNode *&ptr, int k//在以ptr为根的二叉排序树中删除值为k的结点if ptr!NULLif kptr-key Deleteptr-lchild,k;//在左子树进行删除else if kptr-key Deleteptr-rchild,k;//在右子树进行删除 else //ptr指向的结点就是要删除的结点? if ptr-lchild!NULL&&ptr-rchild!NULL //双支结点 tempptr-lchild;while temp-rchild!NULLtemptemp-rchild;//寻找左子树中具有最大值的结点ptr-keytemp-key;Deleteptr-lchild, temp-key; ? else tempptr;if ptr-lchildNULL //单支结点,左子树为空 ptrptr-rchild;else if ptr-rchildNULL //单支结点,右子树为空 ptrptr-lchild; delete temp; //删除 void BiSortTree::Deleteint k //删除Deleteroot,k;9.6 平衡二叉树问题的提出什么是平衡二叉树平衡二叉树的建立

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