二叉树创建的两种方法（图解）_数据结构pta6-4 括号表示法创建二叉树

       

目录

一、括号表示法

（1）括号表示法构建二叉树的算法思路及算法实现

（2）图解括号表示法构建二叉树

（3）测试程序

 二、扩展二叉树

（1）扩展二叉树构建二叉树的算法思路及算法实现

（2）测试程序

---

        二叉树的创建方法有很多种，在这里我介绍两种：用括号表示法或扩展二叉树来创建二叉树。

一、括号表示法

（1）括号表示法构建二叉树的算法思路及算法实现

        扩号表示法（本质广义表）是树的一种表示。它的表示方法：将树的根结点写在括号的左边，除根结点之外的其余结点写在扩号中，并用逗号隔开。如下图：

解释：

1、A是根结点，写在扩号左边，其左右孩子为B，C，写成A(B,C)

2、B又是D、E的双亲结点（相当于B、D、E构成的树，B为根结点），故写成 B(D,E)，带入上面A(B(D,E),C)

3、E有左孩子，但无右孩子，故写成E(G,)，带入得A(B(D,E(G,)),C)

4、C有右孩子，但无左孩子，写成C(,F)，带入得A(B(D,E(G,)),C(,F))

总结：这种写法总的来说就是，树根(左子树，右子树)，其中左子树又有左子树和右子树，同样右子树有左子树和右子树，一直递归下去，直到叶子结点。

        那怎么是用括号表示法的字符序列（上图的A(B(D,E(G,)),C(,F))） 创建二叉树，其算法思路如下：

（1）用str获取括号表示法表示二叉树的字符串

（2）用ch扫描str

（3）ch = '(' ，则将前面刚创建的结点作为双亲结点入栈，并置k = 1，表示其后创建的结点将作为这个结点的左孩子

（4）ch = ',' ，置k = 2，表示其后创建的结点为右孩子结点。

（5）ch = ')'，表示栈顶元素的左右孩子结点处理完毕，出栈。

（6）其它情况创建一个结点，并根据 k 值，判断这个结点是栈中栈顶元素的左孩子还是右孩子，进行链接。

（7）一直循环下去直至str处理完成。

算法实现：

/*栈的存储结构*/
typedef struct Stack
{
	BiTree data[Maxsize]; // 存放栈中元素
	int top;		// 栈顶指针
}SqStack;

/*树的存储结构二叉链表*/
typedef struct BiTNode
{
	Elemtype data;
	struct BiTNode* lchild, * rchild;
}BiTNode, * BiTree;

/*初始化栈*/
void InitStack(SqStack* S)
{
	S->top = -1;
}

/*入栈*/
bool Push(SqStack* S, BiTree x)
{
	if (S->top == Maxsize - 1)   // 栈满
		return false;
	S->data[++(S->top)] = x;
	return true;
}

/*出栈*/
bool Pop(SqStack* S, BiTree* x)
{
	if (S->top == -1) // 栈空
		return false;
	*x = S->data[(S->top)--];
	return true;
}

/*利用广义表构建二叉树*/
void CreateBiTree2(BiTree* T, char* str)
{
	SqStack S;			// 辅助栈
	BiTree p = NULL, x;	// 辅助指针
	InitStack(&S);		// 初始化栈
	char ch;
	int i = 0, k;
	ch = str[i];
	while (ch != '\0')  // str未扫描完时循环
	{
		switch (ch)
		{
			case '(': Push(&S, p);		// 入栈，准备链接左孩子
				      k = 1;
					  break;
			case ')': Pop(&S, &x);		// 出栈
					  break;
			case ',': k = 2;			// 准备链接右孩子
				      break;
			default: 
				p = (BiTree)malloc(sizeof(BiTNode));
				p->data = ch; p->lchild = p->rchild = NULL;
				if ((*T) == NULL)		// p为二叉树的根结点
					(*T) = p;
				else					// 已建立二叉树的根结点,根据k值链接左孩子还是右孩子
				{
					switch (k)
					{
						case 1: S.data[S.top]->lchild = p; break; // 链接左孩子
						case 2: S.data[S.top]->rchild = p; break; // 链接右孩子
					}
				}
		}
		i++;
		ch = str[i]; // 继续扫描str
	}
}

（2）图解括号表示法构建二叉树

        我们用上图的括号表示法的字符串（A(B(D,E(G,)),C(,F))）来构建二叉树：

首先扫描到的A直接是其它情况，构建一个结点，并将A赋值给data，且创建的结点赋值给根结点T（由于刚开始树为空即T=NULL）

 下一次扫描为 ( , A入栈，并且 k = 1（为A链接左孩子左准备），再次扫描下一个字符：

扫描的字符为B，创建结点并赋值，此时T != NULL（执行else语句块），根据 k = 1，栈顶元素（A）链接左孩子（即B）

扫描到 ( , 执行B入栈，k = 1

扫描到 D，创建结点赋值，然后根据 k = 1，栈顶（B）将D作为左孩子进行链接

 扫描到 , ，k = 2，为栈顶元素（B）链接右孩子做准备 

然后接着扫描，扫描到E，创建结点并赋值，根据 k = 2，将C作为右孩子，链接到栈顶元素(B）

 扫描到 ( , 将E入栈，k = 1

扫描到 G，创建结点并赋值，根据 k = 1，将G作为左孩子，链接到栈顶元素（E）

 扫描到 ，，k = 2，接着扫描

扫描到 )，栈顶元素（E）退栈，此时栈中有 B、A

又扫描到 ），栈顶元素（B）退栈，此时栈只有 A

扫描到，， k = 2，接着扫描 

扫描到C，创建结点并赋值，根据 k = 2，C作为右孩子链接到栈顶元素（A）

扫描到 ( ，C入栈 k = 1

扫描到 ，k = 2，继续扫描

扫描到 F，创建节点并赋值，根据 k = 2，F作为右孩子链接到栈顶元素（C）

扫描到 (，进行退栈

 又扫描到（，进行退栈 

 至此，扫描结束，栈为空，二叉树构建完成。

（3）测试程序

// 输入 A(B(D,E(G,)),C(,F))
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
 
#define Maxsize 100
 
typedef char Elemtype;
 
/*树的存储结构二叉链表*/
typedef struct BiTNode
{
	Elemtype data;
	struct BiTNode* lchild, * rchild;
}BiTNode, * BiTree;
 
/*栈的存储结构*/
typedef struct Stack
{
	BiTree data[Maxsize]; // 存放栈中元素
	int top;		// 栈顶指针
}SqStack;
 
/*初始化栈*/
void InitStack(SqStack* S);
/*入栈*/
bool Push(SqStack* S, BiTree x);
/*出栈*/
bool Pop(SqStack* S, BiTree* x);
 
/*利用广义表构建二叉树*/
void CreateBiTree2(BiTree* T, char* str2);
 
/*先序遍历*/
void PreOrder(BiTree T);
 
/*输出树结点*/
void visit(BiTree T);
 
/*以广义表输出二叉树*/
void DispBiTree(BiTree T);
 
/*获取一个由二叉树构成的广义表字符*/
void GetStr(char* str);
 
int main(void)
{
	BiTree T = NULL;
	char str[50];
	GetStr(str);
	CreateBiTree2(&T, str);
	printf("二叉树的先序遍历：\n");
	PreOrder(T);
	printf("二叉树的括号表示法：");
	DispBiTree(T);
	return 0;
}
 
/*初始化栈*/
void InitStack(SqStack* S)
{
	S->top = -1;
}
 
/*入栈*/
bool Push(SqStack* S, BiTree x)
{
	if (S->top == Maxsize - 1)   // 栈满
		return false;
	S->data[++(S->top)] = x;
	return true;
}
 
/*出栈*/
bool Pop(SqStack* S, BiTree* x)
{
	if (S->top == -1) // 栈空
		return false;
	*x = S->data[(S->top)--];
	return true;
}
 
/*利用广义表构建二叉树*/
void CreateBiTree2(BiTree* T, char* str)
{
	SqStack S;			// 辅助栈
	BiTree p = NULL, x;	// 辅助指针
	InitStack(&S);		// 初始化栈
	char ch;
	int i = 0, k;
	ch = str[i];
	while (ch != '\0')  // str未扫描完时循环
	{
		switch (ch)
		{
		case '(': Push(&S, p);		// 入栈,准备链接左孩子
			k = 1;
			break;
		case ')': Pop(&S, &x);		// 出栈
			break;
		case ',': k = 2;			// 准备链接右孩子结点
			break;
		default:
			p = (BiTree)malloc(sizeof(BiTNode));
			p->data = ch; p->lchild = p->rchild = NULL;
			if ((*T) == NULL)		// p为二叉树的根结点
				(*T) = p;
			else					// 已建立二叉树的根结点,根据k值链接左孩子还是右孩子
			{
				switch (k)
				{
				case 1: S.data[S.top]->lchild = p; break; // 链接左孩子
				case 2: S.data[S.top]->rchild = p; break; // 链接右孩子
				}
			}
		}
		i++;
		ch = str[i]; // 继续扫描str
	}
}
 
/*先序遍历*/
void PreOrder(BiTree T)
{
	if (T != NULL)
	{
		visit(T);
		PreOrder(T->lchild);
		PreOrder(T->rchild);
	}
}
 
/*输出树结点*/
void visit(BiTree T)
{
	printf("树结点的值：%c\n", T->data);
}
 
/*获取一个由二叉树构成的广义表字符*/
void GetStr(char* str)
{
	printf("请输入由二叉树构成的广义表字符串：");
	scanf("%s", str);
}
 
/*以广义表输出二叉树*/
void DispBiTree(BiTree T)
{
	if (T != NULL)
	{
		printf("%c", T->data);
		if (T->lchild != NULL || T->rchild != NULL) //左右子树不为空
		{
			printf("(");
			DispBiTree(T->lchild);					// 递归处理左子树
			if (T->rchild != NULL)
				printf(",");
			DispBiTree(T->rchild);					//递归处理右子树
			printf(")");
		}
	}
}

 二、扩展二叉树

（1）扩展二叉树构建二叉树的算法思路及算法实现

        扩展二叉树：将二叉树中的每个结点的空指针引出一个虚结点，其值为一特值，比如"#"，这种处理后的二叉树为原二叉树的扩展树。扩展二叉树就可以做到一个遍历序列确定一颗二叉树。如下图（前序遍历扩展二叉树，介绍的也是这种）：

         上图扩展二叉树的前序序列为：ABD##EG###C#F##.

总结：将二叉树变为扩展二叉树，就是将原二叉树的每一个一件的度都变为2，即都有左、右孩子。

 算法思路：

（1）当 ch = '#'，构建空指针，即（*T = NULL）

（2）ch != '#' ，创建新结点赋值，并进行递归构造左、右子树

算法实现：

/*树的存储结构二叉链表*/
typedef struct BiTNode
{
	Elemtype data;
	struct BiTNode* lchild, * rchild;
}BiTNode, * BiTree;

/*利用一个前序遍历的扩展二叉树的字符串序列*/
void CreateBiTree1(BiTree* T)
{
	Elemtype ch;
 
	scanf("%c", &ch); //获取前序遍历的扩展二叉树的字符串的一个字符
 
	if (ch == '#')
		*T = NULL; // 空树结点
	else
	{
		*T = (BiTree)malloc(sizeof(BiTNode));
		if (!*T)  // 未分配到空间
			exit(false);
		(*T)->data = ch;	// 生成根结点
		(*T)->lchild = (*T)->rchild = NULL;
		CreateBiTree1(&(*T)->lchild); // 构造左子树
		CreateBiTree1(&(*T)->rchild); // 构造右子树
	}
}

（2）测试程序

// 输入 ABD##EG###C#F##
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
 
#define Maxsize 100
 
typedef char Elemtype;
 
/*树的存储结构二叉链表*/
typedef struct BiTNode
{
	Elemtype data;
	struct BiTNode* lchild, * rchild;
}BiTNode, * BiTree;
 
/*利用一个前序遍历的扩展二叉树的字符串序列*/
void CreateBiTree1(BiTree* T);
 
/*先序遍历*/
void PreOrder(BiTree T);
 
/*输出树结点*/
void visit(BiTree T);
 
int main(void)
{
	BiTree T = NULL;
	printf("请输入前序遍历的扩展二叉树的字符序列：");
	CreateBiTree1(&T);
	printf("二叉树的先序遍历：\n");
	PreOrder(T);
	return 0;
}
 
/*利用一个前序遍历的扩展二叉树的字符串序列*/
void CreateBiTree1(BiTree* T)
{
	Elemtype ch;
 
	scanf("%c", &ch); //获取前序遍历的扩展二叉树的字符串的一个字符
 
	if (ch == '#')
		*T = NULL; // 空树结点
	else
	{
		*T = (BiTree)malloc(sizeof(BiTNode));
		if (!*T)  // 未分配到空间
			exit(false);
		(*T)->data = ch;	// 生成根结点
		(*T)->lchild = (*T)->rchild = NULL;
		CreateBiTree1(&(*T)->lchild); // 构造左子树
		CreateBiTree1(&(*T)->rchild); // 构造右子树
	}
}
 
/*先序遍历*/
void PreOrder(BiTree T)
{
	if (T != NULL)
	{
		visit(T);
		PreOrder(T->lchild);
		PreOrder(T->rchild);
	}
}
 
/*输出树结点*/
void visit(BiTree T)
{
	printf("树结点的值：%c\n", T->data);
}