二进制树从预订和顺序遍历 [英] Binary tree from Preorder and inorder traversal
问题描述
如何获得这些预先/按顺序遍历的树形式:
How can I get the tree form these pre/in order traversal:
前:A,B,D,E,C,F,G,H
in:E,D,B,A,G,F,H,C
Pre: A,B,D,E,C,F,G,H in:E,D,B,A,G,F,H,C
EDITED:MY答案
A
/ \
B C
/ \
D F
/ / \
E G H
推荐答案
编辑:
更正
您没有正确的答案,FGH位于C的左侧。
You don't have the correct answer, FGH is to the left of C.
要验证只是运行两个算法:
To verify just run the two algorithms against it:
PreOrder(node)
if node is null return
Print(node)
PreOrder(node.left)
PreOrder(node.Right)
InOrder(node)
if node is null return
InOrder(node.left)
Print(node)
InOrder(node.Right)
你知道A是根,因为它启动了预订。使用按顺序将节点排列在A的左侧和右侧.B是第二个节点(预订),A(依次排列),依此类推。
You know that A is the root because it starts the pre-order. Use the in-order to arrange nodes to the left and right of A. B is the second node (pre-order), and left of A (in-order), and so on.
由于按顺序排列,您知道F,G,H为C。
You know that F,G,H is left of C because of the in-order arrangement.
基本上,使用preorder选择下一个节点,并查看是否为父节点的左侧或右侧。
Basically, use preorder to select the next node, and in-order to see whether it is left or right of the parent node.
EDIT(2011年4月18日)
EDIT (18 Apr 2011):
为了显示我提供这个伪代码的机制是如何的:
To show how mechanical the process is I offer this pseudo code:
// Add method on binary tree class -- stock standard
method Add(item, comparer)
newNode = new Node(item)
parent = null
// Find suitable parent
currentNode = root
while currentNode is not null
parent = currentNode
if comparer(newNode.Key, currentNode.Key) < 0
currentNode = currentNode.Left
else
currentNode = currentNode.Right
// Add new node to parent
if parent is null
root = newNode
else if comparer(newNode.Value, parent.Value) < 0
parent.Left = newNode
else
parent.Right = newNode
诀窍是使用按顺序确定节点是否添加到其父项的左侧或右侧,例如:
The trick is to use the in-order sequence to determine whether a node is added to the left or right of its parent, for example:
// Client code
// Input arrays
var preOrder = ["A","B","D","E","C","F","G","H"]
var inOrder = ["E","D","B","A","G","F","H","C"]
// A collection associating the Key value with its position in the inOrder array
var inOrderMap = GetInOrderMap(inOrder)
// Build tree from pre-order and in-order sequences
foreach (item in preOrder)
Add(item, fun (l, r) -> inOrderMap[l] - inOrderMap[r])
我正在传递一个羔羊,但是传递比较器的任何等效方法都应该做。
I'm passing a lamba, but any equivalent method for passing a comparer should do.
这篇关于二进制树从预订和顺序遍历的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!