1355 - 算法6-1~6-4：二叉链表存储的二叉树

游客注册 | 登录

中文 | En

1355 - 算法6-1~6-4：二叉链表存储的二叉树

通过次数

提交次数

旧版界面

时间限制 : 1 秒内存限制 : 32 MB

树形结构是一类重要的非线性数据结构，其中以树和二叉树最为常用。对于每一个结点至多只有两课子树的一类树，称其为二叉树。二叉树的链式存储结构是一类重要的数据结构，其形式定义如下：

<span style="font-family:宋体;">而二叉树的前序、中序遍历是非常重要的能够访问二叉树所有结点的算法，下面分别列出一种先序遍历和两种中序遍历的算法。</span>

<img src="http://tk.hustoj.com:80/upload/pimg1757_2.png" width="581" height="160" alt="" />

<span style="font-family:宋体;">第一种中序遍历的方法（算法</span><span>6.3</span><span style="font-family:宋体;">）：</span>

<img src="http://tk.hustoj.com:80/upload/pimg1757_3.png" width="566" height="342" alt="" />

<span style="font-family:宋体;">第二种中序遍历的方法（算法</span><span>6.2</span><span style="font-family:宋体;">）：</span>

<img src="http://tk.hustoj.com:80/upload/pimg1757_4.png" width="568" height="360" alt="" />

<span style="font-family:宋体;">通过读入一个字符串，建立二叉树的算法如下：</span>

<img src="http://tk.hustoj.com:80/upload/pimg1757_5.png" width="579" height="268" alt="" />

<span style="font-family:宋体;">在本题中，将会给出一个按照先序遍历得出的字符串，空格代表空的子节点，大写字母代表节点内容。请通过这个字符串建立二叉树，并按照题目描述中的一种先序遍历和两种中序遍历的算法分别输出每一个非空节点。</span>

<span></span>

<span></span>

<span></span>

<span></span>

题目输入

输入只有一行，包含一个字符串S，用来建立二叉树。保证S为合法的二叉树先序遍历字符串，节点内容只有大写字母，且S的长度不超过100。

题目输出

共有三行，每一行包含一串字符，表示分别按先序、中序、中序得出的节点内容，每个字母后输出一个空格。请注意行尾输出换行。

输入/输出样例

输入格式

ABC  DE G  F

输出格式

A B C D E G F 
C B E G D F A 
C B E G D F A

C语言解答

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -1
#define STACK_INIT_SIZE 10 /* 存储空间初始分配量 */
#define STACKINCREMENT 2 /* 存储空间分配增量 */
typedef int Status; /* 函数结果状态代码,如OK等 */
typedef char TElemType;
typedef struct BiTNode {
        TElemType data;
        struct BiTNode *lchild,*rchild; /* 左右孩子指针 */
}BiTNode,*BiTree;
typedef BiTree SElemType; /* 设栈元素为二叉树的指针类型 */
typedef struct SqStack {
        SElemType *base; /* 在栈构造之前和销毁之后，base的值为NULL */
        SElemType *top; /* 栈顶指针 */
        int stacksize; /* 当前已分配的存储空间，以元素为单位 */
}SqStack; /* 顺序栈 */
TElemType Nil=' '; /* 字符型以空格符为空 */
Status InitStack(SqStack *S) { /* 构造一个空栈S */
        (*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
        if(!(*S).base) exit(OVERFLOW); /* 存储分配失败 */
        (*S).top=(*S).base;
        (*S).stacksize=STACK_INIT_SIZE;
        return OK;
}
Status StackEmpty(SqStack S) { /* 若栈S为空栈，则返回TRUE，否则返回FALSE */
        if(S.top==S.base)
                return TRUE;
        else
                return FALSE;
}
Status Push(SqStack *S,SElemType e) { /* 插入元素e为新的栈顶元素 */
        if((*S).top-(*S).base>=(*S).stacksize) { /* 栈满，追加存储空间 */
                (*S).base=(SElemType *)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType));
                if(!(*S).base) exit(OVERFLOW); /* 存储分配失败 */
                (*S).top=(*S).base+(*S).stacksize;
                (*S).stacksize+=STACKINCREMENT;
        }
        *((*S).top)++=e;
        return OK;
}
Status Pop(SqStack *S,SElemType *e) {
/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
        if((*S).top==(*S).base) return ERROR;
        *e=*--(*S).top;
        return OK;
}
Status GetTop(SqStack S,SElemType *e) {
/* 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR */
        if(S.top>S.base) {
                *e=*(S.top-1);
                return OK;
        } else
                return ERROR;
}
Status InitBiTree(BiTree *T) { /* 操作结果: 构造空二叉树T */
        *T=NULL;
        return OK;
}
void CreateBiTree(BiTree *T) {
/* 算法6.4:按先序次序输入二叉树中结点的值（可为字符型或整型，在主程序 */
/* 中定义），构造二叉链表表示的二叉树T。变量Nil表示空（子）树。 */
        TElemType ch;
        scanf("%c",&ch);
        if(ch==Nil) { /* 空 */
                *T=NULL;
        } else {
                *T=(BiTree)malloc(sizeof(BiTNode));
                if(!*T) exit(OVERFLOW);
                (*T)->data=ch; /* 生成根结点 */
                CreateBiTree(&(*T)->lchild); /* 构造左子树 */
                CreateBiTree(&(*T)->rchild); /* 构造右子树 */
        }
}
Status visitT(TElemType e) {
        printf("%c ",e);
        return OK;
}
void PreOrderTraverse(BiTree T,Status(*Visit)(TElemType)) {
/* 初始条件: 二叉树T存在,Visit是对结点操作的应用函数。算法6.1，有改动 */
/* 操作结果: 先序递归遍历T,对每个结点调用函数Visit一次且仅一次 */
        if(T) { /* T不空 */
                Visit(T->data); /* 先访问根结点 */
                PreOrderTraverse(T->lchild,Visit); /* 再先序遍历左子树 */
                PreOrderTraverse(T->rchild,Visit); /* 最后先序遍历右子树 */
        }
}
Status InOrderTraverse1(BiTree T,Status(*Visit)(TElemType)) {
/* 采用二叉链表存储结构，Visit是对数据元素操作的应用函数。算法6.3 */
/* 中序遍历二叉树T的非递归算法(利用栈)，对每个数据元素调用函数Visit */
        SqStack S;
        InitStack(&S);
        while(T||!StackEmpty(S)) {
                if(T) { /* 根指针进栈,遍历左子树 */
                        Push(&S,T);
                        T=T->lchild;
                } else { /* 根指针退栈,访问根结点,遍历右子树 */
                        Pop(&S,&T);
                        if(!Visit(T->data))
                        return ERROR;
                        T=T->rchild;
                }
        }
        printf("\n");
        return OK;
}
Status InOrderTraverse2(BiTree T,Status(*Visit)(TElemType)) {
/* 采用二叉链表存储结构，Visit是对数据元素操作的应用函数。算法6.2 */
/* 中序遍历二叉树T的非递归算法(利用栈)，对每个数据元素调用函数Visit */
        SqStack S;
        BiTree p;
        InitStack(&S);
        Push(&S,T); /* 根指针进栈 */
        while(!StackEmpty(S)) {
                while(GetTop(S,&p)&&p)
                        Push(&S,p->lchild); /* 向左走到尽头 */
                Pop(&S,&p); /* 空指针退栈 */
                if(!StackEmpty(S)) { /* 访问结点,向右一步 */
                        Pop(&S,&p);
                        if(!Visit(p->data)) return ERROR;
                        Push(&S,p->rchild);
                }
        }
        printf("\n");
        return OK;
}
int main() {
        int i;
        BiTree T,p,c;
        TElemType e1,e2;
        InitBiTree(&T);
        CreateBiTree(&T);
        PreOrderTraverse(T,visitT); puts("");
        InOrderTraverse1(T,visitT);
        InOrderTraverse2(T,visitT);
        return 0;
}

C++解答

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -1
#define STACK_INIT_SIZE 10 /* 存储空间初始分配量 */
#define STACKINCREMENT 2 /* 存储空间分配增量 */
typedef int Status; /* 函数结果状态代码,如OK等 */
typedef char TElemType;
typedef struct BiTNode {
	TElemType data;
	struct BiTNode *lchild,*rchild; /* 左右孩子指针 */
}BiTNode,*BiTree;
typedef BiTree SElemType; /* 设栈元素为二叉树的指针类型 */
typedef struct SqStack {
	SElemType *base; /* 在栈构造之前和销毁之后，base的值为NULL */
	SElemType *top; /* 栈顶指针 */
	int stacksize; /* 当前已分配的存储空间，以元素为单位 */
}SqStack; /* 顺序栈 */
TElemType Nil=' '; /* 字符型以空格符为空 */
Status InitStack(SqStack *S) { /* 构造一个空栈S */
	(*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
	if(!(*S).base) exit(OVERFLOW); /* 存储分配失败 */
	(*S).top=(*S).base;
	(*S).stacksize=STACK_INIT_SIZE;
	return OK;
}
Status StackEmpty(SqStack S) { /* 若栈S为空栈，则返回TRUE，否则返回FALSE */
	if(S.top==S.base)
		return TRUE;
	else
		return FALSE;
}
Status Push(SqStack *S,SElemType e) { /* 插入元素e为新的栈顶元素 */
	if((*S).top-(*S).base>=(*S).stacksize) { /* 栈满，追加存储空间 */
		(*S).base=(SElemType *)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType));
		if(!(*S).base) exit(OVERFLOW); /* 存储分配失败 */
		(*S).top=(*S).base+(*S).stacksize;
		(*S).stacksize+=STACKINCREMENT;
	}
	*((*S).top)++=e;
	return OK;
}
Status Pop(SqStack *S,SElemType *e) {
/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
	if((*S).top==(*S).base) return ERROR;
	*e=*--(*S).top;
	return OK;
}
Status GetTop(SqStack S,SElemType *e) {
/* 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR */
	if(S.top>S.base) {
		*e=*(S.top-1);
		return OK;
	} else
		return ERROR;
}
Status InitBiTree(BiTree *T) { /* 操作结果: 构造空二叉树T */
	*T=NULL;
	return OK;
}
void CreateBiTree(BiTree *T) {
/* 算法6.4:按先序次序输入二叉树中结点的值（可为字符型或整型，在主程序 */
/* 中定义），构造二叉链表表示的二叉树T。变量Nil表示空（子）树。 */
	TElemType ch;
	scanf("%c",&ch);
	if(ch==Nil) { /* 空 */
		*T=NULL;
	} else {
		*T=(BiTree)malloc(sizeof(BiTNode));
		if(!*T) exit(OVERFLOW);
		(*T)->data=ch; /* 生成根结点 */
		CreateBiTree(&(*T)->lchild); /* 构造左子树 */
		CreateBiTree(&(*T)->rchild); /* 构造右子树 */
	}
}
Status visitT(TElemType e) {
	printf("%c ",e);
	return OK;
}
void PreOrderTraverse(BiTree T,Status(*Visit)(TElemType)) {
/* 初始条件: 二叉树T存在,Visit是对结点操作的应用函数。算法6.1，有改动 */
/* 操作结果: 先序递归遍历T,对每个结点调用函数Visit一次且仅一次 */
	if(T) { /* T不空 */
		Visit(T->data); /* 先访问根结点 */
		PreOrderTraverse(T->lchild,Visit); /* 再先序遍历左子树 */
		PreOrderTraverse(T->rchild,Visit); /* 最后先序遍历右子树 */
	}
}
Status InOrderTraverse1(BiTree T,Status(*Visit)(TElemType)) {
/* 采用二叉链表存储结构，Visit是对数据元素操作的应用函数。算法6.3 */
/* 中序遍历二叉树T的非递归算法(利用栈)，对每个数据元素调用函数Visit */
	SqStack S;
	InitStack(&S);
	while(T||!StackEmpty(S)) {
		if(T) { /* 根指针进栈,遍历左子树 */
			Push(&S,T);
			T=T->lchild;
		} else { /* 根指针退栈,访问根结点,遍历右子树 */
			Pop(&S,&T);
			if(!Visit(T->data))
			return ERROR;
			T=T->rchild;
		}
	}
	printf("\n");
	return OK;
}
Status InOrderTraverse2(BiTree T,Status(*Visit)(TElemType)) {
/* 采用二叉链表存储结构，Visit是对数据元素操作的应用函数。算法6.2 */
/* 中序遍历二叉树T的非递归算法(利用栈)，对每个数据元素调用函数Visit */
	SqStack S;
	BiTree p;
	InitStack(&S);
	Push(&S,T); /* 根指针进栈 */
	while(!StackEmpty(S)) {
		while(GetTop(S,&p)&&p)
			Push(&S,p->lchild); /* 向左走到尽头 */
		Pop(&S,&p); /* 空指针退栈 */
		if(!StackEmpty(S)) { /* 访问结点,向右一步 */
			Pop(&S,&p);
			if(!Visit(p->data)) return ERROR;
			Push(&S,p->rchild);
		}
	}
	printf("\n");
	return OK;
}
int main() {
	int i;
	BiTree T,p,c;
	TElemType e1,e2;
	InitBiTree(&T);
	CreateBiTree(&T);
	PreOrderTraverse(T,visitT); puts("");
	InOrderTraverse1(T,visitT);
	InOrderTraverse2(T,visitT);
	return 0;
}

上一题下一题提示代码讨论统计