构造平衡二叉树例题 二叉排序树的定义,平衡二叉树和某接点的平衡因子的定义?
浏览量:2459
时间:2021-03-11 19:44:25
作者:admin
二叉排序树的定义,平衡二叉树和某接点的平衡因子的定义?
二叉排序树也称为二叉搜索树。它要么是空树,要么具有以下属性:(1)如果其左子树不为空,则左子树上所有节点的值都小于根节点的值。(2) 如果右子树不为空,则右子树中所有节点的值都大于根节点的值。(3) 左右子树也是二叉排序树。
平衡二叉树是具有以下属性的空树或二叉排序树:(1)左右子树都是平衡二叉树;(2) 左右子树高差的绝对值
如果左右子树的高差称为节点x的平衡因子,则用BF(x)表示。
从平衡二叉树的定义可知:BF(x)=x左子树深度-x右子树深度
简而言之,它是一个平衡的二叉排序树,即先是一个二叉排序树,然后才是平衡的。它要么是一棵空树,要么左右子树的高度差的绝对值不大于1,左右子树都是一棵平衡的二叉树
构造平衡二叉树例题 完全二叉树一定是平衡二叉树 平衡二叉树例题
版权声明:本文内容由互联网用户自发贡献,本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。