[数据结构]代码：二叉树的基本 *** 作

[数据结构]代码：二叉树的基本 *** 作

首先定义节点：

template 
struct TreeNode
{
	T val;
	TreeNode* parent;
	TreeNode* left;
	TreeNode* right;
	TreeNode() : val(0), parent(nullptr), left(nullptr), right(nullptr) {}
	TreeNode(T val) : val(val), parent(nullptr), left(nullptr), right(nullptr) {}
	TreeNode(T val, TreeNode* p) : val(val), parent(p), left(nullptr), right(nullptr) {}
	TreeNode(T val, TreeNode* p, TreeNode* l, TreeNode* r) : val(val), parent(p), left(l), right(r) {}
};

说明：这里并没有用到指向父节点的指针parent，可能以后会需要

定义二叉树类：

template 
class BinaryTree {
private:	
	TreeNode* root;
	
public:
	BinaryTree() : root(nullptr) {}
	BinaryTree(TreeNode* r) : root(r) {}
	
	TreeNode* getRoot() {
		return root;
	}
    
    //层级建树
	void levelOrderBuildTree(vector arr) {
		queue*>> que;
		root = new TreeNode(arr[0]);
		que.push(make_pair(0, root));
		
		while (!que.empty()) {
			pair*> m = que.front();
			int pos = m.first+1;
			TreeNode* p = m.second;
			que.pop();
			if (pos * 2 - 1 < arr.size() && arr[pos * 2 - 1] != NULL) {
				p->left = new TreeNode(arr[pos * 2 - 1]);
				que.push(make_pair(pos * 2 - 1, p->left));
			}
			if (pos * 2 < arr.size() && arr[pos * 2] != NULL) {
				p->right = new TreeNode(arr[pos * 2]);
				que.push(make_pair(pos * 2, p->right));
			}
		}
		return;
	}

    //前序遍历
	vector preOrder() {
		stack*> st;
		vector ans;
		st.push(root);
		while (!st.empty()) {
			TreeNode* p = st.top();
			st.pop();
			ans.push_back(p->val);
			if (p->right) st.push(p->right);
			if (p->left) st.push(p->left);
		}
		return ans;
	}

    //中序遍历
	vector inOrder() {
		stack*> st;
		vector ans;
		
		if (!root) return ans;

		TreeNode* h = root;
		while (!st.empty() || h!=nullptr) {
			while (h) {
				st.push(h);
				h = h->left;
			}
			h = st.top();
			st.pop();
			ans.push_back(h->val);
			h = h->right;
		}
		return ans;
	}

    //后序遍历
	vector postOrder() {
		vector ans;
		if (!root) return ans;

		stack*> st;
		TreeNode* h = root;
		TreeNode* pre = nullptr;
		while (h != nullptr || !st.empty()) {
			while (h) {
				st.push(h);
				h = h->left;
			}
			h = st.top();
			st.pop();
			if (h->right == nullptr || h->right == pre) {
				ans.push_back(h->val);
				pre = h;
				h = nullptr;
			}
			else {
				st.push(h);
				h = h->right;
			}
		}
		return ans;
	}

    //层级遍历
	vector> levelOrder() {
		vector> ans;

		if (!root) return ans;

		queue*> que;
		que.push(root);
		while (!que.empty()) {
			int size = que.size();
			vector row;
			for (int i = 0; i < size; i++) {
				TreeNode* p = que.front();
				que.pop();
				if (p->left) que.push(p->left);
				if (p->right) que.push(p->right);
				row.push_back(p->val);
			}
			ans.push_back(row);
		}

		return ans;
	}

    //通过前序和中序建树
	void pre_in_BuildTree(vector pre, vector in) {
		unordered_map mp;
		for (int i = 0; i < in.size(); i++) {
			mp[in[i]] = i;
		}
		root = preHelper(pre, in, 0, pre.size() - 1, 0, in.size() - 1, mp);
	}
	TreeNode* preHelper(const vector& pre, const vector& in, int pre_begin, int pre_end, int in_begin, int in_end, unordered_map& mp) {
		if (in_begin > in_end) return nullptr;

		T rootVal = pre[pre_begin];
		TreeNode* node = new TreeNode(rootVal);
		int rootIndex = mp[rootVal];
		int leftSize = rootIndex - in_begin;
		node->left = preHelper(pre, in, pre_begin + 1, pre_begin + leftSize, in_begin, rootIndex - 1, mp);
		node->right = preHelper(pre, in, pre_begin + leftSize + 1, pre_end, rootIndex + 1, in_end, mp);
		return node;
	}


    //通过后序和中序建树
	void post_in_BuildTree(vector post, vector in) {
		unordered_map mp;
		for (int i = 0; i < in.size(); i++) {
			mp[in[i]] = i;
		}
		root = postHelper(post, in, 0, post.size() - 1, 0, in.size() - 1, mp);
	}
	TreeNode* postHelper(const vector& post, const vector& in, int post_begin, int post_end, int in_begin, int in_end, unordered_map& mp) {
		if (in_begin > in_end) return nullptr;

		T rootVal = post[post_end];
		TreeNode* node = new TreeNode(rootVal);
		int rootIndex = mp[rootVal];
		int leftSize = rootIndex - in_begin;
		node->left = postHelper(post, in, post_begin, post_begin + leftSize - 1, in_begin, rootIndex - 1, mp);
		node->right = postHelper(post, in, post_begin + leftSize, post_end - 1, rootIndex + 1, in_end, mp);
		return node;
	}

};