(四)树与二叉树的应用 二叉排序树 定义 二叉排序树(也称二叉查找树)或者是一棵空的二叉树或者是具有下列性质的二叉树 ()若它的左子树不空则左子树上所有结点的值均小于根结点的值 ()若它的右子树不空则右子树上所有结点的值均大于根结点的值 ()它的左右子树也都是二叉排序树 【记】左小于右(左子树<根<右子树) 二叉排序树删除结点 被删除的结点是叶子 被删除的结点只有左子树或者只有右子树 被删除的结点既有左子树也有右子树 平衡二叉树 平衡二叉树或者是一棵空的二叉排序树或者是具有下列性质的二叉排序树 ()根结点的左子树和右子树的深度最多相差; ()根结点的左子树和右子树也都是平衡二叉树 【记】左右高(最)多差一 返回《数据结构》考研复习精编 [] [] [] [] [] [] [] [] [] [] |