二叉树的打印界面 [英] print boundary of binary tree
问题描述
如何打印二叉树的外部帧
How to print the outside frame of a binary tree.
- 的顺序是从上到下，从左到右，再往下顶
- 打印所有最左边的节点和最右端节点
- 打印所有叶子节点
-
打印其中只有1个叶子的所有节点
- the order is top to down, left to right, then down to top
- print all leftest node and rightest nodes
- print all leaf nodes
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
e.g: the output should be 100, 50, 24, 12, 30, 57, 60, 130, 132, 150
如果我们写了三种不同的功能，打印左节点，叶节点和右节点，它可以很容易解决，但它需要为O（n + 2logn）的时间。
If we write three different functions to print left nodes, leaf nodes and right nodes, it can be easily solved but it takes O(n+2logn) time.
我也在寻找一个O（n）的方法，但条件是，每个节点都应该被访问一次，不想要这种额外的O（2logn）的一部分。
I am also looking for an O(n) approach but condition is that each node should be visited only once, dont want this extra O(2logn) part.
推荐答案
这可以在O（N）来完成。那就是，我们走访了树的每个节点只有一次。 逻辑如下 维护两个变量的离开和右侧，并将其初始化为0。 当曾经有一个由1递归调用左边增量的离开 当曾经有递归调用1骑边增量的右侧
This can be done in O(n) .That is ,we visit each node of the tree only once. Logic is as follows Maintain two variables left and right and initialize them to zero. When ever there is recursive call to left side increment left by 1 When ever there is recursive call to ride side increment right by 1
从根开始，做序遍历，并检查是否右是零，这意味着我们从来没有递归调用正确的。如果是打印的节点，这意味着我们要打印树。如果所有最左边的节点右是非零，他们不被视为边界，所以找叶节点，并打印出来。
Starting from root,do inorder traversal and check whether right is zero, that means we never made recursive call to right. If yes print node, this means we are printing all leftmost nodes of tree .If right is non zero , they are not considered as boundaries,so look for leaf nodes and print them .
在后左子树通话序遍历之后，你泡了根，然后我们做递归调用的右子树。现在检查的叶子节点的第一和打印出来，然后检查是否离开是零，这意味着我们做递归调用向左，所以他们不被视为边界。如果离开为零打印节点，这意味着我们要打印树的所有最右边的节点。
In the Inorder traversal after left sub tree calls are done you bubble up to root and then we do recursive call for right sub tree. Now check for leaves nodes first and print them ,then check whether left is zero, that means we made recursive call to left ,so they are not considered as boundary. If left is zero print node, this means we are printing all rightmost nodes of tree .
在code段是
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;
}
}
}
}
这篇关于二叉树的打印界面的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
