原文:
给定一棵二叉树，垂直打印。以下示例说明了垂直顺序遍历。
1
/ \
2 3
/ \ / \
4 5 6 7
\ \
8 9
the output of print this tree vertically will be:
4
2
1 5 6
3 8
7
9
这个想法是遍历一次树，得到相对于根的最小和最大水平距离。对于上面显示的树，最小距离为-2(对于值为 4 的节点)，最大距离为 3(对于值为 9 的节点)。 一旦我们有了离根的最大和最小距离，我们就在离根最小到最大的距离上迭代每条垂直线，对于每条垂直线遍历树并打印位于该垂直线上的节点。 算法:
// min --> minimum horizontal distance from root
// max --> maximum horizontal distance from root
// hd --> horizontal distance of current node from root
findminmax(tree, min, max, hd)
if tree is null then return;
if hd is less than min then
*min = hd;
else if hd is greater than max then
*max = hd;
findminmax(tree->left, min, max, hd-1);
findminmax(tree->right, min, max, hd 1);
printverticalline(tree, line_no, hd)
if tree is null then return;
if hd is equal to line_no, then
print(tree->data);
printverticalline(tree->left, line_no, hd-1);
printverticalline(tree->right, line_no, hd 1);
实现: 以下是上述算法的实现。
c
#include
using namespace std;
// a node of binary tree
struct node
{
int data;
struct node *left, *right;
};
// a utility function to create a new binary tree node
node* newnode(int data)
{
node *temp = new node;
temp->data = data;
temp->left = temp->right = null;
return temp;
}
// a utility function to find min and max distances with respect
// to root.
void findminmax(node *node, int *min, int *max, int hd)
{
// base case
if (node == null) return;
// update min and max
if (hd < *min) *min = hd;
else if (hd > *max) *max = hd;
// recur for left and right subtrees
findminmax(node->left, min, max, hd-1);
findminmax(node->right, min, max, hd 1);
}
// a utility function to print all nodes on a given line_no.
// hd is horizontal distance of current node with respect to root.
void printverticalline(node *node, int line_no, int hd)
{
// base case
if (node == null) return;
// if this node is on the given line number
if (hd == line_no)
cout << node->data << " ";
// recur for left and right subtrees
printverticalline(node->left, line_no, hd-1);
printverticalline(node->right, line_no, hd 1);
}
// the main function that prints a given binary tree in
// vertical order
void verticalorder(node *root)
{
// find min and max distances with resepect to root
int min = 0, max = 0;
findminmax(root, &min, &max, 0);
// iterate through all possible vertical lines starting
// from the leftmost line and print nodes line by line
for (int line_no = min; line_no <= max; line_no )
{
printverticalline(root, line_no, 0);
cout << endl;
}
}
// driver program to test above functions
int main()
{
// create binary tree shown in above figure
node *root = newnode(1);
root->left = newnode(2);
root->right = newnode(3);
root->left->left = newnode(4);
root->left->right = newnode(5);
root->right->left = newnode(6);
root->right->right = newnode(7);
root->right->left->right = newnode(8);
root->right->right->right = newnode(9);
cout << "vertical order traversal is \n";
verticalorder(root);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java program to print binary tree in reverse order
// a binary tree node
class node
{
int data;
node left, right;
node(int item)
{
data = item;
left = right = null;
}
}
class values
{
int max, min;
}
class binarytree
{
node root;
values val = new values();
// a utility function to find min and max distances with respect
// to root.
void findminmax(node node, values min, values max, int hd)
{
// base case
if (node == null)
return;
// update min and max
if (hd < min.min)
min.min = hd;
else if (hd > max.max)
max.max = hd;
// recur for left and right subtrees
findminmax(node.left, min, max, hd - 1);
findminmax(node.right, min, max, hd 1);
}
// a utility function to print all nodes on a given line_no.
// hd is horizontal distance of current node with respect to root.
void printverticalline(node node, int line_no, int hd)
{
// base case
if (node == null)
return;
// if this node is on the given line number
if (hd == line_no)
system.out.print(node.data " ");
// recur for left and right subtrees
printverticalline(node.left, line_no, hd - 1);
printverticalline(node.right, line_no, hd 1);
}
// the main function that prints a given binary tree in
// vertical order
void verticalorder(node node)
{
// find min and max distances with resepect to root
findminmax(node, val, val, 0);
// iterate through all possible vertical lines starting
// from the leftmost line and print nodes line by line
for (int line_no = val.min; line_no <= val.max; line_no )
{
printverticalline(node, line_no, 0);
system.out.println("");
}
}
// driver program to test the above functions
public static void main(string args[])
{
binarytree tree = new binarytree();
/* let us construct the tree shown in above diagram */
tree.root = new node(1);
tree.root.left = new node(2);
tree.root.right = new node(3);
tree.root.left.left = new node(4);
tree.root.left.right = new node(5);
tree.root.right.left = new node(6);
tree.root.right.right = new node(7);
tree.root.right.left.right = new node(8);
tree.root.right.right.right = new node(9);
system.out.println("vertical order traversal is :");
tree.verticalorder(tree.root);
}
}
// this code has been contributed by mayank jaiswal
计算机编程语言
# program to print binary tree in vertical order
# a binary tree
class node:
# constructor to create a new node
def __init__(self, key):
self.data = key
self.left = none
self.right = none
# a utility function to find min and max distances with
# respect to root
def findminmax(node, minimum, maximum, hd):
# base case
if node is none:
return
# update min and max
if hd < minimum[0] :
minimum[0] = hd
elif hd > maximum[0]:
maximum[0] = hd
# recur for left and right subtrees
findminmax(node.left, minimum, maximum, hd-1)
findminmax(node.right, minimum, maximum, hd 1)
# a utility function to print all nodes on a given line_no
# hd is horizontal distance of current node with respect to root
def printverticalline(node, line_no, hd):
# base case
if node is none:
return
# if this node is on the given line number
if hd == line_no:
print node.data,
# recur for left and right subtrees
printverticalline(node.left, line_no, hd-1)
printverticalline(node.right, line_no, hd 1)
def verticalorder(root):
# find min and max distances with respect to root
minimum = [0]
maximum = [0]
findminmax(root, minimum, maximum, 0)
# iterate through all possible lines starting
# from the leftmost line and print nodes line by line
for line_no in range(minimum[0], maximum[0] 1):
printverticalline(root, line_no, 0)
print
# driver program to test above function
root = node(1)
root.left = node(2)
root.right = node(3)
root.left.left = node(4)
root.left.right = node(5)
root.right.left = node(6)
root.right.right = node(7)
root.right.left.right = node(8)
root.right.right.right = node(9)
print "vertical order traversal is"
verticalorder(root)
# this code is contributed by nikhil kumar singh(nickzuck_007)
c
// c# program to print binary tree in reverse order
using system;
// a binary tree node
public class node
{
public int data;
public node left, right;
public node(int item)
{
data = item;
left = right = null;
}
}
class values
{
public int max, min;
}
public class binarytree
{
node root;
values val = new values();
// a utility function to find min and
// max distances with respect to root.
void findminmax(node node, values min,
values max, int hd)
{
// base case
if (node == null)
return;
// update min and max
if (hd < min.min)
min.min = hd;
else if (hd > max.max)
max.max = hd;
// recur for left and right subtrees
findminmax(node.left, min, max, hd - 1);
findminmax(node.right, min, max, hd 1);
}
// a utility function to print
// all nodes on a given line_no.
// hd is horizontal distance of
// current node with respect to root.
void printverticalline(node node,
int line_no, int hd)
{
// base case
if (node == null)
return;
// if this node is on the given line number
if (hd == line_no)
console.write(node.data " ");
// recur for left and right subtrees
printverticalline(node.left, line_no, hd - 1);
printverticalline(node.right, line_no, hd 1);
}
// the main function that prints
// a given binary tree in vertical order
void verticalorder(node node)
{
// find min and max distances with resepect to root
findminmax(node, val, val, 0);
// iterate through all possible
// vertical lines starting from the
// leftmost line and print nodes line by line
for (int line_no = val.min; line_no <= val.max; line_no )
{
printverticalline(node, line_no, 0);
console.writeline("");
}
}
// driver code
public static void main()
{
binarytree tree = new binarytree();
/* let us construct the tree
shown in above diagram */
tree.root = new node(1);
tree.root.left = new node(2);
tree.root.right = new node(3);
tree.root.left.left = new node(4);
tree.root.left.right = new node(5);
tree.root.right.left = new node(6);
tree.root.right.right = new node(7);
tree.root.right.left.right = new node(8);
tree.root.right.right.right = new node(9);
console.writeline("vertical order traversal is :");
tree.verticalorder(tree.root);
}
}
/* this code is contributed princiraj1992 */
java 描述语言
输出:
vertical order traversal is
4
2
1 5 6
3 8
7
9
时间复杂度:上述算法的时间复杂度为 o(wn)，其中 w 为二叉树的宽度，n 为二叉树中的节点数。在最坏的情况下，w 的值可以是 o(n)(例如考虑一个完整的树)，时间复杂度可以变成 o(n 2 )。 这个问题可以使用帖子中讨论的技术更有效地解决。我们将很快讨论完整的算法和实现更有效的方法。 本文由 shalki agarwal* 供稿。如果您发现任何不正确的地方，请写评论，或者您想分享更多关于上面讨论的主题的信息
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
