博客

通过字符串（括号表示法）创建一个二叉树（C语言实现）

写在前面：该篇文章参考文献：数据结构教程（第五版） 李春葆 主编

实现步骤

假设采用括号表示法表示的二叉树字符串

str

是正确的，用

ch

扫描str，其中只有四类字符，其处理如下。

• 单个字符：结点的值
• （：表示一棵子树的开始
• ）：表示一棵子树的结束
• ，：表示一棵右子树的开始

算法设计

• 先构造
  
  根结点N
  
  ，再构造
  
  左子树L
  
  ,最后构造
  
  右子树R
  
• 构造
  
  右子树R
  
  时，找不到N了，所以需要保存N
• 而括号（子树）是按照最近原则匹配的，所以使用一个
  
  栈
  
  保存N

ch扫描采用括号表示法表示二叉树的字符串：



A(B(D(,G)),C(E,F))

1. 若ch=’
   
   (
   
   ’：表示前面刚创建的结点p存在孩子结点，需要将其进栈作为栈顶结点，并置空
   
   k=1
   
   ，表示开始处理左孩子结点；
2. 若ch=’
   
   )
   
   ’：表示栈顶结点的左右孩子结点处理完毕，退栈；
3. 若ch=’
   
   ，
   
   ’：表示开始处理右孩子结点，置
   
   k=2
   
   ；
4. 其他情况（结点值）：
   
   
   创建p
   
   结点用于存放ch
   
   当
   
   k=1
   
   时，将p作为栈顶元素的左孩子结点；
   
   当
   
   k=2
   
   时，将p作为栈顶元素的右孩子结点；

源代码

头文件 btree.h

#pragma once
typedef char ElemType;

typedef struct node {
	ElemType data;		//数据元素
	struct node *lchild;	//指向左孩子的结点
	struct node *rchild;	//指向右孩子的结点
}BTNode;

函数实现 btree.cpp

#include<iostream>
#define MaxSize 20   //最大结点数
#include"btree.h"

void CreateBTree(BTNode *&b, char *str)
{
	BTNode *St[MaxSize], *p;   //St数组作为顺序栈，保存双亲结点
	int top = -1, k, i= 0;		//top为栈顶指针
	char ch;
	b = NULL;		//初始时二叉链为空
	ch = str[i];
	while (ch != '\0')		//循环处理，直到str中的每个字符扫描完毕
	{
		switch (ch)
		{
		case '(':top++; St[top] = p; k = 1; break;		//开始处理左孩子结点
		case ')':top--;  break;							//栈顶结点的子树处理完毕
		case ',': k = 2; break;							//开始处理右孩子结点
		default:
			p = (BTNode *)malloc(sizeof(BTNode));		//创建一个结点由p指向它
			p->data = ch;								//存放结点值
			p->lchild = p->rchild = NULL;				//左右指针都设置为空
			if (b == NULL)					//尚未设置根结点
				b = p;						//p作为根结点
			else
			{
				switch (k)
				{
				case 1:St[top]->lchild = p; break;		//新建结点作为栈顶结点的左孩子
				case 2:St[top]->rchild = p; break;		//新建结点作为栈顶结点的右孩子
				}
			}
		}
		i++;
		ch = str[i];
	}
}

补充：关于二叉树的其他基本算法代码

/*销毁二叉树:释放二叉树b的所有结点分配的空间*/
void DestoryBTree(BTNode *&b) 
{
	if (b != NULL)
	{ 
		DestoryBTree(b->lchild);
	    DestoryBTree(b->rchild);
		free(b);
    }
}

/*查找结点：在二叉树b中查找值为x的结点，找到后返回其地址，否则返回NULL*/
BTNode *FindNode(BTNode *b, ElemType x)
{
	BTNode *p;
	if (b == NULL)
		return NULL;
	else if (b->data == x)
		return b;
	else 
	{
		p = FindNode(b->lchild, x);
		if (p != NULL)
			return p;
		else
			return FindNode(b->rchild, x);
	}
}


/*找孩子结点：直接返回结点p的左孩子或者右孩子地址*/
BTNode *LchildNode(BTNode *p)		//返回结点p的左孩子指针
{
	return p->lchild;
}

BTNode *RchildNode(BTNode *p)		//返回结点p的右孩子指针
{
	return p->rchild;
}

/*求二叉树的高度：返回二叉树的高度*/
int BTHeight(BTNode *b) 
{
	int lchildh, rchildh;
	if (b == NULL) return 0;		//空树高度为0
	else
	{
		lchildh = BTHeight(b->lchild);		//求左子树的高度
		rchildh = BTHeight(b->rchild);		//求右子树的高度
		return (lchildh > rchildh) ? (lchildh + 1) : (rchildh + 1);
	}
}

/*输出二叉树：输出创建二叉树时输入的字符串*/
void DispBTree(BTNode *b)
{
	if (b != NULL)
	{
		printf("%c", b->data);
		if (b->lchild != NULL || b->rchild != NULL)
		{
			printf("(");
			DispBTree(b->lchild);
			if (b->rchild != NULL)
				printf(",");
			DispBTree(b->rchild);
			printf(")");
		}
	}
}