描述

用链表的方式实现二叉树的存储和基本操作，包括CreateBinTree()、PreorderTraversal()、InorderTraversal()、PostorderTraversal()等操作。

输入

ABCDFGI00E00H000000

输入为一行字符型数据，字符之间无空格，表示二叉树的层序生成序列，’0’表示空结点。

输出

ABDFECGHI
DBEFAGHCI
DEFBHGICA

直接用STL的queue模板

#include<iostream>
#include<queue>
using namespace std;
struct TNode {
	char Data;
	struct TNode* Left;
	struct TNode* Right;
};
typedef struct TNode* BinTree;
BinTree CreatBinTree(string s) {
	char c;
	BinTree BT, T;
	queue<BinTree> q;
	if (s[0] != '0') {
		BT = (BinTree)malloc(sizeof(struct TNode));
		BT->Data = s[0];
		BT->Left = BT->Right = NULL;
		q.push(BT);
	}
	else
		return NULL;
	
	for (int i = 1;i<s.size();i++) {
		T = q.front();
		q.pop();
		c = s[i];
		if (c == '0')
			T->Left = NULL;
		else {
			T->Left = (BinTree)malloc(sizeof(struct TNode));
			T->Left->Data = c;
			T->Left->Left = T->Left->Right = NULL;
			q.push(T->Left);
		}
		i++;
		c = s[i];
		if (c == '0')
			T->Right = NULL;
		else {
			T->Right = (BinTree)malloc(sizeof(struct TNode));
			T->Right->Data = c;
			T->Right->Left = T->Right->Right = NULL;
			q.push(T->Right);
		}
	}
	return BT;
}
void PreorderTraversal(BinTree BT) {
	if (BT) {
		cout << BT->Data;
		PreorderTraversal(BT->Left);
		PreorderTraversal(BT->Right);
	}
}
void InorderTraversal(BinTree BT){
	if (BT) {
		InorderTraversal(BT->Left);
		cout << BT->Data;
		InorderTraversal(BT->Right);
	}
}
void PostorderTraversal(BinTree BT){
	if (BT) {
		PostorderTraversal(BT->Left);
		PostorderTraversal(BT->Right);
		cout << BT->Data;
	}
}
int main() {
	string x;
	cin >> x;
	BinTree t = CreatBinTree(x);
	PreorderTraversal(t);
	cout << endl;
	InorderTraversal(t);
	cout << endl;
	PostorderTraversal(t);
	return 0;
}