培训啦 学历 考研

2022计算机考研备考:依据先序后序生成二叉树

发布时间: 2023-01-14 11:12:02
2022计算机考研备考:依据先序后序生成二叉树

2022计算机考研备考:依据先序后序生成二叉树

备考的你是否已经开始了呢?今天给大家整理了依据先序后序生成二叉树的相关内容,希望对大家有所帮助~

题目:已知二叉树的先序遍历序列和后序遍历序列,试编写生成该二叉树的算法。

思路:先序 pre = DLR,后序 post = LRD,D表示根结点,L表示左子树,R为右子树。

从先序出发:取先序的第一个元素pre[0]做根,第二个元素pre[1]做左子树的根(不确定也可能是右子树的根,但是先序是根左右,先认为它是左子树的根),然后去后序序列找pre[1]这个元素的下标位置i,在后序序列里,下标i到最后一个元素间没有元素,说明这个树只有一个子树(可以是左子树或右子树);有元素,那这段序列是右子树,下标i往前到post[0]是左子树。对左子树和右子树分别再这样分出根、左子树和右子树。

算法:

def func(pre[],post[]) {

int index = 0;

if(length(pre) == 0) return NULL;

node = BinTnode(pre[0]);

if(length(pre) == 1) return node;

while (pre[1] != post[index]){

index=index+1;

}

node->left = func(pre[1:index+1],post[0:index]);

node->right = func(pre[index+2:n],post[index+1:n-1]);

return node;

}

思考:或者从后序出发:取后序最后一个元素做根,倒数第二个元素是右子树的根A,去先序序列里找这个A的下标,这个下标往后的先序序列是右子树,往前到pre[1]是左子树,其他思路同上。请根据上述内容试着写一下这个算法吧。

以上是小编整理的关于“2022计算机考研备考:依据先序后序生成二叉树”的相关内容,希望对小伙伴们有所帮助。

.xqy_container .xqy_core .xqy_core_main .xqy_core_text{height:auto !important;} 2022计算机考研备考:依据先序后序生成二叉树
温馨提示:
本文【2022计算机考研备考:依据先序后序生成二叉树】由作者教培参考提供。该文观点仅代表作者本人,培训啦系信息发布平台,仅提供信息存储空间服务,若存在侵权问题,请及时联系管理员或作者进行删除。
我们采用的作品包括内容和图片部分来源于网络用户投稿,我们不确定投稿用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的权利,请联系我站将及时删除。
内容侵权、违法和不良信息举报
Copyright @ 2024 培训啦 All Rights Reserved 版权所有. 湘ICP备2022011548号