二叉树的个人总结

由于本人目前在找算法工程师方向的工作，在面试过程中，经常会被问到非递归方法遍历的二叉树，二叉搜索树，二叉树的高度等一系列方法，本人写了c++代码供自己复习使用，希望也能够帮到各位小伙伴们

代码块

// // tree.cpp // myTest // // Created by lixiaoxue on 2017/8/28. // Copyright © 2017年 lixiaoxue. All rights reserved. // #include <stdio.h> #include <iostream> #include <queue> #include <vector> #include <algorithm> #include <math.h> #include <numeric> #include <stack> using namespace std; struct TreeNode{ public: int val; TreeNode* left; TreeNode* right; TreeNode(int a): val(a),left(nullptr),right(nullptr){} }; //递归先序遍历 void pre_order(vector<int>& out,TreeNode* root){ if(!root) return; out.push_back(root->val); pre_order(out, root->left); pre_order(out, root->right); } //递归中序遍历 void mid_order(vector<int>& out,TreeNode* root){ if(!root) return; mid_order(out, root->left); out.push_back(root->val); mid_order(out, root->right); } //递归的后序遍历 void after_order(vector<int>& out,TreeNode* root){ if(!root) return; after_order(out, root->left); after_order(out, root->right); out.push_back(root->val); } //非递归先序遍历2 vector<int> pre_order_non2(TreeNode* root){ if(!root) return vector<int>(); vector<int> number; stack<TreeNode*> s; TreeNode* cur = root; while ((!s.empty()) || !cur) { while (cur) { number.push_back(cur->val); s.push(cur); cur = cur->left; } if(!s.empty()){ cur = s.top()->right; s.pop(); } } return number; } //先序遍历3 vector<int> pre_order_non3(TreeNode* root){ if(!root) return vector<int>(); stack<TreeNode*> s; vector<int> number; while (root) { number.push_back(root->val); s.push(root); root = root->left; } while (!s.empty()) { TreeNode* temp = s.top()->right; s.pop(); while (temp) { number.push_back(temp->val); s.push(temp); temp = temp->left; } } return number; } //中序遍历非递归 vector<int> mid_order_non(TreeNode* root){ if(!root) return vector<int>(); stack<TreeNode*> s; vector<int> number; TreeNode* cur = root; while ((!s.empty()) || cur) { while (cur) { s.push(cur); cur = cur->left; } if (!s.empty()) { TreeNode* temp = s.top(); s.pop(); number.push_back(temp->val); cur = temp->right; } } return number; } //中序遍历2 vector<int> mid_order_non2(TreeNode* root){ if(!root) return vector<int>(); stack<TreeNode*> s; vector<int> number; TreeNode* cur = root->left; while ((!s.empty())||cur) { while (cur) { s.push(cur); cur = cur->left; } cur = s.top(); s.pop(); number.push_back(cur->val); cur = cur->right; } return number; } //后序遍历 vector<int> after_order_non(TreeNode* root){ if(!root) return vector<int>(); vector<int> number; stack<TreeNode*> s; TreeNode* cur = root; TreeNode* last = nullptr; while ((!s.empty()) || cur) { while (cur) { s.push(cur); cur = cur->left; } cur = s.top(); if((!cur->right) || cur->right == last){ number.push_back(cur -> val); last = cur; s.pop(); cur = s.top(); }else cur = cur->right; } return number; } void PostOrder_Nonrecursive(TreeNode* root) // 后序遍历的非递归 双栈法 { stack<TreeNode*> s1 , s2; TreeNode* curr ; // 指向当前要检查的节点 s1.push(root); while(!s1.empty()) // 栈空时结束 { curr = s1.top(); s1.pop(); s2.push(curr); if(curr->left) s1.push(curr->left); if(curr->right) s1.push(curr->right); } while(!s2.empty()) { printf("%c ", s2.top()->val); s2.pop(); } } //求二叉树非遍历情况下的平均深度 int findDepth(TreeNode* root){ if(!root) return 0; root->val = 1; vector<int> height; vector<TreeNode*> tree{root}; while (tree.size()) { root = tree.back(); tree.pop_back(); if(!root->left && !root->right) height.push_back(root->val); if(root->left){ tree.push_back(root->left); root->left->val = root->val+1; } if(root->right){ tree.push_back(root->right); root->right->val = root->val + 1; } } int sum = accumulate(height.begin(), height.end(), 0); cout << sum << " " << height.size() << endl; return (float)sum/(float)height.size(); } //求二叉树非遍历情况下的平均深度 int tree_depth(TreeNode* root){ if(!root) return 0; vector<TreeNode*> temp{root}; int h =0; vector<int> height; while (temp.size()) { h+= 1; vector<TreeNode*> nei; for(TreeNode* it:temp){ if(!it->left && !it->right) {height.push_back(h);continue;} if(it->left) nei.push_back(it->left); if (it->right) { nei.push_back(it->right); } } temp = nei; } int sum= accumulate(height.begin(), height.end(), 0); cout << sum << " " << height.size() << endl; return sum/height.size(); } int main(){ TreeNode* root = new TreeNode(6); TreeNode* left1 = new TreeNode(6); TreeNode* right1 = new TreeNode(6); TreeNode* left12 = new TreeNode(6); TreeNode* left123 = new TreeNode(6); TreeNode* left1234 = new TreeNode(6); root->left = left1; left1->left = left12; left12->left = left123; left123->right = left1234; root->right = right1; int zhi = tree_depth(root); cout << zhi << endl; return 0; }