预购基于数组的二叉搜索树

1

您应该考虑递归方法而不是迭代方法。树遍历（preorder，inorder和postorder）很容易用递归完成。

The Wikipedia article on tree traversal有一个伪代码递归算法，但它真的没有太多。由于您将树存储在数组中，因此不会有节点指针，只有索引。

至于如何知道何时到达叶节点，那么它们的索引将超出数组的末尾。

2009-12-01 05:51:11

+0

是啊，我已经看过，超过之前。要预先遍历一个非空的二叉树，请在每个节点处以从根节点开始递归执行以下操作： 1.访问根目录。 2.遍历左侧子树。 3.遍历右侧子树。我该如何知道何时完成遍历数组中的左侧？我需要一个更好的算法。这不应该很难。 =（ – Steller 2009-12-01 05:57:10

+0

该索引超出了数组的末尾，您可以在递归函数中传递数组的大小以及当前根的索引 – 2009-12-01 06:03:04

1

做树遍历通常用递归函数完成，因为这是表达遍历的最自然的方法。

做预购遍历很简单。忽略细节，你有这样的事情：

void do_preorder(Tree t) 
{ 
    // do something with the current tree node 

    if (leftnode(t) not empty) 
     do_preorder(leftnode(t)); 
    if (rightnode(t) not empty) 
     do_preorder(rightnode(t)) 
}

如果你想成为非常棘手，你甚至可以创建一个通用的遍历，允许您选择的味道（预购，按顺序或后序）在运行时：

void do_xorder(Tree t, Flavor f) 
{ 
    if (f == PREORDER) 
     handle_currentnode(t) 

    if (leftnode(t) not empty) 
     do_xorder(leftnode(t), f); 

    if (f == INORDER) 
     handle_currentnode(t) 

    if (rightnode(t) not empty) 
     do_xorder(rightnode(t), f) 

    if (f == POSTORDER) 
     handle_currentnode(t) 

}

来源

2009-12-01 05:56:44

+0

如果绝对不能更改该函数，那么您需要一个帮助器如果问题是你不能改变现有的调用，你可以给父母一个默认值（BST :: displayPreOrder（ostream＆out，int parent = 0）） – 2009-12-01 06:27:02

+0

@R Samuel：如果你添加一个只有一个参数本身具有缺省值，所有对具有单个参数的函数方法的调用都将变得模糊不清：编译器无法确定要调用哪个超载。 – 2009-12-01 07:22:58

+0

@dribeas - 我的建议是不添加新函数，而是更改现有函数。 – 2009-12-01 16:52:59

0

根据你的代码你可以使用（2i + 1）左边和（2i + 2）右边的孩子。

我建议你应该从数组中的索引1开始存储元素，因为你可以在（2 * i）索引处将左边的孩子存储在（2 * i + 1）索引处的右边孩子。

通过检查（2 * i> currSize）是否为真，可以很容易找到左侧子节点的末尾。

http://en.wikipedia.org/wiki/Tree_traversal

看看这个链接，你想上树进行任何遍历...

来源

2009-12-01 06:06:40 Ashish

预购基于数组的二叉搜索树

回答

相关问题