一棵树的后序遍历和这棵树对应的二叉树的中序遍历相同 以及 高效的二叉树~

一棵树的后序遍历和这棵树对应的二叉树的()相同。
A.先序遍历 B.中序遍历 C.后序遍历 D.层次遍历

嗯 就这么道题

拆分下题目就是
一棵树的后序遍历 == 这棵树拆成二叉树的中序遍历
下面来解题

文章目录

1.解题

来解题
这题
其实用试的是很快的~
还是用这个例子

【1】普通树的后序遍历

《一棵树的后序遍历和这棵树对应的二叉树的中序遍历相同 以及 高效的二叉树~》

后序遍历 左右中(左后 右后 根)—— 翻译得详细些就是——

最开始 遍历到(还有左子树的)最深处的节点

【1】先访问该节点的左子树

2

【2】然后访问其余子树(以同样规则访问其余子树—先左后其他)

56 34

【3】最后访问根

1

得到结果 2 5634 1

【2】二叉树的中序遍历

《一棵树的后序遍历和这棵树对应的二叉树的中序遍历相同 以及 高效的二叉树~》

最开始 遍历到(还有左子树的)最深处的节点

【1】先访问该节点的左子树

2

【2】访问该左子树的右子树

56 3 4

【3】最后访问根
1

同样得到结果 2 5634 1

一棵树的后序遍历和这棵树对应的二叉树的(B)相同。
A.先序遍历 B.中序遍历 C.后序遍历 > D.层次遍历

好的我得到答案了(逃)

2.更省空间的二叉树表示法

下面来看看为啥二叉树更节省空间~

一天一个小知识:二叉树表示法(即左孩子右兄弟表示法)更加节省空间
(下面解释了 为啥这个表示法叫“左孩子右兄弟表示法~”)
为啥?
三叉树中每个节点都存储3个指针域(因为是三叉树嘛 时刻准备着连三个孩子)
造成有效指针域(指向明确节点的)非常少!
《一棵树的后序遍历和这棵树对应的二叉树的中序遍历相同 以及 高效的二叉树~》
像这个三叉树就有6*3个指针域 但是有效指针域只有5个 浪费13个。

做个转换
二叉树
《一棵树的后序遍历和这棵树对应的二叉树的中序遍历相同 以及 高效的二叉树~》
是的 普通树到二叉树的转换就是那么简单
保留所有左子树的结构 之前是兄弟的 变成右儿子就好了
咳咳接下来来看看二叉树的效率
6*2个指针域 同样是5个的有效指针域 浪费了7个指针域。
很明显 比多叉树要香嘛!!

其中k元n叉树中的k和n越大 转换成二叉树越省空间!
n元k叉树浪费的空间——kn -(n-1)
n元2叉树浪费的空间——2n – (n-1)

    原文作者:敲代码的小提琴手
    原文地址: https://blog.csdn.net/qq_45704942/article/details/116572222
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞