依次读取广义表中的字符，根据不同情况按照以下方式处理：

（1）遇到左括号，可能接下来读取的元素是左孩子，需要将双亲结点入栈，同时将标志k置为1；

（2）遇到逗号，下一个读取的元素一定是右孩子，将标志置为2；

（3）遇到右括号，表明当前层读取结束，需要回退到上一层，上一层的栈元素将成为新的双亲结点；

（4）遇到字符，创建一个新结点，将当前字符ch存入数据域，然后将该结点插入对应的子树中。根据k的值进行以下处理：

①k为1，则使该结点成为栈顶元素结点的左孩子结点；

②k为2，则使该结点成为栈顶元素结点的右孩子结点。\

#include <iostream>
#include <malloc.h>
#include <stdio.h>
typedef char DataType;
#define MAXSIZE 200
 
using namespace std;
typedef struct BiTnode 
{
	DataType data;
	struct BiTnode *lchild, *rchild;
}*BiTree,BitNode;
int CreateBiTree(BiTree *T, DataType *str);
void DispBTNode(BiTree T);
int CreateBiTree(BiTree *T, DataType *str)
{
	BiTree S[MAXSIZE], p = NULL;
	int top = 0, k = 0, j = 0;
	char ch;
	*T = NULL;
	ch = str[j];
	while (ch!='@')
	{
		switch (ch)
		{
		case '(':
			S[top++] = p;
			k = 1;
			break;
		case ')':
			top--;
			break;
		case ',':
			k = 2;
			break;
 
		default:
			p = (BiTree)malloc(sizeof(BitNode));
			p->data = ch;
			p->lchild = p->rchild = NULL;
			if (*T==NULL)
			{
				*T = p;
			} 
			else
			{
				switch (k)
				{
				case 1:
					S[top - 1]->lchild = p;
					break;
				case 2:
					S[top - 1]->rchild = p;
					break;
				}
			}
			break;
		}
		ch = str[++j];
	}
 
	return 1;
}
 
void main()
{
	int n, len = 0;
	char ch, str[MAXSIZE];
	BiTree T;
	cout << "请输入广义表，以‘@’结束：" << endl;
 
	while ((ch=getchar())!='\n')
	{
		str[len++] = ch;
	}
 
	n = CreateBiTree(&T, str);
	if (n==1)
	{
		cout << "创建成功！" << endl;
	} 
	else
	{
		cout << "创建失败！" << endl;
	}
 
	DispBTNode(T);
 
	system("pause");
}
 
void DispBTNode(BiTree T)
{
	BitNode *qu[MAXSIZE];
	BitNode *p;
	int front, rear, n;
	n = 0;
	front = rear = 0;
	qu[rear++] = NULL;
	p = T;
	if (p!=NULL)
	{
		qu[rear++] = p;
	}
	do 
	{
		p = qu[front++];
		if (p==NULL)
		{
			qu[rear++] = NULL;
			n++;
			printf("\n");
		} 
		else
		{
			cout << "第" << n << "层：" << p->data << endl;
			if (p->lchild!=NULL)
			{
				qu[rear++] = p->lchild;
			}
			if (p->rchild!=NULL)
			{
				qu[rear++] = p->rchild;
			}
 
 
		}
	} while (front!=rear-1);
}

转载请注明：PHP开发日志 >> APP开发 » 广义表使用栈链构建二叉树