给定一棵二叉树，垂直打印。下面的示例演示了垂直顺序遍历。
null
1 / 2 3 / / 4 5 6 7 8 9 The output of print this tree vertically will be:421 5 63 879
![图片[1]-按垂直顺序打印二叉树|集3（使用水平顺序遍历）-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/uploads/geeks_print-binary-tree-in-vertical-order.png)
我们在下面的帖子中讨论了一种有效的方法。 按垂直顺序打印二叉树|集2（基于Hashmap的方法） 上述解决方案使用前序遍历和Hashmap根据水平距离存储节点。由于上述方法使用了前序遍历，垂直线中的节点可能不会按照它们在树中出现的顺序打印。例如，上面的解决方案在下面的树中打印9之前的12。看见 这 作为一个样本运行。
1 / 2 3 / / 4 5 6 7 / 8 10 9 11 12
如果我们使用 水平顺序遍历 ，我们可以确保，如果像12这样的节点位于同一垂直线的下方，它将在像9这样的节点位于垂直线的上方之后打印。
1. To maintain a hash for the branch of each node.2. Traverse the tree in level order fashion.3. In level order traversal, maintain a queue which holds, node and its vertical branch. * pop from queue. * add this node's data in vector corresponding to its branch in the hash. * if this node hash left child, insert in the queue, left with branch - 1. * if this node hash right child, insert in the queue, right with branch + 1.
C++
// C++ program for printing vertical order // of a given binary tree using BFS. #include <bits/stdc++.h> using namespace std; // Structure for a binary tree node struct Node { int key; Node *left, *right; }; // A utility function to create a new node Node* newNode( int key) { Node* node = new Node; node->key = key; node->left = node->right = NULL; return node; } // The main function to print vertical order of a // binary tree with given root void printVerticalOrder(Node* root) { // Base case if (!root) return ; // Create a map and store vertical order in // map using function getVerticalOrder() map< int , vector< int > > m; int hd = 0; // Create queue to do level order traversal. // Every item of queue contains node and // horizontal distance. queue<pair<Node*, int > > que; que.push(make_pair(root, hd)); while (!que.empty()) { // pop from queue front pair<Node*, int > temp = que.front(); que.pop(); hd = temp.second; Node* node = temp.first; // insert this node's data in vector of hash m[hd].push_back(node->key); if (node->left != NULL) que.push(make_pair(node->left, hd - 1)); if (node->right != NULL) que.push(make_pair(node->right, hd + 1)); } // Traverse the map and print nodes at // every horizontal distance (hd) map< int , vector< int > >::iterator it; for (it = m.begin(); it != m.end(); it++) { for ( int i = 0; i < it->second.size(); ++i) cout << it->second[i] << " " ; cout << endl; } } // Driver program to test above functions int main() { 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); root->right->right->left = newNode(10); root->right->right->left->right = newNode(11); root->right->right->left->right->right = newNode(12); cout << "Vertical order traversal is " ; printVerticalOrder(root); return 0; } |
JAVA
import java.util.ArrayList; import java.util.LinkedList; import java.util.Map; import java.util.Queue; import java.util.TreeMap; class Node { int key; Node left, right; // A utility function to create a new node Node newNode( int key) { Node node = new Node(); node.key = key; node.left = node.right = null ; return node; } } class Qobj { int hd; Node node; Qobj( int hd, Node node) { this .hd = hd; this .node = node; } } public class VerticalOrderTraversal { // The main function to print vertical order of a // binary tree with given root static void printVerticalOrder(Node root) { // Base case if (root == null ) return ; // Create a map and store vertical order in // map using function getVerticalOrder() TreeMap<Integer, ArrayList<Integer> > m = new TreeMap<>(); int hd = 0 ; // Create queue to do level order traversal. // Every item of queue contains node and // horizontal distance. Queue<Qobj> que = new LinkedList<Qobj>(); que.add( new Qobj( 0 , root)); while (!que.isEmpty()) { // pop from queue front Qobj temp = que.poll(); hd = temp.hd; Node node = temp.node; // insert this node's data in array of hash if (m.containsKey(hd)) { m.get(hd).add(node.key); } else { ArrayList<Integer> al = new ArrayList<>(); al.add(node.key); m.put(hd, al); } if (node.left != null ) que.add( new Qobj(hd - 1 , node.left)); if (node.right != null ) que.add( new Qobj(hd + 1 , node.right)); } // Traverse the map and print nodes at // every horizontal distance (hd) for (Map.Entry<Integer, ArrayList<Integer> > entry : m.entrySet()) { ArrayList<Integer> al = entry.getValue(); for (Integer i : al) System.out.print(i + " " ); System.out.println(); } } // Driver program to test above functions public static void main(String ar[]) { Node n = new Node(); Node root; root = n.newNode( 1 ); root.left = n.newNode( 2 ); root.right = n.newNode( 3 ); root.left.left = n.newNode( 4 ); root.left.right = n.newNode( 5 ); root.right.left = n.newNode( 6 ); root.right.right = n.newNode( 7 ); root.right.left.right = n.newNode( 8 ); root.right.right.right = n.newNode( 9 ); root.right.right.left = n.newNode( 10 ); root.right.right.left.right = n.newNode( 11 ); root.right.right.left.right.right = n.newNode( 12 ); System.out.println( "Vertical order traversal is " ); printVerticalOrder(root); } } |
Python3
# python3 Program to print zigzag traversal of binary tree import collections # Binary tree node class Node: # Constructor to create a new node def __init__( self , data): self .data = data self .left = self .right = None # function to print vertical order traversal of binary tree def verticalTraverse(root): # Base case if root is None : return # Create empty queue for level order traversal queue = [] # create a map to store nodes at a particular # horizontal distance m = {} # map to store horizontal distance of nodes hd_node = {} # enqueue root queue.append(root) # store the horizontal distance of root as 0 hd_node[root] = 0 m[ 0 ] = [root.data] # loop will run while queue is not empty while len (queue) > 0 : # dequeue node from queue temp = queue.pop( 0 ) if temp.left: # Enqueue left child queue.append(temp.left) # Store the horizontal distance of left node # hd(left child) = hd(parent) -1 hd_node[temp.left] = hd_node[temp] - 1 hd = hd_node[temp.left] if m.get(hd) is None : m[hd] = [] m[hd].append(temp.left.data) if temp.right: # Enqueue right child queue.append(temp.right) # store the horizontal distance of right child # hd(right child) = hd(parent) + 1 hd_node[temp.right] = hd_node[temp] + 1 hd = hd_node[temp.right] if m.get(hd) is None : m[hd] = [] m[hd].append(temp.right.data) # Sort the map according to horizontal distance sorted_m = collections.OrderedDict( sorted (m.items())) # Traverse the sorted map and print nodes at each horizontal distance for i in sorted_m.values(): for j in i: print (j, " " , end = "") print () # Driver program to check above function """ Constructed binary tree is 1 / 2 3 / / 4 5 6 7 / 8 10 9 11 12 """ 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.left = Node( 10 ) root.right.right.right = Node( 9 ) root.right.right.left.right = Node( 11 ) root.right.right.left.right.right = Node( 12 ) print ( "Vertical order traversal is " ) verticalTraverse(root) # This code is contributed by Shweta Singh |
C#
// C# program to implement the // above approach using System; using System.Collections; using System.Collections.Generic; class Node{ public int key; public Node left, right; // A utility function to // create a new node public Node newNode( int key) { Node node = new Node(); node.key = key; node.left = node.right = null ; return node; } } class Qobj{ public int hd; public Node node; public Qobj( int hd, Node node) { this .hd = hd; this .node = node; } } class VerticalOrderTraversal{ // The main function to print // vertical order of a binary // tree with given root static void printVerticalOrder(Node root) { // Base case if (root == null ) return ; // Create a map and store vertical // order in map using function // getVerticalOrder() SortedDictionary< int , ArrayList> m = new SortedDictionary< int , ArrayList>(); int hd = 0; // Create queue to do level order // traversal. Every item of queue // contains node and horizontal // distance. Queue que = new Queue(); que.Enqueue( new Qobj(0, root)); while (que.Count != 0) { // pop from queue front Qobj temp = (Qobj)que.Dequeue(); hd = temp.hd; Node node = temp.node; // insert this node's data in // array of hash if (m.ContainsKey(hd)) { m[hd].Add(node.key); } else { ArrayList al = new ArrayList(); al.Add(node.key); m[hd] = al; } if (node.left != null ) que.Enqueue( new Qobj(hd - 1, node.left)); if (node.right != null ) que.Enqueue( new Qobj(hd + 1, node.right)); } // Traverse the map and print // nodes at every horizontal // distance (hd) foreach (KeyValuePair< int , ArrayList> entry in m) { ArrayList al = (ArrayList)entry.Value; foreach ( int i in al) Console.Write(i + " " ); Console.Write( "" ); } } // Driver code public static void Main( string []arr) { Node n = new Node(); Node root; root = n.newNode(1); root.left = n.newNode(2); root.right = n.newNode(3); root.left.left = n.newNode(4); root.left.right = n.newNode(5); root.right.left = n.newNode(6); root.right.right = n.newNode(7); root.right.left.right = n.newNode(8); root.right.right.right = n.newNode(9); root.right.right.left = n.newNode(10); root.right.right.left.right = n.newNode(11); root.right.right.left.right.right = n.newNode(12); Console.Write( "Vertical order traversal is " ); printVerticalOrder(root); } } // This code is contributed by Rutvik_56 |
Javascript
<script> // Javascript program to implement the // above approach class Node { constructor() { this .key = 0; this .left = null ; this .right = null ; } } // A utility function to // create a new node function newNode(key) { var node = new Node(); node.key = key; node.left = node.right = null ; return node; } class Qobj{ constructor(hd, node) { this .hd = hd; this .node = node; } } // The main function to print // vertical order of a binary // tree with given root function printVerticalOrder(root) { // Base case if (root == null ) return ; // Create a map and store vertical // order in map using function // getVerticalOrder() var m = new Map(); var hd = 0; // Create queue to do level order // traversal. Every item of queue // contains node and horizontal // distance. var que = []; que.push( new Qobj(0, root)); while (que.length != 0) { // pop from queue front var temp = que[0]; que.shift(); hd = temp.hd; var node = temp.node; // insert this node's data in // array of hash if (m.has(hd)) { var al = m.get(hd); al.push(node.key); m.set(hd, al); } else { var al = []; al.push(node.key); m.set(hd, al); } if (node.left != null ) que.push( new Qobj(hd - 1, node.left)); if (node.right != null ) que.push( new Qobj(hd + 1, node.right)); } // Traverse the map and print // nodes at every horizontal // distance (hd) [...m].sort((a,b)=>a[0]-b[0]).forEach(tmp => { var al = tmp[1]; for ( var i of al) document.write(i + " " ); document.write( "<br>" ); }); } // Driver code var 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); root.right.right.left = newNode(10); root.right.right.left.right = newNode(11); root.right.right.left.right.right = newNode(12); document.write( "Vertical order traversal is <br>" ); printVerticalOrder(root); // This code is contributed by famously. </script> |
输出：
Vertical order traversal is 4 2 1 5 6 3 8 10 7 11 9 12
上述实现的时间复杂度为O（n logn）。注意，上面的实现使用了一个映射，该映射是使用自平衡BST实现的。 我们可以使用无序映射将时间复杂度降低到O（n）。要按所需顺序打印节点，可以使用两个变量来表示最小和最大水平距离。我们可以简单地从最小水平距离迭代到最大水平距离，并从地图中得到相应的值。所以是O（n）
辅助空间：O（n）
本文由 萨希尔·查布拉（阿克库） .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
