★二叉排序树 心定义:二叉排序树或是一棵空树,或是具有下列性质 的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根 结点的值 ●若它的子树不空,则右子树上所有结点的值均大于或等于 它的根结点的值 ●它的左、右子树也分别为二叉排序树 今二叉排序树的插入 ●插入原则:若二叉排序树为空,则插入结点应为新的根结点; 否则,继续在其左、右子树上查找,直至某个叶子结点的左 子树或右子树为空为止.则插入结点应为该叶子结点的左孩 子或右孩子 ●二叉排序树生成:从空树出发,经过一系列的查找、插入操 作之后,可生成一棵二叉排序树二叉排序树 ❖定义：二叉排序树或是一棵空树，或是具有下列性质 的二叉树： ⚫若它的左子树不空，则左子树上所有结点的值均小于它的根 结点的值 ⚫若它的右子树不空，则右子树上所有结点的值均大于或等于 它的根结点的值 ⚫它的左、右子树也分别为二叉排序树 ❖二叉排序树的插入 ⚫插入原则：若二叉排序树为空，则插入结点应为新的根结点； 否则，继续在其左、右子树上查找，直至某个叶子结点的左 子树或右子树为空为止，则插入结点应为该叶子结点的左孩 子或右孩子 ⚫二叉排序树生成：从空树出发，经过一系列的查找、插入操 作之后，可生成一棵二叉排序树