[数据结构与算法]数据结构——二叉树

前言

博主从七月初开始为找工作开始刷leetcode题目，从今天开始持续记录刷题过程中的问题，巩固自己的知识储备。结合网上资料整理有关二叉树的总结，提供给一起学习的朋友。

树的前序遍历、中序遍历、后续遍历

最先接触的是二叉树中几种常见的遍历方法。初步了解树的数据结构。链式储存的二叉树结点定义：

	struct TreeNode{
		int val;
		TreeNode* left;
		TreeNode* right;
		TreeNode(int x):val(x), left(NULL), right(NULL){}
	};

前中后序遍历的递归写法：区别仅在于根节点与左右叶结点的取值先后。

	//前序遍历
	void preorder(TreeNode* root, vector<int>& res) {
        if (!root) {
            return;
        }
        res.push_back(root->val);
        preordertraversal(root->left, res);
        preordertraversal(root->right, res);
    }
    //中序遍历
	void inorder(TreeNode* root, vector<int>& res) {
        if (!root) {
            return;
        }
        inorder(root->left, res);
        res.push_back(root->val);
        inorder(root->right, res);
    }
    //后序遍历
	void postorder(TreeNode* root, vector<int>& res) {
        if (!root) {
            return;
        }
        postorder(root->left, res);
        postorder(root->right, res);
        res.push_back(root->val);
    }

中序遍历的迭代写法（相比于递归更需理解！）

	//inorder
	void preorder(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st//用来保存结点地址
        if(root)
        	st.push(root);
        while(!st.empty()){
			TreeNode* p =st.top();
			if(p){
				st.pop();
				if(p->right) st.push(p->right);
				st.push(p);
				st.push(NULL);    //前后序遍历只需改变这两行代码的顺序
				if(p->left) st.push(p->left);
			}else{
			st.pop();
			p = st.top();
			st.pop();
			result.push_back(p->val);
			}
		}
		return result
    }

二叉树的层序遍历

二叉树的层序遍历应用到广度搜索算法（BFS），参考代码如下：

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector <vector <int>> ans;
        if (!root) {
            return ans;
        }
        queue <TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int currentLevelSize = q.size();
            ans.push_back(vector <int> ());
            for (int i = 1; i <= currentLevelSize; ++i) {
                TreeNode* node = q.front();
                q.pop();
                ans.back().push_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }
        return ans;
    }
};

二叉搜索树

二叉搜索树是一个有序树，是一种能够高效地进行如下操作的数据结构：

1. 插入一个数值；
2. 查询一个数值；
3. 删除某个数值；

在二叉搜索树中其结构为：

1. 任意结点处左子树上所有结点的值均不大于当前根结点的值（当前结点的左子树存在）；
2. 任意结点处右子树上所有结点的值均不小于当前根结点的值（当前结点的右子树存在）；
3. 任意结点的左、右子树也分别为二叉搜索树；

Leetcode_700 二叉搜索树中搜索：

TreeNode* searchBST(TreeNode* root, int val) {
        if (root == NULL || root->val == val) return root;
        if (root->val > val) return searchBST(root->left, val);
        if (root->val < val) return searchBST(root->right, val);
        return NULL;
    }