|
|
|
若在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素，则称此类查找表为动态查找表。动态查找表的特点是表结构是动态生成的。
|
|
|
|
|
|
二叉排序树又称二叉查找树，它或者是一棵空树，或者是具有以下性质的二叉树。
|
|
|
|
.若它的左子树非空，则左子树上所有节点的值均小于根节点的值。
|
|
|
|
.若它的右子树非空，则右子树上所有节点的值均大于或等于根节点的值。
|
|
|
|
|
|
|
|
若二叉树为非空，将给定值与根节点的关键字值进行比较，若相等，则查找成功；若不等，则当根节点的关键字值大于给定值时，到根的左子树中进行查找；否则到根的右子树进行查找。
|
|
|
|
|
|
二叉排序树是通过依次输入数据元素并把它们插到二叉树的适当位置上构造起来的，具体过程如下：读入一个元素，建立一个新节点。若二叉排序树非空，则将新节点的值与根节点的值进行比较，如果小于根节点的值，则插入左子树中，否则插入右子树中；若二叉树为空，则新节点作为二叉排序树的根节点。
|
|
|
|
|
|
在二叉排序树中删除一个节点，不能把以该节点为根的子树都删除，只能删除这个节点并仍旧保持二叉排序树的特性。
|
|
|
