algorithm - 仅从前序或后序遍历计算 BST 的内部路径长度

Question

你好 StackOverflow 社区！

我试图弄清楚如何在不构造树的情况下仅在给定前序或后序遍历（它不应该有太大区别）的情况下计算 BST 的内部路径长度；也就是说，我只想使用上面提到的遍历之一。这对你们大多数人来说可能是一个简单的答案，但你可能已经认为我对树木很陌生。

好吧，任何想法都会受到赞赏和感谢。

Answer 1

在http://geeksforgeeks.org/?p=6633有一个页面讨论了从其前序遍历和中序遍历构建一棵树。在这里，由于您的树是搜索树，因此您可以隐式进行中序遍历（使用键的排序顺序）。您可以使用类似于该站点的递归算法来计算每个树节点的级别（无需构建树），然后将级别加在一起以获得内部路径长度。该算法可能不是最有效的，因为它会搜索遍历以找到每个节点的正确子节点，但它应该可以工作。这是我对如何进行单遍算法的最佳猜测（假设所有键都是不同的）：

int internal_path_length(key_iter& cur_node, key_iter end, int level, key max_key) {
  if (cur_node == end) return 0;
  key cur_key = *cur_node;
  if (cur_key > max_key) return 0;
  ++cur_node;
  int len1 = internal_path_length(cur_node, end, level + 1, cur_key);
  int len2 = internal_path_length(cur_node, end, level + 1, max_key);
  return len1 + len2 + level;
}

从...开始：

key_iter i = preorder.begin();
internal_path_length(i, preorder.end(), 0, mk);

wheremk大于树中可能的最大键。

Answer 2

由于它是 BST，因此我们隐含地对树进行了中序遍历（元素的排序列表）。

我们可以从前序或后序遍历创建一个唯一的树 Pre 将是 [R，元素列表小于 R ，元素列表大于 R] Post 将是 [元素列表小于 R ，元素列表大于 R， [R]

伪代码将如下所示。

findIPLPreOrder(poArray,startIndex,endIndex, height) {
     if(startIndex==endIndex){
          retrn height;
     }
     m=findIndexOfEndofLeftSubTree(poArray,start,end);
     return findIPLPreOrder(poArray,start+1,m,height + 1) + findIPLPreOrder(poArray,m+1,end,height + 1);     
}

findIndexOfEndofLeftSubTree(poArray,start,end){
  R=poArray[start]
  for(i=start+1;i<=end;i++){
     if(R < poArray[i]){
         return i-1;
       }
  }
}

Answer 3

如果我理解你的问题，那可能是不可能的。考虑两棵树

   A         A
  / \        |
 B   C       B
             |
             C

它们具有相同的前序遍历 (ABC) 但内部路径长度不同（2 和 3）。