3

我们得到一个二叉搜索树；我们需要找出它的边界。

所以，如果二叉树是 

           10
       /         \
     50           150
    /  \         /   \
  25    75     200    20
 / \           /      / \
15 35        120    155 250

它应该打印出来50 25 15 35 120 155 250 20 150 10。

如果二叉树是

               10
           /         \
         50           150
        /  \         /   
      25    75     200   
     / \   / \    
    15 35 65 30

应该是这样的50 25 15 35 65 30 200 150 10。

如何才能做到这一点？将其推广到二叉树是否会使问题变得更加困难？

通过链接提供的任何帮助也将不胜感激。

PS：请注意，模式不是从根开始，而是从左边开始（在这种情况下）。它也可能以正确开头，但始终以根结尾。

4

4 回答 4

2

您要求的是修改后的深度优先遍历，其中仅在以下情况下打印/返回节点的值：1）节点是叶节点或 2）节点沿着树的“外部路径”，其中“外部路径”定义为

如果您通过从根开始遵循所有左（或右）路径到达该节点，或者该节点是父节点的右（或左）子节点，则该节点是“外部路径”的一部分本身是“外部路径”的一部分，但没有左（或右）孩子。

如果你知道如何编写 DFS，那么这里的修改可以通过在遍历过程中检查一些额外的条件来实现。

于 2010-09-20T17:46:29.483 回答
0 
printBorder(node *n){

   printLeft(n);   O(log n)
   printBottom(n); O(n)
   printRight(n);  O(log n)
}

printBottom(node *n)
{
  int h = treeHeight(n);
  printBottomHelper(n, 0);
}
printBottomHelper(n, h, max)
{
   if(h == max) {
    print n->data
  }
   printBottomHelper(n->left, h+1, max);
   printBottomHelper(n->right, h+1, max);
}
printLeft(node *n)
{
  while(n!= null){
   node *l = n->left;
   l!= null ? print l->data:1
   n =l;
  }
}
于 2011-08-30T15:59:04.163 回答
0

您可以维护两个布尔值来说明要打印的内容。

调用 printBorder(root, true, true) 开始。编辑：最后不打印root，但在开始时，应该是特殊情况。

function printBorder(
Node node, bool printLeft, bool printRight, int height, const int MAX_HEIGHT) {
  if (printLeft || printRight ||
  (node.left == null && node.right == null && height == MAX_HEIGHT)) {
    print node;
  }
  if (node.left) printBorder(node.left, printLeft, printRight && node.right==null)
  if (node.right) printBorder(node.right, printLeft && node.left == null, printRight)
}

其中 MAX_HEIGHT 由 maxdepth(root, 0) 找到；

int maxdepth(Node node, int height) {
  if (node == null) return height;
  return max(maxdepth(node.left, height+1), maxdepth(node.right, height+1))
}
于 2011-12-09T08:13:12.977 回答
0

I'm not sure if it matters whether this a binary tree or not. I think the walk algorithm would be the same either way.

Start with the left subtree, and do a modified breadth first walk that prints a node only if it's the left sibling or an edge. this will print the left siblings until it hits the edges, then print the leaves out.

Then you do a modified depth first walk on the right tree that prints either the right sibling or a leaf. This will print all the right subtree leaves, and then the right siblings.

于 2010-09-20T17:56:20.330 回答