Access二叉树遍历问题 前序遍历是abdgcefh,中序遍历是dgbaechf,怎么推后序遍历?具体步骤啊~~~~~~~~~

来源:百度知道 编辑:UC知道 时间:2024/05/19 20:16:02
急啊~~~~~~~~~~~

一、二叉树遍历原则

先序遍历二叉树:
若二叉树为空,则空操作;
否则
(1) 访问根结点;
(2) 先序遍历左子树;
(3) 先序遍历右子树。
~~~~~~~~~~~~~~~~~~~~~
中序遍历二叉树:
若二叉树为空,则空操作;
否则
(1) 中序遍历左子树;
(2) 访问根结点;
(3) 中序遍历右子树。
~~~~~~~~~~~~~~~~~~~~~
后序遍历二叉树:
若二叉树为空,则空操作;
否则
(1) 后序遍历左子树;
(2) 后序遍历右子树;
(3) 访问根结点。

二、根据题推导
前序遍历是abdgcefh;
中序遍历是dgbaechf;
我们可以知道 a是根节点,
前序遍历是a bdg cefh
根节点 左子树前序遍历 右子树前序遍历
中序遍历是dgb a echf
左子树中序遍历 根节点 右子树中序遍历

我们分析a的左子树结构:
a的左子树前序遍历bdg;
a的左子树中序遍历dgb;
我们可以知道 b是根节点,
前序遍历是b dg 空(无右子树)
根节点 左子树前序遍历 右子树前序遍历
中序遍历是gb b 空(无右子树)
左子树中序遍历 根节点 右子树中序遍历