叉排序树.pptVIP

二叉排序树定义 二叉排序树又称二叉查找树它或者是一棵空树，或者是一棵具有如下特性的非空二叉树。 若它的左子树非空，则左子树上所有结点的关键字均小于根结点的关键字； 若它的右子树非空，则右子树上所有的关键字均大于（若允许具有相同的关键字的结点存在，则大于等于）根结点的关键字； 左、右子树本身又各是一棵二叉排序树。 特点：中序遍历序列为非递减序列。 (2 4 5 7 8 ) 4 8 2 7 5 18 12 10 (12 18) 根 二叉排序树的插入和生成 插入规则 若二叉树为空，新结点作为根结点插入 若新结点小于根结点，则插入到根结点的左子树上 若新结点大于根结点，则插入到根结点的右子树上 二叉排序树的插入过程可看成是在有序列中查找插入位置的过程。 二叉排序树插入结果 对于任一结点，左子结点比双亲结点要小 对于任一结点，右子结点比双亲结点要大 10 10 18 10 18 3 10 18 3 8 10 18 3 8 12 10 18 3 8 12 2 10 18 3 8 12 2 7 10 18 3 8 12 2 7 4 【例】已知关键字序列{10, 18, 3, 8, 12, 2, 7, 4}，请给出构造一颗二叉排序树的过程。 二叉排序树的查找 BTNode* BSTSearch(BTNode *root,DataType item) { BTNode *p=root; if(root==NULL) return NULL; //空树查找失败 while(p!=NULL) { if(item==p-data) return p; //查找成功 if(itemp-data) p=p-left; //在左子树中查找 else p=p-right; //在右子树中查找 } return NULL; //到达终点结点查找失败 } 4 8 2 7 5 18 12 10 【例】在下面二叉排序中查找 7 和 15 。 root p p p p p p 查找7：10?4?8?7，比较4次，查找成功 查找15：10?18?12，比较3次，查找失败 p=NULL 在二叉排序中删除叶子结点 删除该结点并将其双亲结点中相应的指针域置空 在二叉排序中删除单支结点 直接删除该结点，并将被删除结点非空子树的根 作为其双亲结点的相应子女 在二叉排序中删除双支结点 用被删结点的中序前驱结点（或中序后继）代替被删结点，然后删除它的中序前驱（或中序后继） 中序前驱：左子树的最右结点 中序后继：右子树的最左结点 在二叉排序中删除叶子结点 8 16 2 7 12 5 15 ^ ^ ^ ^ ^ ^ root （2 3 4 5 6 7） （12 15 16 ） 删除该结点并将其双亲结点中相应的指针域置空 4 ^ 6 ^ ^ ^ 3 ^ ^ 在二叉排序中删除单支结点 直接删除该结点，并将被删除结点非空子树的根 作为其双亲结点的相应子女 8 2 7 5 ^ 12 15 ^ ^ ^ ^ 16 ^ root （2 3 4 5 6 7） （12 15 16 ） 4 ^ 6 ^ ^ 3 ^ ^ 在二叉排序中删除双支结点 用被删结点的中序前驱结点代替被删结点，然后删除它的中序前驱 8 2 7 5 ^ 12 15 ^ ^ ^ ^ 16 ^ root （2 3 4 5 6 7） （12 15 16 ） 6 ^ ^ 3 ^ ^ 4 ^ 4 3 ^ ^ 中序前驱（左子树的最右结点）的右子树一定为空 用被删结点的中序后继结点代替被删结点，然后删除它的中序后继 8 2 7 5 ^ 12 15 ^ ^ ^ ^ 16 ^ root （2 3 4 5 6 7） （12 15 16 ） 6 ^ ^ ^ 3 ^ ^ 4 ^ 6 中序后继（右子树的最左结点）的左子树一定为空 课后练习 画出序列 5,3,7,2,4,8 所对应的二叉排序树； 在下面二叉排序树中分别删除1、10、6；