Question

将整数序列{4,5,7,2,1,3,6}中的数依此插入到一棵空的二叉排序树中，试构造相应的二叉排序

将整数序列{4,5,7,2,1,3,6}中的数依此插入到一棵空的二叉排序树中，试构造相应的二叉排序树，要求用图形给出构造过程，不需编写程序

Answer 1

将整数序列{4,5,7,2,1,3,6}中的数依次插入到一棵空的二叉排序树中，相应的二叉排序树是：

平均查找长度=1*1+2*2+3*3+4*3=26

(第一层一个结点，每个结点比较一次查找成功；第二层两个结点，每个结点比较两次查找成功；第三层三个结点，每个结点比较三次查找成功；第四层三个结点，每个结点比较四次查找成功)。

扩展资料：

性质1：二叉树的第i层上至多有2i-1（i≥1）个节点。

性质2：深度为h的二叉树中至多含有2h-1个节点。

性质3：若在任意一棵二叉树中，有n0个叶子节点，有n2个度为2的节点，则必有n0=n2+1。

性质4：具有n个节点的完全二叉树深为log2x+1（其中x表示不大于n的最大整数）。

参考资料来源：百度百科-二叉树

Answer 2

7505535棵