由先序中序，或后序中序，可以唯一确定二叉树；完全二叉树的顺序存储，c/c++描述

  这是课本里的，两个定理。由先序（根左右）、后序（左右根）可以确定根节点是哪个。由中序（左根右）可以确定左子树和右子树的范围。所以我们也找到了二叉树的左子树和右子树的先序（或后序）和中序排列。由归纳法，可得出这个构造二叉树链表的方法。
  对于完全二叉树，相对于满二叉树，只有最后两行可以不排满，是非常接近于满二叉树的，其跟满二叉树一样，父母节点与子节点的层序排列序号有2倍的规律可循。所以可以由完全二叉树的顺序排列构造其链表排列，非完全二叉树，比较稀疏的二叉树要补充至完全二叉树形式，才可以使用顺序存储，比如后两行以上的行中的空节点，以存储字符‘#’代替表示。
  本程序包含以下几个函数，程序执行思路是：由函数createBiTreeCommaExpre完成从逗号表达式建立二叉树；由函数displayBiTree输出二叉树的逗号表达式形式到屏幕，以检测建立二叉树的createBiTreeCommaExpre是否正确；由函数totalNumberOfNodes统计二叉树的总节点数。
  由函数preOrderRecursion输出二叉树的先序遍历结果至数组，（这里以节点为字符为例，所以遍历结果存储到字符数组里）；由函数inOrderRecursion输出二叉树的中序排列结果至数组；由函数postOrderRecursion输出二叉树的后序遍历结果至数组。由函数dispalyArray输出字符数组至屏幕，以检验各种遍历结果是否正确。
  由函数buildBiTreePreIn根据二叉树的先序中序遍历结果重新构造新的另一个二叉树；由函数buildBiTreePostIn根据二叉树的后序中序遍历结果重新构造另一个新的二叉树；由函数buildBiTreeSequen根据二叉树的顺序存储结果构造其对应的二叉树；由函数compareBiTree比较这四个二叉树是否完全相等，以确认我们这三个构造函数是否写的正确。由主函数main调用以上所有函数。
  完整代码如下，这是主函数main所在的源文件：

#include<iostream>
#include<stdio.h>
using namespace std;
#define MAXARRAY 20
#define STACKDEPTH 15
struct BiTreeNode {
	char value;
	BiTreeNode* leftChild;
	BiTreeNode* rightChild;
};

extern void createBiTreeCommaExpre(BiTreeNode*& biTreeRoot, char* ptChar);
extern void displayBiTree(BiTreeNode*& biTreeRoot);
extern int totalNumberOfNodes(BiTreeNode*& biTreeRoot);
extern void dispalyArray(char array[]);
extern void preOrderRecursion(BiTreeNode*& biTreeRoot, char* &ptArrayPreExp);
extern void inOrderRecursion(BiTreeNode*& biTreeRoot, char* &ptArrayInExp);
extern void postOrderRecursion(BiTreeNode*& biTreeRoot, char* &ptArrayPostExp);
extern BiTreeNode * buildBiTreePreIn(char * ptPreExpre,char* ptInexpre,int length);
extern BiTreeNode * buildBiTreePostIn(char* ptPostExpre, char* ptInexpre, int length);
extern BiTreeNode * buildBiTreeSequen(char* ptSequenExpre,int location);
extern bool compareBiTree(BiTreeNode * &biTreeA, BiTreeNode* &biTreeB);

int main() {
	char arrayCommaExpress[MAXARRAY] = "A(B(D(,G)),C(E,F))";
	char* ptArrayComma = arrayCommaExpress;  //c++里只能这样分开定义，要不会出错。
	BiTreeNode* biTreeRoot = NULL;

	createBiTreeCommaExpre(biTreeRoot,arrayCommaExpress);
	cout << "the char array is :"; 
	dispalyArray(arrayCommaExpress);

	cout<< endl<< "binary tree is    :";
	displayBiTree(biTreeRoot);

	int lengthBiTree = totalNumberOfNodes(biTreeRoot);
	cout<<endl << "binary tree total nodes : " << lengthBiTree << endl;

	char arrayPreExpre[MAXARRAY] = "";
	char* ptArrayPreExp = arrayPreExpre;
	preOrderRecursion(biTreeRoot,ptArrayPreExp);
	cout <<endl<< "pre order expression  : ";
	dispalyArray(arrayPreExpre);

	char arrayInExpre[MAXARRAY] = "";
	char* ptArrayInExpre = arrayInExpre;
	inOrderRecursion(biTreeRoot,ptArrayInExpre);
	cout << endl << "in order expression   : ";
	dispalyArray(arrayInExpre);

	char arrayPostExpre[MAXARRAY] = "";
	char* ptArrayPostExpre = arrayPostExpre;
	postOrderRecursion(biTreeRoot,ptArrayPostExpre);
	cout << endl << "post order expression : ";
	dispalyArray(arrayPostExpre);

	char arraySequenExpre[MAXARRAY] = "9ABCD#EF#G";
	char* ptArraySequenExpre = arraySequenExpre;
	cout << endl << "sequential order expression(手工计算的) : ";
	dispalyArray(arraySequenExpre);
	cout << endl;

	BiTreeNode* biTreePreIn = buildBiTreePreIn(arrayPreExpre,
		arrayInExpre,lengthBiTree);
	BiTreeNode* biTreePostIn = buildBiTreePostIn(arrayPostExpre,
		arrayInExpre,lengthBiTree);
	BiTreeNode* biTreeSequen = buildBiTreeSequen(arraySequenExpre,1);

	cout << endl;
	cout << "Succeed in building BiTree according to pre and in expression ? ";
	cout << (compareBiTree(biTreeRoot, biTreePreIn) ? "yes" : "no" )<< endl;
	displayBiTree(biTreePreIn);
	cout << endl;

	cout << endl;
	cout << "Succeed in building BiTree according to post and in expression ? ";
	cout << (compareBiTree(biTreeRoot, biTreePostIn) ? "yes" : "no") << endl;
	displayBiTree(biTreePostIn);
	cout << endl;

	cout << endl;
	cout << "Succeed in building BiTree according to sequential expression ? ";
	cout << (compareBiTree(biTreeRoot, biTreeSequen) ? "yes" : "no") << endl;
	displayBiTree(biTreeSequen);
	cout << endl;

	cout << endl <<"thank you for your practices ." << endl;

	return 0;
}

  这是各个函数所在的源文件（大量应用了递归，所以不算太长）：

#include<iostream>
#include<stdio.h>
using namespace std;
#define STACKDEPTH 15
#define MAXARRAY 20
struct BiTreeNode {
	char value;
	BiTreeNode* leftChild;
	BiTreeNode* rightChild;
};
void createBiTreeCommaExpre(BiTreeNode*& biTreeRoot, char* ptChar) {
	struct {
		BiTreeNode* ptsBiTree[STACKDEPTH];
		int indexTop = -1;
	}sequStack;

	BiTreeNode* ptNew = NULL;
	char s;
	int leftRight;//1 is left   2 is right
	while (*ptChar != '\0') {
		s = *ptChar;
		if ('A' <= s && s <= 'Z') {
			ptNew = new BiTreeNode;
			ptNew->value = s;
			ptNew->leftChild = ptNew->rightChild = NULL;

			if (biTreeRoot == NULL)
				biTreeRoot = ptNew;
			else if (leftRight == 1)
				sequStack.ptsBiTree[sequStack.indexTop]->leftChild = ptNew;
			else if (leftRight == 2)
				sequStack.ptsBiTree[sequStack.indexTop]->rightChild = ptNew;
		}
		else if (s == '(') {
			sequStack.indexTop++;
			sequStack.ptsBiTree[sequStack.indexTop] = ptNew;
			leftRight = 1;
		}
		else if (s == ',')
			leftRight = 2;
		else if (s == ')')
			sequStack.indexTop--;

		ptChar++;
	}
}
void displayBiTree(BiTreeNode*& biTreeRoot) {   // 本查找方法是先序遍历
	if (biTreeRoot == NULL)
		return;//if binary tree does not exsit,return
	cout << biTreeRoot->value;
	if (biTreeRoot->leftChild != NULL || biTreeRoot->rightChild != NULL) {
		cout << '(';
		displayBiTree(biTreeRoot->leftChild);
		if (biTreeRoot->rightChild != NULL) {
			cout << ',';
			displayBiTree(biTreeRoot->rightChild);
		}
		cout << ')';
	}
}

int totalNumberOfNodes(BiTreeNode*& biTreeRoot) {
	if (biTreeRoot == NULL)
		return 0;
	return totalNumberOfNodes(biTreeRoot->leftChild) +
		totalNumberOfNodes(biTreeRoot->rightChild) + 1;
}

void dispalyArray(char array[]) {
	char* pt = array;
	while (*pt != '\0') {
		cout << *pt;
		pt++;
	}
}

void preOrderRecursion(BiTreeNode*& biTreeRoot, char* &ptArrayPreExp) {
	if (biTreeRoot == NULL)
		return;
	*ptArrayPreExp = biTreeRoot->value;
	ptArrayPreExp++;

	preOrderRecursion(biTreeRoot->leftChild,ptArrayPreExp);
	preOrderRecursion(biTreeRoot->rightChild,ptArrayPreExp);
}

void inOrderRecursion(BiTreeNode*& biTreeRoot, char* &ptArrayInExp) {
	if (biTreeRoot == NULL)
		return;
	
	inOrderRecursion(biTreeRoot->leftChild,ptArrayInExp);
	
	*ptArrayInExp = biTreeRoot->value;
	ptArrayInExp++;

	inOrderRecursion(biTreeRoot->rightChild,ptArrayInExp);

}
void postOrderRecursion(BiTreeNode*& biTreeRoot, char* &ptArrayPostExp) {
	if (biTreeRoot == NULL)
		return;

	postOrderRecursion(biTreeRoot->leftChild,ptArrayPostExp);
	postOrderRecursion(biTreeRoot->rightChild,ptArrayPostExp);

	*ptArrayPostExp = biTreeRoot->value;
	ptArrayPostExp++;

}

BiTreeNode* buildBiTreePreIn(char* ptPreExpre, char* ptInexpre, int length) {
	if (length <= 0)
		return NULL;
	 
	char root = *ptPreExpre;
	
	BiTreeNode* biTreeRoot = new BiTreeNode;
	biTreeRoot->value = root;

	char* ptRoot = ptInexpre;
	while (*ptRoot != root)
		ptRoot++;
	int lengthLeftChilds = ptRoot - ptInexpre;
	int lengthRightChilds = length - 1 - lengthLeftChilds;

	biTreeRoot->leftChild = 
		buildBiTreePreIn(ptPreExpre + 1,ptInexpre,lengthLeftChilds);
	biTreeRoot->rightChild = buildBiTreePreIn(ptPreExpre + lengthLeftChilds + 1,
		ptRoot + 1,lengthRightChilds);

	return biTreeRoot;
}
BiTreeNode* buildBiTreePostIn(char* ptPostExpre, char* ptInexpre, int length) {
	if (length <= 0)
		return 0;

	char root = *(ptPostExpre + length - 1);
	BiTreeNode* biTreeRoot = new BiTreeNode;
	biTreeRoot->value = root;

	char* ptRoot = ptInexpre;
	while (*ptRoot != root)
		ptRoot++;

	int lengthLeftChilds = ptRoot - ptInexpre;
	int lengthRightChilds = length - 1 - lengthLeftChilds;

	biTreeRoot->leftChild = 
		buildBiTreePostIn(ptPostExpre,ptInexpre,lengthLeftChilds);
	biTreeRoot->rightChild = buildBiTreePostIn(
		ptPostExpre + lengthLeftChilds,ptRoot + 1,lengthRightChilds);

	return biTreeRoot;
}
BiTreeNode* buildBiTreeSequen(char* ptSequenExpre,int location) {
	if (*(ptSequenExpre + location) == '\0' || 
		*(ptSequenExpre + location) == '#')
		return NULL;
	
	BiTreeNode* biTreeRoot = new BiTreeNode;
	biTreeRoot->value = *(ptSequenExpre + location);

	biTreeRoot->leftChild = buildBiTreeSequen(ptSequenExpre,location * 2);
	biTreeRoot->rightChild = buildBiTreeSequen(ptSequenExpre,location * 2 + 1);

	return biTreeRoot;
}
bool compareBiTree(BiTreeNode* &biTreeA, BiTreeNode* &biTreeB) {
	if (biTreeA == NULL && biTreeB == NULL)
		return true;

	if (biTreeA == NULL && biTreeB != NULL || biTreeA != NULL && biTreeB == NULL)
		return false;

	if (biTreeA->value != biTreeB->value)
		return false;

	return compareBiTree(biTreeA->leftChild, biTreeB->leftChild) &&
		compareBiTree(biTreeA->rightChild,biTreeB->rightChild);
}

  测试结果及对应的二叉树如下：

  谢谢阅读