本文主要是介绍哈希(2) - 垂直打印一棵二叉树(使用哈希表实现)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
垂直打印给定的一棵二叉树。下面的例子演示了垂直遍历的顺序。
1/ \2 3/ \ / \4 5 6 7\ \8 9
对这棵树的垂直遍历结果为：
4
2
1 5 6
3 8
7
9
在二叉树系列中，已经讨论过了一种O(n2)的方案。在本篇中，将讨论一种基于哈希表的更优的方法。
首先在水平方向上检测所有节点到root的距离。如果两个node拥有相同的水平距离(Horizontal Distance，简称HD)，则它们在相同的垂直线上。root自身的HD为0，右侧的node的HD递增，即+1，而左侧的node的HD递减，即-1。
例如，上面的那棵树中，Node4的HD为-2， 而Node5和Node6的HD为0，Node7的HD为2。
可以对二叉树做先序遍历。在遍历的过程中，可以递归的计算HD的值。首先指定root HD为0。对于左子树，递归的-1，而对于右子树，递归的+1。
对于每一个HD值，我们在哈希表中维护一个节点链表。当遍历时每获取到一个节点，则将此node插入到哈希表中，利用它的HD做为key。
下面是上述方法的C++实现。
// 垂直的打印一棵二叉树
#include <iostream>
#include <map>
#include <vector>//二叉树的节点
struct Node {int key;Node* left;Node* right;
};//创建一个新的节点
Node* newNode(int key) {Node* node = new Node;node->key = key;node->left = node->right = NULL;return node;
}// 将垂直排序的节点存入哈希表m中；
// 参数distance表示当前节点到root的HD距离。初始值为0
void getVerticalOrder(Node* root, int distance, std::map<int, std::vector<int> >& result) {// 检测特定情况if (root == NULL)return;// 将当前node存入map中result[distance].push_back(root->key);// 递归存储左子树。 注意：距离值是递减的getVerticalOrder(root->left, distance - 1, result);// 递归存储右子树。注意：距离值是递增的getVerticalOrder(root->right, distance + 1, result);
}// 按照垂直顺序打印二叉树的节点
void printVerticalOrder(Node* root) {//map存储所有垂直排序的节点std::map <int, std::vector<int> > result;int distance = 0;getVerticalOrder(root, distance, result);//遍历map，进行打印std::map< int, std::vector<int> > ::iterator it;for (it = result.begin(); it != result.end(); it++) {for (unsigned int i = 0; i < it->second.size(); ++i)std::cout << it->second[i] << " ";std::cout << std::endl;}
}Node* generateBST() {/* 构建二叉树树1/ \2 3/ \ / \4 5 6 7\ \8 9*/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);return root;
}int main() {Node* root = generateBST();std::cout << "Vertical order traversal is:" << std::endl;printVerticalOrder(root);return 0;
}运行结果：
Vertical order traversal is:
4
2
1 5 6
3 8
7
9
时间复杂度： 假设我们有一个比较好的哈希函数，能实现O(1)时间进行插入和检索，则基于哈希的这个方案的时间复杂度可以认为是O(n)。上述代码中，使用了STL map。而STL map主要就是使用自平衡二叉树来实现的，其所有操作都是O(Logn)时间。因此，上述方案的时间复杂度可以认为是O(nLogn).
这篇关于哈希(2) - 垂直打印一棵二叉树(使用哈希表实现)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
