树与二叉树

1、将一个无序序列中的元素依次插入到一棵( 二叉排序树 ),并进行中序遍历,可得到一个有序序列。

本题考查数据结构基础知识。
    一个连通图的生成树是一个极小连通子图,它包含图中的全部顶点,但只有构成一棵树的n-1条边。把生成树各边的权值总和称为生成树的权,把权值最小的生成树称为最小生成树。
    哈夫曼树又称最优二叉树,是一类带权路径长度最短的树。若深度为k的二叉树有2k-1个结点,则称其为满二叉树。可以对满二叉树中的结点进行连续编号:约定编号从根结点起,自上而下、自左至右依次进行。深度为k、有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时,称之为完全二叉树。

    二叉排序树又称二叉查找树,它或者是一棵空树,或者是具有如下性质的二叉树。
    若它的左子树非空,则左子树上所有结点的值均小于根结点的值。
    若它的右子树非空,则右子树上所有结点的值均大于根结点的值。
    左、右子树本身就是两棵二叉排序树。
    显然,将一个无序序列中的元素依次插入到一棵二叉排序树中并进行中序遍历,可得到一个有序序列。

发表评论

电子邮件地址不会被公开。 必填项已用*标注