二叉树的遍历问题

| June 12, 2008 10:33 | timmy | Via Original
    以前参加NOI时自己摸索出来的方法。
已知序列画树:
Quotation


已知后序与中序排前序:

    由后序最后一位得知根节点,然后以此元素为基准将序列分为左、右子树,其中左子树的中序为上一层中序的左半部分,其后序为中序中的元素以上一层后序的顺序排列;右子树的中序为上一层中序的右半部分,其后序为中序中的元素以上一层后序的顺序排列。接着再根据此方法分别对每个子树中的中、后序继续分解,最后即可依次写出整棵二叉树的图,再通过描点法写出前序。

已知中序与前序排后序:

    由前序第一位得知根节点,然后以此元素为基准将序列分为左、右子树,其中左子树的中序为上一层中序的左半部分,其前序为中序中的元素以上一层前序的顺序排列;右子树的中序为上一层中序的右半部分,其前序为中序中的元素以上一层前序的顺序排列。接着再根据此方法分别对每个子树中的中、前序继续分解,最后即可依次写出整棵二叉树的图,再通过描点法写出后序。

Program/Code » NOI | Comments(0) | Trackbacks(0) | Reads(146)
Add a comment
 Site URI
 Email
  Password Optional
 Nickname  *  [Register]
               

 
Emots
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
Enable HTML
Enable UBB
Enable Emots
Hidden
Remember