「Binary Tree」Extension

在普通的二叉树(链式结构)上增加了一些功能

bitree.h

typedef int Status;
typedef int TElemType;

typedef struct BiTNode {
    TElemType       data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

Status InitBiTree(BiTree *T);
Status DestroyBiTree(BiTree *T);
Status CreateBiTree(BiTree *T);
Status ClearBiTree(BiTree *T);
Status BiTreeEmpty(BiTree T);

Status PrintBiTree(BiTree T, int level);		//二叉树的输出(按层次缩进，且区分左右子树)
BiTree SearchBiTree(BiTree T, TElemType e);		//在二叉树中查找值为e的第1个结点(返回该结点的指针)
int    BiTreeDepth(BiTree T);				//求二叉树的高度(深度)
int    BiTreeCount(BiTree T);				//求二叉树中结点的数量
int    BiTreeCountLeaf(BiTree T);			//求二叉树中叶子结点的数量
Status BiTreeExchange(BiTree *T);			//二叉树左右子树互换(递归)
Status BiTreeCopy(BiTree T, BiTree *CT);		//二叉树的复制

/* 非递归方式实现各应用 */
Status PrintBiTree1(BiTree T, int level);		//二叉树的输出(按层次缩进，且区分左右子树)
BiTree SearchBiTree1(BiTree T, TElemType e);		//在二叉树中查找值为e的第1个结点(返回该结点的指针)
int    BiTreeDepth1(BiTree T);				//求二叉树的高度(深度)
int    BiTreeCount1(BiTree T);				//求二叉树中结点的数量
int    BiTreeCountLeaf1(BiTree T);			//求二叉树中叶子结点的数量
Status BiTreeExchange1(BiTree *T);			//二叉树左右子树互换(递归)
Status BiTreeCopy1(BiTree T, BiTree *CT);		//二叉树的复制

bitree.c

#include <stdio.h>
#include <stdlib.h>
#include "bitree.h"
#define MaxSize 40

/*--------------------递归方式实现------------------------*/
//二叉树的输出(按层次缩进，且区分左右子树)
Status PrintBiTree(BiTree T, int level)
{
	int i;
	static int flag = 0;
	if (T)
	{
		for (i = 1; i <= level; i++)
			printf("    ");
		printf("%d", T->data);
		if (level == 1)
			printf("(r)");
		else if (flag == 1)
			printf("(0)");
		else if (flag == 2)
			printf("(1)");
		for (i = 4 * level + 1; i <= MaxSize - (T->data) / 10; i++)
			printf("-");
		printf("\n");
		flag = 1;
		PrintBiTree(T->lchild, level + 1);
		flag = 2;
		PrintBiTree(T->rchild, level + 1);
	}
	return OK;
}

//在二叉树中查找值为e的第1个结点(返回该结点的指针)
BiTree SearchBiTree(BiTree T, TElemType e)
{
	BiTree tmp;
	if (T == NULL)
		return NULL;
	else
		if (T->data == e)
			return T;
	if ((tmp = SearchBiTree(T->lchild, e)) != NULL || (tmp = SearchBiTree(T->rchild, e)) != NULL)
		return tmp;
	return NULL;
}

//求二叉树的高度(深度)
int BiTreeDepth(BiTree T)
{
	if (T == NULL)
		return 0;

	int	lmax = BiTreeDepth(T->lchild);
	int	rmax = BiTreeDepth(T->rchild);
	return (lmax > rmax ? lmax : rmax) + 1;
}

//求二叉树中结点的数量
int BiTreeCount(BiTree T)
{
	if (T == NULL)
		return 0;
	return BiTreeCount(T->lchild) + BiTreeCount(T->rchild) + 1;
}

//求二叉树中叶子结点的数量
int BiTreeCountLeaf(BiTree T)
{
	if (T == NULL)
		return 0;
	if (T->lchild == NULL && T->rchild == NULL)
		return 1;
	return BiTreeCountLeaf(T->lchild) + BiTreeCountLeaf(T->rchild);
}

//二叉树左右子树互换
Status BiTreeExchange(BiTree *T)
{
	if ((*T) == NULL)
		return 0;
	BiTNode *p;
	p = (*T)->lchild;
	(*T)->lchild = (*T)->rchild;
	(*T)->rchild = p;
	BiTreeExchange(&((*T)->lchild));
	BiTreeExchange(&((*T)->rchild));

	return OK;
}

//二叉树的复制
Status BiTreeCopy(BiTree T, BiTree *CT)
{
	if (T == NULL)
	{
		(*CT) = NULL;
		return 0;
	}
	*CT = (BiTNode *)malloc(sizeof(BiTNode));
	(*CT)->data = T->data;
	BiTreeCopy(T->lchild, &((*CT)->lchild));
	BiTreeCopy(T->rchild, &((*CT)->rchild));
	return OK;
}


/*--------------------非递归方式实现------------------------*/
//二叉树的输出(按层次缩进，且区分左右子树)
Status PrintBiTree1(BiTree T, int level)
{
	BiTree stack[MaxSize], p;
	int num[MaxSize][2], top = 1, i, n, width = 4;
	char type;
	if (T != NULL)
	{
		stack[top] = T;
		num[top][0] = width;
		num[top][1] = 2;
		while (top > 0)
		{
			p = stack[top];
			n = num[top][0];
			switch (num[top][1])
			{
			case 0:
				type = '0';
				break;
			case 1:
				type = '1';
				break;
			case 2:
				type = 'r';
				break;
			}
			for (i = 1; i <= n; i++)
				printf(" ");
			printf("%d(%c)", p->data, type);
			for (i = n + 1; i <= MaxSize - (p->data) / 10; i++)
				printf("-");
			printf("\n");
			top--;
			if (p->rchild != NULL)
			{
				top++;
				stack[top] = p->rchild;
				num[top][0] = n + width;
				num[top][1] = 1;
			}
			if (p->lchild != NULL)
			{
				top++;
				stack[top] = p->lchild;
				num[top][0] = n + width;
				num[top][1] = 0;
			}
		}
	}
	return OK;
}

//在二叉树中查找值为e的第1个结点(返回该结点的指针)
BiTree SearchBiTree1(BiTree T, TElemType e)
{
	BiTree stack[MaxSize], p;
	int top = 0;

	p = T;
	while (p || top > 0)
	{
		if (p)
		{
			if (p->data == e)
				return p;

			if (p->rchild)
				stack[top++] = p->rchild;
			p = p->lchild;
		}
		else
			p = stack[--top];
	}
	return NULL;
}

//求二叉树的高度(深度)
int BiTreeDepth1(BiTree T)
{
	BiTree queue[MaxSize];
	int front = 0, rear = 0;
	int last = 1, level = 0;

	if (T == NULL)
		return OK;

	queue[++rear] = T;
	while (front != rear)
	{
		front = (front + 1) % MaxSize;
		if (queue[front]->lchild != NULL)
		{
			rear = (rear + 1) % MaxSize;
			queue[rear] = queue[front]->lchild;
		}
		if (queue[front]->rchild != NULL)
		{
			rear = (rear + 1) % MaxSize;
			queue[rear] = queue[front]->rchild;
		}
		if (front == last)
		{
			level++;
			last = rear;
		}
	}

	return level;
}

//求二叉树中结点的数量
int BiTreeCount1(BiTree T)
{
	BiTree stack[MaxSize], p;
	int top = 0, tot = 0;

	p = T;
	while (p || top > 0)
	{
		if (p)
		{
			tot++;

			if (p->rchild)
				stack[top++] = p->rchild;
			p = p->lchild;
		}
		else
			p = stack[--top];
	}
	return tot;
}

//求二叉树中叶子结点的数量
int BiTreeCountLeaf1(BiTree T)
{
	BiTree stack[MaxSize], p;
	int top = 0, tot = 0;

	p = T;
	while (p || top > 0)
	{
		if (p)
		{
			if (p->lchild == NULL&&p->rchild == NULL)
				tot++;

			if (p->rchild)
				stack[top++] = p->rchild;
			p = p->lchild;
		}
		else
			p = stack[--top];
	}
	return tot;
}

//二叉树左右子树互换
Status BiTreeExchange1(BiTree *T)
{
	if ((*T) == NULL)
		return 0;
	BiTree stack[MaxSize];
	int top = 0;
	stack[++top] = *T;
	
	while (top > 0)
	{
		BiTree p = stack[top--];
		if (p->lchild != NULL)
			stack[++top] = p->lchild;
		if (p->rchild != NULL)
			stack[++top] = p->rchild;
		BiTree tmp;
		tmp = p->lchild;
		p->lchild = p->rchild;
		p->rchild = tmp;
	}
	return OK;
}

//二叉树的复制
Status BiTreeCopy1(BiTree T, BiTree *CT)
{
	BiTree stack1[MaxSize], stack2[MaxSize], p1, p2;
	int top1 = 0, top2 = 0;

	(*CT) = (BiTNode *)malloc(sizeof(BiTNode));
	stack1[++top1] = T;
	stack2[++top2] = (*CT);
	while (top1 > 0)
	{
		p1 = stack1[top1--];
		p2 = stack2[top2--];
		p2->data = p1->data;

		if (p1->rchild)
		{
			stack1[++top1] = p1->rchild;
			p2->rchild = (BiTNode *)malloc(sizeof(BiTNode));
			stack2[++top2] = p2->rchild;
		}
		else
			p2->rchild = NULL;
		if (p1->lchild)
		{
			stack1[++top1] = p1->lchild;
			p2->lchild = (BiTNode *)malloc(sizeof(BiTNode));
			stack2[++top2] = p2->lchild;
		}
		else
			p2->lchild = NULL;
	}
	return OK;
}