我们知道先序遍历、中序遍历和后序遍历。有哪些算法可以重构二叉搜索树?
由于这是BST,所以可以从先序遍历
或后序遍历
中的中序遍历
进行排序<1>。实际上,只需要其中一种遍历方式即可....
<1>如果您知道比较函数是什么
从先序遍历
和中序遍历
构建二叉树
BT createBT(int* preOrder, int* inOrder, int len)
{
int i;
BT tree;
if(len <= 0)
return NULL;
tree = new BTNode;
t->data = *preOrder;
for(i = 0; i < len; i++)
if(*(inOrder + i) == *preOrder)
break;
tree->left = createBT(preOrder + 1, inOrder, i);
tree->right = createBT(preOrder + i + 1, inOrder + i + 1, len - i - 1);
return tree;
}
这样做的原理是:
在先序遍历中,第一个节点是根节点。在中序遍历中找到根节点,然后将树分为左子树和右子树。递归执行此操作。
后序遍历
和中序遍历
同理。
这里是一个 Ruby 递归解决方案
def rebuild(preorder, inorder)
root = preorder.first
root_inorder = inorder.index root
return root unless root_inorder
root.left = rebuild(preorder[1, root_inorder], inorder[0...root_inorder])
root.right = rebuild(preorder[root_inorder+1..-1], inorder[root_inorder+1..-1])
root
end
还有一个例子
class Node
attr_reader :val
attr_accessor :left, :right
def initialize(val)
@val = val
end
def ==(node)
node.val == val
end
def inspect
"val: #{val}, left: #{left && left.val || "-"}, right: #{right && right.val || "-"}"
end
end
inorder = [4, 7, 2, 5, 1, 3, 8, 6, 9].map{|v| Node.new v }
preorder = [1, 2, 4, 7, 5, 3, 6, 8, 9].map{|v| Node.new v }
tree = rebuild(preorder, inorder)
tree
# val: 1, left: 2, right: 3
tree.left
# val: 2, left: 4, right: 5
tree.left.left
# val: 4, left: -, right: 7
struct node* buildTree(char in[],char pre[], int inStrt, int inEnd,int preIndex){
// start index > end index..base condition return NULL.
if(inStrt > inEnd)
return NULL;
// build the current node with the data at pre[preIndex].
struct node *tNode = newNode(pre[preIndex]);
// if all nodes are constructed return.
if(inStrt == inEnd)
return tNode;
// Else find the index of this node in Inorder traversal
int inIndex = search(in, inStrt, inEnd, tNode->data);
// Using index in Inorder traversal, construct left and right subtress
tNode->left = buildTree(in, pre, inStrt, inIndex-1,preIndex+1);
tNode->right = buildTree(in, pre, inIndex+1, inEnd,preIndex+inIndex+1);
return tNode;
}
我个人觉得Dante的回答有点难以理解。我按照解决方案的步骤进行了操作,发现它与此处发布的一个解决方案相似 http://geeksforgeeks.org/?p=6633
时间复杂度为O(N^2)。
这里还有另一种使用后序遍历构建树的方法:http://www.technicallyidle.com/2011/02/15/build-binary-search-tree-using-post-order-traversal-trace/
希望这可以帮到你。
preOrder + i + 1
开始? - brainydexter