计算机软件技术06第三章 查找及排序技术(下)_40学时.ppt

计算机软件技术基础 第三章 查找与排序技术（下） 3.4 二叉排序树及其查找 从线性表的顺序查找与对分查找可以看出，对分查找的效率要比顺序查找高，但对分查找只适用于顺序存储结构的有序线性表。 接下来介绍的二叉排序树及其查找方式是一种对于无序表的查找方法，当采用一种适合的存储结构后，其查找效率与有序表的对分查找基本接近。 二叉排序树的结点结构与一般二叉树相同 //定义二叉排序树结点类型 template class T struct BSnode { T d; //数据域 BSnode *lchilid; //左指针域 BSnode *rchild; //右指针域 }; 在C++中，可以定义二叉排序树类BS_Tree如下： //文件名BS_Tree.h #include iostream using namespace std; //定义二叉链表结点类型 template class T struct BSnode { T d; //数据域 BSnode *lchilid; //左指针域 BSnode *rchild; //右指针域 }; //二叉排序树类 template class T class BS_Tree { private: BSnodeT *BT; public: BS_Tree() { BT=NULL; return; } void insert_BS_Tree(T); int delete_BS_Tree(T); BSnodeT *serch_BS_Tree(T) void intrav_BS_Tree(); }; 3.4.1 二叉排序树的基本概念 二叉排序树的递归定义： (1)左子树上的所有结点值均小于根结点值； (2)右子树上的所有结点值均不小于根结点值； (3)左、右子树也满足上述两个条件。 二叉排序树中的结点值都是应该可以互相比较的； 并且在二叉排序树中，所有结点以根结点为界按值分成了两部分：左子树上的所有结点值均小于右子树上的所有结点值。 3.4.2 二叉排序树的插入 根据给定的元素序列来构造二叉排序树： 依次读入给定序列中的每一个元素，然后进行如下处理： (1)若当前的二叉排序树为空，则读入的元素为根结点； (2)若读入的元素值小于根结点值，则将元素插入到左子树中； (3)若读入的元素值不小于根结点值，则将元素插入到右子树中。 无论是插入到左子树还是右子树，同样按照上述方法处理。 例： 给定一个数据元素序列( 53, 61, 12, 37, 90, 100, 3, 78, 45 )，画出对应二叉排序树。 如果给定一个数据元素的集合，则数据元素的读入顺序不同，其构造出的二叉排序树的形态也不同。 二叉排序树的插入算法 //二叉排序树的插入 template class T void BS_TreeT::insert_BS_Tree ( T x ) { BSnodeT *p, *q; p = new BSnodeT; //申请一个新结点 p-d = x; //置新结点的值域 //置新结点左右指针均为空 p-lchild = NULL; p-rchild = NULL; q = BT; //从根结点开始 if ( q==NULL ) BT=p; //树空，新结点为根结点 else //未到叶子结点 { while (( q-lchild != p )( q-rchild != p )) { if ( x q-d ) //插入到左子树 { if ( q-lchild != NULL ) q = q-lchild; else q-lchild = p; } else //插入右子树 { if ( q-rchild != NULL ) q = q-rchild; else q-rchild = p; } } } return; } 二叉排序树的特性 中序遍历二叉排序树可以得到有序序列。 在二叉排序树中插入的新结点均为叶子结点，所以不需要移动其它结点，而只需要改动叶子结点的指针即可。 如何删除二叉排序树中的一个结点？ 3.4.3 二叉排序树的删除 试编写在二叉排序树中删除一个元素的算法。 二叉树排序树的性质： (1)左子树上的所有结点值均小于根结点值； (2)右子树上的所有结点值均不小于根结点值； (3)左、右子树也满足上述两个条件。 分析 解题思想： 要保证二叉树的树形； 要保证所有父结点和