发布网友 发布时间:2022-05-26 11:44
共2个回答
热心网友 时间:2023-10-15 13:17
得到的树:a为根节点,b为其左孩子,c为右孩子;d为b左孩子,g为d右孩子;e为c左孩子,f为c右孩子,h为f左孩子热心网友 时间:2023-10-15 13:18
中序:左子树--> 根节点--> 右子树
后序:左子树--> 右子树-->根节点
先序:根节点-->左子树-->右子树
由前序遍历结果可知a为根节点,再看中序遍历结果,因为中序遍历顺序是左子树、根、右子树,因此由“中序遍历顺序是dgbaechf”可断定,dgb为该二叉树的左子树中序遍历结果,echf为右子树中序遍历结果。
由前序遍历结果可知,左子树的前序遍历结果是bdg,右子树的前序遍历结果是cefh,因此,可知b为左子树的根,再由“dgb为该二叉树的左子树中序遍历结果”可知,dg为该左子树的左子树的中序遍历结果。
再由dg在前序遍历结果中排列顺序dg可知,d为根,因此由“dg为该左子树的左子树的中序遍历结果”可推出g为d的右孩子。可以完全推断出该二叉树的左子树的结构了。
按照同样方法,可以推断出该二叉树的右子树的结构该二叉树的后序遍历结果是:gdbehfca。
扩展资料:
从根结点开始,假设根结点为第1层,根结点的孩子结点为第2层,如果某一个结点位于第L层,则其孩子结点位于第L+1层。
若对一棵有n个节点的完全二叉树进行顺序编号(1≤i≤n),那么,对于编号为i(i≥1)的节点:
当i=1时,该节点为根,它无双亲节点 。
当i>1时,该节点的双亲节点的编号为i/2。
若2i≤n,则有编号为2的左孩子,否则没有左孩子 。
若2+1≤n,则有编号为2i+1的右孩子,否则没有右孩子。