数据结构实验4--树和二叉树

本系列文章广泛借鉴了各种教材和博客文章，由于完成时间比较久远，如果有遗漏标注的请联系我补充或删除解答。本文中解答仅供参考学习。

其他章节实验见：分类 - 数据结构 - Loststar’s blog

文档要求以下问题要求统一在一个大程序里解决。

定义

#define OK 1
#define ERROR 0	
#define OVERFLOW 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef int TElemType;
typedef char Elem;
typedef struct s_BiTNode
{
	TElemType		data;
	struct s_BiTNode	*lchild, *rchild;
} BiTNode, *BiTree;

按先序遍历的扩展序列建立二叉树的存储结构

Status Create(BiTree &Tree)
{
	TElemType el;
	printf("input:");
	scanf("%d", &el);
	if (el == 0)
		Tree = NULL;
	else
	{
		if (!(Tree = (BiTree)malloc(sizeof(BiTNode))))
			exit(OVERFLOW);
		Tree->data = el;	//先根
		Create(Tree->lchild);	//次左
		Create(Tree->rchild);	//后右
	}
	return (OK);
}

二叉树先序、中序、后序遍历的递归算法

先序

void Preorder(BiTree Tree) 
{	//先序遍历
	if (Tree) {
		printf("%d", Tree->data);
		Preorder(Tree->lchild);
		Preorder(Tree->rchild);
	}
}

中序

void Inorder(BiTree Tree) 
{	//中序遍历
	if (Tree) {
		Inorder(Tree->lchild);
		printf("%d", Tree->data);
		Inorder(Tree->rchild);
	}
}

后序

void Postorder(BiTree Tree) 
{	//后序遍历
	if (Tree) {
		Postorder(Tree->lchild);
		Postorder(Tree->rchild);
		printf("%d", Tree->data);
	}
}

二叉树中序遍历的非递归算法

直接用 STL 的栈也行

//栈的简易实现
BiTree stack[1024] = { NULL };
int stackFlag = -1;
void stackPush(BiTree Tree)
{
	if (stackFlag < 1024)
	{
		stackFlag++;
		stack[stackFlag] = Tree;
	}
}
BiTree stackPop()
{
	stackFlag--;
	return stack[stackFlag + 1];
}
int isStackEmpty()
{
	return stackFlag == -1 ? 1 : 0;
}

void Inorder2(BiTree Tree)
{	//非递归中序遍历
	BiTree p = Tree;
	while (p || !isStackEmpty())
	{
		if (p)
		{
			stackPush(p);
			p = p->lchild;
		}
		else
		{
			p = stackPop();
			printf("%d", p->data);
			p = p->rchild;
		}
	}
}

二叉树层次遍历的非递归算法

直接用 STL 的队列也行

//队列的简易实现
BiTree queue[1024] = { NULL };
int queueFlag = -1;
void queuePush(BiTree Tree)
{
	if (queueFlag < 1024)
	{
		queueFlag++;
		queue[queueFlag] = Tree;
	}
}

BiTree queuePop()
{
	BiTree head = queue[0];
	for (int i = 1; i <= queueFlag; i++)
	{
		queue[i - 1] = queue[i];
	}
	queueFlag--;
	return head;
}

int isEmptyQueue()
{
	return queueFlag == -1 ? 1 : 0;
}

void Levelorder(BiTree Tree)
{
	BiTree p = Tree;
	queuePush(p);
	while (!isEmptyQueue())
	{
		p = queuePop();
		printf("%d", p->data);
		if (p->lchild)
		{
			queuePush(p->lchild);
		}
		if (p->rchild)
		{
			queuePush(p->rchild);
		}
	}
}

求二叉树的深度(后序遍历)

int Depth(BiTree Tree)
{
	int depth,ldepth,rdepth;
	if (!Tree)
	{
		depth = 0;
	}
	else
	{
		ldepth = Depth(Tree->lchild);
		rdepth = Depth(Tree->rchild);
		depth = 1 + (ldepth > rdepth ? ldepth : rdepth);
	}
	return depth;
}

求树的深度

int CSTreeDepth(CSTree T)
{
	if (!T)
		return 0;
	if (!T->firstchild)	//无长子
		return 1;
	CSTree p;
	int depth, max = 0;
	p = T->firstchild;
	while (p)
	{
		depth = CSTreeDepth(p);
		if (depth > max)
			max = depth;
		p = p->nextsibling;
	}
	return max + 1;	//当前层的下一层
}