已知一棵二叉树的前序遍历的结果是ABECDFGHIJ, 中序遍历的结果是EBCDAFHIGJ, 试画出这棵二叉树。

Question

如题所述

Answer 1

前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。

中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。若二叉树为空则结束返回。

因此，A是根结点，B是A的左子树，F是A的右子树。E是B的左子树，C是B的右子树，D是C的右子树。G是F的右子树。H是G的左子树，J是G的右子树。I是H的左子树。

扩展资料：

在前缀和后缀表达式中都不必采用括号或优先级。从左到右或从右到左扫描表达式并采用操作数栈，可以很容易确定操作数和操作符的关系。

若在扫描中遇到一个操作数，把它压入堆栈，若遇到一个操作符，则将其与栈顶的操作数相匹配。把这些操作数推出栈，由操作符执行相应的计算，并将所得结果作为操作数压入堆栈。

当t的高度为n时(右斜二叉树的情况)，通过观察其前序、中序和后序遍历时所使用的递归栈空间即可得到空间复杂性均为O (n)，时间复杂性为O(n)。

Answer 2

前序遍历又称先根遍历,就是按照根,左子树,右子树的顺序,中序遍历就是左子树,根,右子树的顺序,那么按照你这个题:这个二叉树的根应该为A,左子树为EBCD,右子树为FHIGJ,你可以按照这个画出这个二叉树,因为没有特别的要求,所以你可以随意安排左右子树中结点的顺序.本回答被提问者采纳

Answer 3

左一定优先于右 ，所以根的位置有三种。
根 左 右、左 根 右、左 右 根。
分别称为先序遍历、中序遍历、后续遍历，子树也一样，到一个子树就遍历一次，按照遍历顺序写下去就好，尤其注意根特殊对待（只有一个所以只写一个）。
后续遍历是：cbefda

Answer 4

______A
__B_______ F
E__C___________G
_____D______H______J
_______________I

_是为了增加空格