二叉排序树怎么构造 哈夫曼树的构造过程

一、二叉排序树构造过程

二叉排序树的构造过程：按照给定序列，以此将结点插入二叉排序树中，在二叉排序树中插入新结点，要保证插入后的二叉树仍符合二叉排序树的定义。

插入过程：若二叉排序树为空，则待插入结点*S作为根结点插入到空树中；

当非空时，将待插结点关键字S->key和树根关键字t->key进行比较，

若s->key=t->key,则无须插入，若s->key<t->key,则插入到根的左子树中，

若s->key>t->key,则插入到根的右子树中。而子树中的插入过程和在树中的插入过程相同，

如此进行下去，直到把结点*s作为一个新的树叶插入到二叉排序树中，或者直到发现树已有相同关键字的结点为止。

说明：

①每次插入的新结点都是二叉排序树上新的叶子结点。

②由不同顺序的关键字序列，会得到不同二叉排序树。

③对于一个任意的关键字序列构造一棵二叉排序树，其实质上对关键字进行排序。

查找的过程类似，从根结点开始进行比较，小于根结点的在左子树上，大于根结点的在右子树上，以此查找下去，直到查找成功或不成功（比较到叶子结点）。

二、二叉平衡排序树是一棵高度最大的树

给定值的比较次数等于给定值节点在二叉排序树中的层数。

如果二叉排序树是平衡的，则n个节点的二叉排序树的高度为Log2(n+1),其查找效率为O(Log2n)，近似于折半查找。

如果二叉排序树完全不平衡，则其深度可达到n，查找效率为O(n)，退化为顺序查找。

一般的，二叉排序树的查找性能在O(Log2n)到O(n)之间。因此，为了获得较好的查找性能，就要构造一棵平衡的二叉排序树。

三、二叉排序树是机构力学嘛

二叉排序树是计算机专业数据结构课程中的一种数据结构。