定义
二叉树的左（右）视图即：以从上到下的顺序，输出一颗二叉树每一层最左（右）端的节点，结果就是其左（右）视图。
步骤
- 采用递归的方式，将二叉树的所有节点连带其深度信息存入动态数组（若对二叉树的递归遍历不熟悉，可参考二叉树的创建与遍历 （附C++代码））
- 如左视图，以根——>左——>右的顺序将深度和节点信息添加到动态数组，再进行倒序向前覆盖，即可得到左视图结果。右视图原理与左视图相同
形象理解
- 对于上树来说，若计算其左视图，则递归后存入动态数组的数据为：
0， 6， 1， 5， 2， 0， 2， 2， 3， 3， 1， 7， 2， 9
- 偶数位为该节点的深度，奇数位为该节点的值，以深度为Key值为Value将该动态数组存入字典（map），采用从后向前进行存储。以深度2来说
key:2, value:9先被存入，但由于逆序更新，则key:2的值会最终被key:2, value:0更新，最终的字典中存放的键值对为[key:0, value:6], [key:1, value:5], [key:2, value:0], [key:3, value:3。 - 将字典中的value按照深度递增的顺序输出，即得到左视图
右视图与左视图的遍历顺序向反，但是逆序更新的顺序与原理相同。
C++代码
生成左右视图时用到的逆序覆盖函数
传入的
vector为以左优先或右优先存入的，完整的深度与节点值信息
void reUpdate(vector<float> &result) {
map<int, float> mp; // 逆序更新 for(int i = result.size() - 1; i >0; i -= 2) {
auto pos = mp.find((int)result[i - 1]); // 如果已经存在则更新，若不存在则添加 if(pos != mp.end()) {
pos->second = result[i]; // 更新 } else {
mp.insert(make_pair((int)result[i - 1], result[i])); } } // 清空原result vector<float>().swap(result); // 将mp的结果放入result，并输出结果 for(auto pair : mp) {
result.push_back(pair.second); } } 讯享网
左视图处理函数
讯享网/*二叉树左视图*/ // 递归部分 void preLeftView(Node & node, vector<float> &result, const int deep = 0) {
result.push_back(deep); result.push_back(node.data); if(node.leftChiled != nullptr) {
preLeftView(*(node.leftChiled), result, deep + 1); } if(node.rightChiled != nullptr) {
preLeftView(*(node.rightChiled), result, deep + 1); } } // 左视图生成函数 void leftView(Node & node) {
vector<float> result; preLeftView(node, result); // 逆序更新result reUpdate(result); for(auto x : result) {
cout << x << " "; } }
右视图处理函数
/*二叉树右视图*/ // 递归部分 void preRightView(Node & node, vector<float> &result, const int deep = 0) {
result.push_back(deep); result.push_back(node.data); if(node.rightChiled != nullptr) {
preRightView(*(node.rightChiled), result, deep + 1); } if(node.leftChiled != nullptr) {
preRightView(*(node.leftChiled), result, deep + 1); } } // 右视图生成部分 void rightView(Node & node) {
vector<float> result; preRightView(node, result); // 逆序更新result reUpdate(result); for(auto x : result) {
cout << x << " "; } } 主函数
讯享网int main() {
// 创建二叉树的根及若干节点 Node root(6); Node one(5); Node two(7); Node three(0); Node four(2); Node five(9); Node six(3); // 拼接节点 root.leftChiled = &one; root.rightChiled = &two; one.leftChiled = &three; one.rightChiled = &four; two.rightChiled = &five; four.rightChiled = &six; // 二叉树左视图 cout << "左视图结果" << endl; leftView(root); cout << endl; cout << endl; // 二叉树右视图 cout << "右视图结果" << endl; rightView(root); cout << endl; cout << endl; }
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/122340.html