数据结构中树的介绍 • Mility

树是一种在实际编程中经常遇到的数据结构。它的逻辑很简单：除了根节点之外每个节点只有一个父节点，根节点没有父节点；除了叶节点之外所有的节点都有一个或多个子节点，叶节点没有子节点。通常树有如下几种遍历方式：

前序遍历：先访问根节点，再访问左子节点，最后访问右子节点。
中序遍历：先访问左子节点，再访问根节点，最后访问右子节点。
后序遍历：先访问左子节点，再访问右子节点，最后访问根节点。
宽度优先遍历：先访问数的第一层节点，再访问树的第二层节点……一直到访问到最下面一层节点。在同一层节点中，以从左到右的顺序依次访问。

二叉树右很多特例，二叉搜索树就是其中的一种。在二叉搜索树中，左子节点总是小于或等于根节点，而右子节点总是大于或等于根节点。
二叉树的另外两个特例是堆和红黑树。堆分为最大堆和最小堆。在最大堆中根节点的值最大，在最小堆中根节点的值最小。有很多需要快速找到最大值或者最小值的问题都可以用堆来解决。红黑树是把树中的节点定义为红、黑两种颜色，并通过规则确保从根节点到叶节点的最长路径的长度不超过最短路径的两倍。

/*
 * ConstructCore.cpp
 *
 *  Created on: 2016年7月12日
 *      Author: mility
 */

/**
 * 功能：输入二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。  
 * 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如  
 * 输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}。
 */

#include <iostream>
#include <vector>
#include <stdexcept>
using namespace std;

struct BinaryTreeNode {
	int value;
	BinaryTreeNode *left;
	BinaryTreeNode *right;

	BinaryTreeNode(int val) {
		value = val;
		left = NULL;
		right = NULL;
	}
};

BinaryTreeNode* ConstructTree(vector<int>::const_iterator prebeg,
		vector<int>::const_iterator preend, vector<int>::const_iterator inbeg,
		vector<int>::const_iterator inend) {
	BinaryTreeNode *root = new BinaryTreeNode(*prebeg);

	if (prebeg == preend) {
		if (inbeg == inend && *inbeg == *prebeg)
			return root;
		else
			throw runtime_error("Invalid input.");
	}

	vector<int>::const_iterator index;

	index = inbeg;
	while (*index != root->value && index != inend)
		index++;
	if (index == inend && *index != root->value)
		throw runtime_error("Invalid input.");

	int leftlength = index - inbeg;

	if (leftlength > 0) {
		root->left = ConstructTree(prebeg + 1, prebeg + leftlength, inbeg,
				index - 1);
	}
	if (inend > index) {
		root->right = ConstructTree(prebeg + leftlength + 1, preend, index + 1,
				inend);
	}

	return root;
}

int AfterOrder(BinaryTreeNode *root) {
	if (root == NULL)
		return 0;
	if (root->left)
		AfterOrder(root->left);
	if (root->right)
		AfterOrder(root->right);
	cout << root->value << " ";
	return 0;
}

int main(void) {
	int n, i = 0;

	while (cin >> n) {
		vector<int> preorder(n);
		vector<int> inorder(n);
		i = 0;
		while (i < n) {
			cin >> preorder[i];
			i++;
		}
		i = 0; 
		while (i < n) {
			cin >> inorder[i];
			i++;
		}

		if (n == 0) {
			cout << "No" << endl;
			continue;
		}

		BinaryTreeNode *root;
		vector<int>::const_iterator prebeg = preorder.begin();
		vector<int>::const_iterator preend = preorder.end();
		vector<int>::const_iterator inbeg = inorder.begin();
		vector<int>::const_iterator inend = inorder.end();
		root = ConstructTree(prebeg, preend - 1, inbeg, inend - 1);
		if (root == NULL)
			continue;

		AfterOrder(root);

		cout << endl;
	}

	return 0;
}

Back to the top!