js实现二叉树的前序遍历,中序遍历,后续遍历

JavaScript014

js实现二叉树的前序遍历,中序遍历,后续遍历,第1张

首先创建一棵二叉搜索树,所谓二叉搜索树,则左子树节点的值小于父节点,右子树的值大于父节点

以上就是二叉树前序遍历,中序遍历,后序遍历的所有内容。有问题欢迎指出。

以下面的例题为例进行讲解:

已知一棵二叉树的先序遍历序列和中序遍历序列分别是ABDCEF、BDAECF,求二叉树及后序遍历序列。

分析:先序遍历序列的第一个字符为根结点。对于中序遍历,根结点在中序遍历序列的中间,左边部分是根结点的左子树的中序遍历序列,右边部分是根结点的右子树的中序遍历序列。

先序:ABDCEF --> A BD CEF

中序:BDAECF --> BD A ECF

得出结论:A是树根,A有左子树和右子树,左子树有BD结点,右子树有CEF结点。

先序:BD --> B D

中序:BD --> B D

得出结论:B是左子树的根结点,B无左子树,有右子树(只有D结点)。

先序:CEF --> C E F

中序:ECF --> E C F

得出结论:C是右子树的根结点,C有左子树(只有E结点),有右子树(只有F结点)。

还原二叉树为:

A

B C

D EF

后序遍历序列:DBEFCA