遍历二叉树、恢复二叉树以及平均查找长度

数据结构中的二叉树的前(先)序遍历,中序遍历,后序遍历,遍历二叉树

这里拿一个考研真题举例子,A是根结点

二叉树的前(先)序,根左右(根结点排第一个),

ABDECFGH

后序遍历,左右根(根结点排最后一个),

EDBGHFCA

中序遍历需要借助null来写,左根右(根结点在中间)

节省时间,随便画一画

null D E B A null C (右比较多,看作一个整体) G F H

那么最后中序遍历是 DEBACGFH

还有一个层次遍历,ABCDFEGH(考层次遍历考的比较少)

结论,前序遍历根结点一定在第一个,中序遍历根结点在中间,后序遍历根结点在最后一个,知道前序和后序遍历,是不能确定唯一的二叉树的,相反,只要知道中序遍历和前后中的一个,即可确定唯一的二叉树,如果二叉树比较复杂的话,推荐中和后序遍历借助null来写

下面一个例题来说明

恢复二叉树

考研真题

画出有 3 个结点的所有二叉树 ,画出有3个结点的树

满二叉树的定义:除最后一层外没有任何子结点,其他每一层上的结点都有两个子结点

根结点就是最上面的,

结点就是每个圈

二叉排序树(二叉搜索树,二叉查找树)

30是根结点,15比30小,放在30左子树,28也比30小,放左子树,再去比较15,比15大,说明在15的右子树,以此类推

赞赏

微信赞赏支付宝赞赏

357 次阅读量

发表评论