跳动百科

二叉树结点概念(二叉树结点)

傅翰琛
导读 大家好,我是小跳,我来为大家解答以上问题。二叉树结点概念,二叉树结点很多人还不知道,现在让我们一起来看看吧!1、首先我们知道,前序...

大家好,我是小跳,我来为大家解答以上问题。二叉树结点概念,二叉树结点很多人还不知道,现在让我们一起来看看吧!

1、首先我们知道,前序遍历的规则是:根结点→左子结点→右子结点 中序遍历是:左子结点→根结点→右子结点 后序遍历是:左子结点→右子结点→根结点 那么,对于一棵二叉树,前序遍历的第一个结点一定是这棵树的根结点,即根结点是a。

2、 在中序遍历的顺序dgbaechf中,以a分成左、右两边,左边是dgb,右边是echf。

3、 所以,这棵树现在可以确定如下: a / dgb echf 接下来再分别对左子树和右子树进行类似的操作。

4、 对于左子树dgb来说,在前序遍历abdgcefh中找到bdg,证明这子树的根是b,那么现在可以确定的树结构如下: a / b echf / dg 再看dg,前序遍历中的顺序为dg,所以d是dg这部分子树的根,那么又因为中序遍历的dg顺序也是dg,所以g是右子结点。

5、 即: a / b echf / d g 现在看echf这部分子树,前序中顺序是cefh,所以子树根结点是c,那么左子结点是e,右子树是hf: 得到: a / b c / / d e hf g 最后只剩下hf部分了,前序遍历中是fh,所以根是f,那么h就是左子结点。

6、 现在得到了整棵树: a / b c / / d e f / g h 对这棵树再进行后序遍历就行了,结果就是:gdbehfca。

本文到此讲解完毕了,希望对大家有帮助。