二叉树的先序,中序,后序遍历的序列_二叉树先序遍历和后序遍历正好相反

二叉树的先序,中序,后序遍历的序列_二叉树先序遍历和后序遍历正好相反    二叉树的遍历主要有三种:(1)先(根)序遍历(根左右)(2)中(根)序遍历(左根右)(3)后(根)序遍历(左右根)举个例子:先(根)序遍历(根左右):ABDHEICFJKG中(根)序遍历(左根右):DHBEIAJFKCG后(根)序遍历(左右根):HDIEBJKFGCA    以后(根)序…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

    二叉树的遍历主要有三种:

(1)先(根)序遍历(根左右)

(2)中(根)序遍历(左根右)

(3)后(根)序遍历(左右根)

举个例子:

二叉树的先序,中序,后序遍历的序列_二叉树先序遍历和后序遍历正好相反

先(根)序遍历(根左右):A B D H E I C F J K G

中(根)序遍历(左根右) : D H B E I A J F K C G

后(根)序遍历(左右根) : H D I E B J K F G C A

    以后(根)序遍历为例,每次都是先遍历树的左子树,然后再遍历树的右子树,最后再遍历根节点,以此类推,直至遍历完整个树。

    此外,还有一个命题:给定了二叉树的任何一种遍历序列,都无法唯一确定相应的二叉树。但是如果知道了二叉树的中序遍历序列和任意的另一种遍历序列,就可以唯一地确定二叉树。

例子1:已知二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是(cedba)。

(1)中序遍历:debac

后序遍历:dabec

后序遍历序列的最后一个结点是根结点,所以可知c为根结点。

中序遍历序列的根结点在中间,其左边是左子树,右边是右子树。所以从中序遍历序列中可看出,根结点c只有左子树,没有 右子树。

 

(2)中序遍历:deba

后序遍历:dabe

后序遍历序列的最后一个结点是根结点,所以可知e为c的左子树的根结点。

中序遍历序列的根结点在中间,其左边是左子树,右边是右子树。所以从中序遍历序列中可看出,根结点e的左子结点是d,右子树是ba。

 

(3)中序遍历:ba

后序遍历:ab

由后序遍历序列可知b为e的右子树的根结点。由中序遍历序列中可看出,a为根结点b的右子结点。

树的结构如下:

二叉树的先序,中序,后序遍历的序列_二叉树先序遍历和后序遍历正好相反

class Node:
    def __init__(self, dat, left=None, right=None):
        self.data = dat
        self.left = left
        self.right = right


def rebuild(rear, center):
    if not rear:
        return
    cur = Node(rear[-1])
    index = center.index(rear[-1])
    cur.left = rebuild(rear[:index], center[:index])
    cur.right = rebuild(rear[index:-1], center[index + 1:]) #rear[index:-1]是到倒数第二个数
    return cur


def pre_order(t):
    if t == None:
        return
    print(t.data)
    pre_order(t.left)
    pre_order(t.right)


if __name__ == "__main__":
    rear = ['d','a','b','e','c']
    center = ['d','e','b','a','c']
    t = rebuild(rear, center)
    pre_order(t)

例子2:已知二叉树的前序遍历序列是abdgcefh,中序遍历序列是dgbaechf,它的前序遍历序列是(gdbehfca)。

 

(1)先序遍历:abdgcefh

中序遍历:dgbaechf

先序遍历序列的第一个结点是根结点,所以可知a为根结点。

中序遍历序列的根结点在中间,其左边是左子树,右边是右子树。所以从中序遍历序列中可看出,根结点a的左子树是dgb,右子树是echf。

a的左子树:

(2)先序遍历:bdg

中序遍历:dgb

先序遍历序列的第一个结点是根结点,所以可知b为a的左子树的根结点。

中序遍历序列的根结点在中间,其左边是左子树,右边是右子树。所以从中序遍历序列中可看出,根结点b的左子树是dg,没有右子树。

 

b的左子树:

(3)先序遍历:dg

中序遍历:dg

由先序遍历序列可知d为b的左子树的根结点。

中序遍历序列的根结点在中间,其左边是左子树,右边是右子树。所以从中序遍历序列中可看出,根结点d的右子结点是g。

 

a的右子树:

 

(4)先序遍历:cefh

中序遍历:echf

由先序遍历序列可知c为a的右子树的根结点。

从中序遍历序列中可看出,根结点c的左子结点是e,右子树是hf。

 

 

c的右子树:

(5)先序遍历:fh

中序遍历:hf

由先序遍历序列可知f为c的右子树的根结点。

从中序遍历序列中可看出,根结点f的左子结点是h,没有右子树。

树的结构如下:

二叉树的先序,中序,后序遍历的序列_二叉树先序遍历和后序遍历正好相反

class Node:
    def __init__(self, dat, left=None, right=None):
        self.data = dat
        self.left = left
        self.right = right


def rebuild(pre, center):
    if not pre:
        return
    cur = Node(pre[0])
    index = center.index(pre[0])
    cur.left = rebuild(pre[1:index + 1], center[:index])
    cur.right = rebuild(pre[index + 1:], center[index + 1:])
    return cur


def post_order(t):
    if t == None:
        return
    post_order(t.left)
    post_order(t.right)
    print(t.data)


if __name__ == "__main__":
    pre = ['a','b','d','g','c','e','f','h']
    center = ['d','g','b','a','e','c','h','f']
    t = rebuild(pre, center)
    post_order(t)

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/193816.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • linux(9)find命令详解「建议收藏」

    linux(9)find命令详解「建议收藏」find命令格式:findpath-option[-print][-exec-okcommand]{}\;find命令的参数:path:要查找的目录路径。~表示$HO

  • vim中保存退出_文档没保存就关了怎么恢复

    vim中保存退出_文档没保存就关了怎么恢复保存命令按ESC键跳到命令模式,然后::w保存文件但不退出vi:wfile将修改另外保存到file中,不退出vi:w!强制保存,不推出vi:wq保存文件并退出vi:wq!强制保存文件,并退出viq:不保存文件,退出vi:q!不保存文件,强制退出vi:e!放弃所有修改,从上次保存文件开始再编辑

  • mac版idea2021.5激活码[在线序列号]

    mac版idea2021.5激活码[在线序列号],https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

  • spel表达式注入[通俗易懂]

    spel表达式注入[通俗易懂]使用parseExpression方法将字符串表达式转换为Expression对象;ParserContext接口用于定义字符串表达式是不是模板,及模板开始与结束字符;

  • app测试常用工具(最常用的软件测试工具)

    随着移动互联网的高速发展,App应用非常火,测试工程师也会接触到各种app应用。除了人工测试之外,也可以通过一些测试工具来提高我们的测试效率,以下对于我用过或听过的app测试工具做了一个统一整理,欢迎补充。一、APP自动化测试工具Appium官网:http://appium.io/GitHub地址:https://github.com/appium/appium介绍:Appium是一个开源的、跨平台的自动化测试工具。支持自动化iOS,Android和Window

  • 除了we tool还有哪些免费安全好用的微信群发软件?这两个软件比we tool好用!

    除了we tool还有哪些免费安全好用的微信群发软件?这两个软件比we tool好用!除了wetool还有哪些安全好用的微信群发软件?群发工具是社群运营使用频率最高的工具,无论是给群内推送消息,还是给个人推送消息。按键精灵:点击左侧链接下载按键精灵是一款模拟鼠标键盘动作的软件。通过制作脚本,可以让按键精灵代替您的双手,自动执行一系列鼠标键盘动作。按键精灵免费版简单易用,不需要任何编程知识就可以作出功能强大的脚本。只要您在电脑前用双手可以完成的动作,按键精灵都可以替您完成。按键精灵用途广泛,具有大量脚本资源。简单百宝箱:点击左侧链接下载简单百宝箱是一个绿色和安全的游戏

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号