打印二叉树的边界

Question

如何打印二叉树的外框。

1. the order is top to down, left to right, then down to top
2. print all leftest node and rightest nodes
3. print all leaf nodes

4. print all nodes which only have 1 leaf

            100
           /   \ 
         50     150
        / \      /
      24   57   130
     /  \    \    \
   12   30    60   132
   

例如： 输出结果应该是 100，50，24，12，30，57，60，130，132，150

如果我们编写三个不同的函数来打印左节点、叶子节点和右节点，那么可以很容易地解决，但它需要O(n+2logn)的时间。

我也在寻找一种O(n)的方法，但条件是每个节点只被访问一次，不想要这额外的O(2logn)部分。

- sachin

---

O(n+2logn) 等同于 O(n)。 - interjay

@interjay 是正确的，我们可以跳过常数部分，因为它等于O(n)。 - Shoaib Shaikh

请查看此链接：http://www.geeksforgeeks.org/archives/2755，它的时间和空间复杂度与简单遍历算法相同。 - Shoaib Shaikh

@interjay 我知道 O(n+2logn) 是 O(n)，但我想说的是不同的……算法应该只访问每个节点一次。 - sachin

请查看此链接：http://stackoverflow.com/questions/4932235/binary-trees-count-number-of-leaves。它只会遍历每个节点一次，并使用递归。 - Shoaib Shaikh

Answer 1

这可以在O(n)时间内完成，也就是说我们只访问树的每个节点一次。 其逻辑如下： 维护两个变量 left 和 right 并将它们初始化为零。 每当有向左递归调用时，就将 left 值加1。 每当有向右递归调用时，就将 right 值加1。

从根开始，进行中序遍历并检查 right 是否为零，这意味着我们从未进行过对右子树的递归调用。若是，则打印该节点，这意味着我们正在打印整个树的所有左边界节点。如果 right 不为零，则不将其视为边界，因此请寻找叶节点并打印它们。

在中序遍历中，当左子树的所有调用都已完成后，您会返回到根，然后我们为右子树进行递归调用。现在首先检查叶节点并打印它们，然后检查 left 是否为零，这意味着我们已经对左子树进行了递归调用，因此不将其视为边界。如果 left 为零，则打印该节点，这意味着我们正在打印整个树的所有右边界节点。

代码片段如下：

void btree::cirn(struct node * root,int left,int right)
{



 if(root == NULL)
    return;
if(root)
{

    if(right==0)
    {

        cout<<root->key_value<<endl;
    }

     cirn(root->left,left+1,right);




if(root->left==NULL && root->right==NULL && right>0)
    {

            cout<<root->key_value<<endl;
    }





  cirn(root->right,left,right+1);
  if(left==0)
   {

       if(right!=0)
      {
            cout<<root->key_value<<endl;
       }


   }




}

}

- Imposter

---

我觉得这个问题的答案不会打印出130。 - aandis

Answer 2

算法：

1. 打印左边界
2. 打印叶子节点
3. 打印右边界

---

void getBoundaryTraversal(TreeNode t) {
        System.out.println(t.t);
        traverseLeftBoundary(t.left);
        traverseLeafs(t);
        //traverseLeafs(t.right);
        traverseRightBoundary(t.right);
    }
    private void traverseLeafs(TreeNode t) {
        if (t == null) {
            return;
        }
        if (t.left == null && t.right == null) {
            System.out.println(t.t);
            return;
        }
        traverseLeafs(t.left);
        traverseLeafs(t.right);
    }
    private void traverseLeftBoundary(TreeNode t) {
        if (t != null) {
            if (t.left != null) {
                System.out.println(t.t);
                traverseLeftBoundary(t.left);
            } else if (t.right != null) {
                System.out.println(t.t);
                traverseLeftBoundary(t.right);
            }
        }
    }

    private void traverseRightBoundary(TreeNode t) {
        if (t != null) {
            if (t.right != null) {
                traverseRightBoundary(t.right);
                System.out.println(t.t);
            } else if (t.left != null) {
                traverseLeafs(t.left);
                System.out.println(t.t);
            }
        }
    }

---

TreeNode 的定义：

class TreeNode<T> {

    private T t;
    private TreeNode<T> left;
    private TreeNode<T> right;

    private TreeNode(T t) {
        this.t = t;
    }
}

- Trying

Answer 3

看起来像是一道家庭作业问题，但我需要练习。我已经十年没有使用递归了。

void SimpleBST::print_frame()
{
   if (root != NULL)
   {
      cout << root->data;

      print_frame_helper(root->left, true, false);
      print_frame_helper(root->right, false, true);
      cout << endl;
   }
}

void SimpleBST::print_frame_helper(Node * node, bool left_edge, bool right_edge)
{
   if (node != NULL)
   {
      if (left_edge)
         cout << ", " << node->data;

      print_frame_helper(node->left, left_edge && true, false);

      if ((!left_edge) && (!right_edge))
         if ((node->left == NULL) || (node->right == NULL))
            cout << node->data << ", ";

      print_frame_helper(node->right, false, right_edge && true);

      if (right_edge)
         cout << ", " << node->data;
   }
}

- jlunavtgrad

Answer 4

这是一个简单的解决方案：

def printEdgeNodes(root, pType, cType):
   if root is None:
       return
   if pType == "root" or (pType == "left" and cType == "left") or (pType == "right" and cType == "right"):
        print root.val
   if root.left is None and root.right is None:
       print root.val
   if pType != cType and pType != "root":
       cType = "invalid"
   printEdgeNodes(root.left, cType, "left")

def printEdgeNodes(root):
    return printEdgeNodes(root, "root", "root")

- Clay Schubiner

Answer 5

你可以使用欧拉遍历算法来实现你的树。请参考这个链接：

或者（如果有访问权限）Goodrich等人的书（链接在此处）

希望这能帮到你。

- gmazlami

Answer 6

可以通过先序遍历树来解决问题 - O(n)。
以下是示例代码。源码和一些解释。

Java示例代码：

public class Main {
    /**
     * Prints boundary nodes of a binary tree
     * @param root - the root node
     */
    public static void printOutsidesOfBinaryTree(Node root) {

        Stack<Node> rightSide = new Stack<>();
        Stack<Node> stack = new Stack<>();

        boolean printingLeafs = false;
        Node node = root;

        while (node != null) {

            // add all the non-leaf right nodes left
            // to a separate stack
            if (stack.isEmpty() && printingLeafs && 
                    (node.left != null || node.right != null)) {
                rightSide.push(node);
            }

            if (node.left == null && node.right == null) {
                // leaf node, print it out
                printingLeafs = true;
                IO.write(node.data);
                node = stack.isEmpty() ? null : stack.pop();
            } else {
                if (!printingLeafs) {
                    IO.write(node.data);
                }

                if (node.left != null && node.right != null) {
                    stack.push(node.right);
                }
                node = node.left != null ? node.left : node.right;
            }
        }

        // print out any non-leaf right nodes (if any left)
        while (!rightSide.isEmpty()) {
            IO.write(rightSide.pop().data);
        }
    }
}

- user1712376

Answer 7

你可以递归遍历每个节点并控制何时打印，以下是JavaScript代码片段。

function findBtreeBoundaries(arr, n, leftCount, rightCount) {
  n = n || 0;
  leftCount = leftCount || 0;
  rightCount = rightCount || 0;

  var length = arr.length;
  var leftChildN = 2*n + 1, rightChildN = 2*n + 2;

  if (!arr[n]) {
    return;
  }

  // this is the left side of the tree
  if (rightCount === 0) {
    console.log(arr[n]);
  }

  // select left child node
  findBtreeBoundaries(arr, leftChildN, leftCount + 1, rightCount);

  // this is the bottom side of the tree
  if (leftCount !== 0 && rightCount !== 0) {
    console.log(arr[n]);
  }

  // select right child node
  findBtreeBoundaries(arr, rightChildN, leftCount, rightCount + 1);

  // this is the right side of the tree
  if (leftCount === 0 && rightCount !== 0) {
    console.log(arr[n]);
  }

}

findBtreeBoundaries([100, 50, 150, 24, 57, 130, null, 12, 30, null, 60, null, 132]);

- eguitarz