二叉樹先序周遊、中序周遊、後序周遊

輸入二叉樹的先序周遊序列和中序周遊序列，輸出該二叉樹的後序周遊序列。（非建二叉樹版本）

#include<iostream>
#include<string>
using namespace std;
string preord, inord;
void rebuild (int preleft, int preright, int inleft, int inright)
{
	int root, leftsize, rightsize;
	if(preleft <= preright && inleft <= inright)
	{
		for(root = inleft; root <= inright; root++)
		{
			if(preord[preleft] == inord[root])
			{
				break;
			}
		}
		leftsize = root - inleft;
		rightsize = inright - root;
		if(leftsize > 0)
		{
			rebuild(preleft + 1, preleft + leftsize, inleft, inleft + leftsize - 1);
		}
		if(rightsize > 0)
		{
			rebuild(preleft + leftsize + 1, preright, inleft + leftsize + 1, inright);
		}
	cout << inord[root];
	}
}
int main()
{
	int length;
	while(cin >> preord >> inord)
	{
		length = preord.length();
		rebuild(0, length-1, 0, length-1);
		cout << endl;
		preord.clear();
		inord.clear();
	}
	return 0;
}

           

已知一棵二叉樹的中序周遊和後序周遊，求二叉樹的先序周遊

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
string midord, inord;
void rebuild(int midleft, int midright, int inleft, int inright)
{
	int root, leftsize, rightsize;
	if(midleft <= midright && inleft <= inright)
	{
		 for(root = midleft; root <= midright; root++)
        {
            if(inord[inright] == midord[root])
			{
				break;
			}
        }
		leftsize = root - midleft;
		rightsize = midright - root;
		cout << midord[root];
		if(leftsize > 0)
		{
			rebuild(midleft, midleft + leftsize - 1, inleft, inleft + leftsize - 1);
		}
		if(rightsize > 0)
		{
			rebuild(midleft + leftsize + 1, midright, inleft + leftsize, inright - 1);
		}
	}
}
int main()
{
	while(cin >> midord >> inord)
	{
	int length = midord.length() -1;
	rebuild(0, length, 0, length);
	cout << endl;
	midord.clear();
	inord.clear();
	}
	return 0;
}
           

至于已知前序周遊序列和後序周遊序列，求中序周遊序列，存在多種情況。

建立二叉樹版本

#include<iostream>
#include<queue>
#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std;
#pragma warning(disable : 4996)
#define MAX 100
typedef struct BiNode
{
	char data;
	struct BiNode *left;
	struct BiNode *right;
}BiNode, *BiTree;
int sum;

void CreateBinaryTreeToPre(BiTree &tree, char *inorder, char *postorder, int length)
{
	if(length == 0)
	{
		return;
	}
	tree = new BiNode;
	tree->data = *(postorder + length - 1);
	tree->left = NULL;
	tree->right = NULL;
	//cout << tree->data;
	int rootIndex;
	for(rootIndex = 0; rootIndex < length; rootIndex++)
	{
		if(inorder[rootIndex] == *(postorder + length - 1))
		{
			break;
		}
	}
	CreateBinaryTreeToPre(tree->left, inorder, postorder, rootIndex);
	CreateBinaryTreeToPre(tree->right, inorder + rootIndex + 1, postorder + rootIndex, length - rootIndex - 1);
}


void CreateBinaryTreeToPost(BiTree &tree, char *preorder, char *inorder, int length)
{
	if(length == 0)
	{
		return;
	}
	tree = new BiNode;
	tree->data = *preorder;
	tree->left = NULL;
	tree->right = NULL;
	int rootIndex;
	for(rootIndex = 0; rootIndex < length; rootIndex++)
	{
		if (inorder[rootIndex] == *preorder)
		{
			break;
		}
	}
	CreateBinaryTreeToPost(tree->left, preorder + 1, inorder, rootIndex);
	CreateBinaryTreeToPost(tree->right, preorder + rootIndex + 1, preorder + rootIndex + 1, length - rootIndex - 1);
	//cout << tree->data;
}

void PreOrder(BiTree T)//前序周遊
{
	if(T != NULL)
	{
		cout << T->data;
		PreOrder(T->left);
		PreOrder(T->right);
	}
}
void InOrder(BiTree T)//中序周遊
{
	if(T != NULL)
	{
		InOrder(T->left);
		cout << T->data;
		InOrder(T->right);
	}
}
void PostOrder(BiTree T)//後序周遊
{
	if(T != NULL)
	{
		PostOrder(T->left);
		PostOrder(T->right);
		cout << T->data;
	}
}
void LevOrder(BiTree T)//層次周遊
{
	if(T != NULL)
	{
		BiTree p = T;
		queue<BiTree>que;
		que.push(p);
		while(!que.empty())
		{
			p = que.front();
			cout << p->data;
			que.pop();
			if(p->left != NULL)
			{
				que.push(p->left);
			}
			if(p->right != NULL)
			{
				que.push(p->right);
			}
		}
	}
}
int Size(BiTree T)//計算二叉樹節點數
{
	if(T)
	{
		if(T->left == NULL && T->right == NULL)
		{
			sum++;
		}
		Size(T->left);
		Size(T->right);
	}
	return sum;
}
int Deep(BiTree T)//計算二叉樹深度
{
	int m, n;
	if(T == NULL) return 0;
	m = Deep(T->left);
	n = Deep(T->right);
	if(m > n) return m + 1;
	else return n + 1;
}

int Scan()
{
	int n;
	cout << "-----------------++++++++++++++++++------------------- " << endl;  
	cout << "                請選擇所要進行的操作                     " << endl;  
	cout << "   1、已知前序、中序建立二叉樹                           " << endl;  
	cout << "   2、已知中序、後序建立二叉樹                           " << endl;  
	cout << "   3、輸出前序周遊序列                                   " << endl;  
	cout << "   4、輸出中序周遊序列      5、輸出後序周遊結果           " << endl;  
	cout << "   6、輸出層次周遊序列  7、輸出葉節點數和深度             " << endl;  
	cout << "-----------------++++++++++++++++++------------------- " << endl;  
	cin >> n;
	return n;
}

int main(void)
{
	int quit = 0;
	BiTree tree = NULL;
	char inorder[MAX] = {0};
	char preorder[MAX] = {0};
	char postorder[MAX] = {0};

	while (!quit)
	{
		switch(Scan())
		{
		case 1 : cin >> preorder >> inorder; CreateBinaryTreeToPost(tree, preorder, inorder, strlen(preorder)); break;
		case 2 : cin >> inorder >> postorder; CreateBinaryTreeToPre(tree, inorder, postorder, strlen(inorder));break;
		case 3 : cout << "前序周遊結果為：" << endl; PreOrder(tree); cout << endl << endl; break;
		case 4 : cout << "中序周遊結果為：" << endl; InOrder(tree); cout << endl << endl; break;
		case 5 : cout << "後序周遊結果為：" << endl; PostOrder(tree); cout << endl << endl; break;
		case 6 : cout << "層次周遊結果為：" << endl; LevOrder(tree); cout << endl << endl; break;
		case 7 : cout << "二叉樹葉節點個數為：" << Size(tree)<<endl; cout << "二叉樹深度數為：" << Deep(tree) << endl; break;
		default: quit = 0; break;
		}
	}
	return 0;
}