已知一棵二叉树的前序遍历结果序列是'ABDEGJCFHIK',中序遍历的结果是'DBGJEAHFKIC',请画出这棵二叉树

解答:

根据前序遍历和中序遍历的结果,可以唯一确定一棵二叉树。重建二叉树的步骤如下:

  1. 找到根节点: 前序遍历的第一个节点为根节点,即 'A'。
  2. 在中序遍历中找到根节点: 在中序遍历中找到根节点 'A',并将中序遍历序列划分为左右子树:
    • 左子树:'DBGJE'
    • 右子树:'HFKIC'
  3. 递归重建左右子树:
    • 左子树的前序遍历序列为 'BDEGJ',中序遍历序列为 'DBGJE',递归重建左子树。
    • 右子树的前序遍历序列为 'CFHIK',中序遍历序列为 'HFKIC',递归重建右子树。

最终重建的二叉树如下:

          A
        /   \
       B     C
     /   \   /  \
    D     E F    G
         /     /   \
        J     H     I
        \
         K

注: 这棵二叉树的形态不唯一,但前序和中序遍历的结果是唯一的。

二叉树重建:根据前序遍历和中序遍历结果画出二叉树

原文地址: https://www.cveoy.top/t/topic/mQah 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录