algorithm - 打印二叉树的边界

Question

如何打印二叉树的外框。

1. 顺序是从上到下，从左到右，再从下到上
2. 打印所有最左节点和最右节点
3. 打印所有叶节点

4. 打印所有只有一片叶子的节点

            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) 部分。

Answer 1

这可以在 O(n) 中完成。也就是说，我们只访问树的每个节点一次。逻辑如下维护两个变量left 和right 并将它们初始化为零。每当递归调用左侧增量 left 1每当递归调用骑乘侧增量 right 1

从根开始，中序遍历，检查right是否为零，即没有对right进行递归调用。如果是，则打印节点，这意味着我们正在打印树的所有最左边的节点。如果 right 不为零，则它们不被视为边界，因此查找叶节点并打印它们。

在左子树调用完成后的中序遍历中，您冒泡到根，然后我们对右子树进行递归调用。现在先检查叶子节点并打印它们，然后检查 left 是否为零，这意味着我们对 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;
       }


   }




}