头文件

使用node 定义节点，并重命名为BTNode。二叉树类 BTree中含有一个成员BTNode* head;存放二叉树的头节点。

typedef int ElemType;
const int MaxSize = 20;
typedef struct node {
	data: ElemType;
	lchild: node*;
	rchild: node*;
}
BTNode;
class BTree {
	head: BTNode*;
	public:
		BTree() {
			head = new BTNode;
		}
		BTree(const char* str) {
			CreateBTNode(str);
		}
		// ...其他成员函数定义
}

成员函数

构造函数

两个构造函数：一个无参构造，只为头节点开辟空间。一个有参构造，传入一个以括号表示法表示的树的const char*字符串对象。

BTree::BTree(const char* str) {
	CreateBTNode(str);
}

创建二叉树CreateBTNode

使用void CreateBTNode(const char* str);方法创建。

创建过程使用栈作为辅助，对于一个合法的字符串，遍历其中所有元素，如果遇到一个节点元素(default部分)，初始化节点，若该节点作为头节点，则执行
this->head = p;，若不是头节点，通过
k判断该节点作为栈顶元素的左孩子节点或者右孩子节点。如果遇到
(，此时
p已经被赋值，其值为上一个遍历到的节点元素，
(表明该节点
p将作为之后节点的父节点，将
p进栈，并将
k置为1。如果遇到
,，表明某个节点的左子树处理完，将要处理右孩子。如果遇到
)，表明当前栈顶元素的孩子节点已经处理完，将其出栈。

void BTree::CreateBTNode(const char* str) {
	BTNode* St[MaxSize], * p = NULL;
	int top = -1;
	int k = 1;
	int j = 0;
	char ch;
	this->head = NULL;
	ch = str[j];
	while (ch != '\0') {
		switch (ch) {
		case '(': // 遇到左括号
			++top;
			St[top] = p;
			k = 1;
			break;
		case ')': // 遇到右括号
			top--;
			break;
		case ',': // 遇到逗号
			k = 2;
			break;
		default:
			// 遇到一个元素时，节点初始化
			p = new BTNode;
			p->data = ch;
			p->lchild = p->rchild = NULL;
			if (this->head == NULL) {
				this->head = p;
			} else {
				switch (k) {
				case 1:
					St[top]->lchild = p;
					break;
				case 2:
					St[top]->rchild = p;
					break;
				}
			}
		}
		ch = str[++j];
	}
}

输出二叉树DispBTree

BTree类提供公共接口void DispBTree();用于输出二叉树，并void DispBTree(BTNode* b);中实现接口

输出过程通过递归实现，并以括号表示法格式输出。

void BTree::DispBTree() {
	this->DispBTree(this->head);
	cout << endl;
}
 void BTree::DispBTree(BTNode* b) {
if (b == NULL) return;
cout << (char)b->data;
if (b->lchild != NULL || b->rchild != NULL) {
cout << "(";
this->DispBTree(b->lchild);
if (b->rchild != NULL) {
cout << ",";
}
this->DispBTree(b->rchild);
cout << ")";
}
}