tree.c

ADT BinaryTree 的实现及验证程序采用的主要数据结构：二叉树、栈、队算法思想：1、 先序建树、输出树、后序遍历用递归方法。性能分析：O( n )2、 先序遍历、中序遍历：性能分析：O( n

#include <stdio.h>
#include <stdlib.h>

//ADT tree
typedef struct BiTNode{
	char data;
	struct BiTNode *l, *r;
	struct BiTNode *fw, *bw;
}BiTNode, *BiTree;

void CreateBiTree(BiTree *T);
void PreOrderTraverse(BiTree T, int(*Visit)(BiTree));
void InOrderTraverse(BiTree T, int(*Visit)(BiTree));
void PostOrderTraverse(BiTree T, int(*Visit)(BiTree));
void LevelOrderTraverse(BiTree T, int(*Visit)(BiTree));
void PreOrderThreading(BiTree T);
void InOrderThreading(BiTree T);
//End ADT tree

int PrintElement(BiTree);
void PrintTree(BiTree T, int D);

//Stack
typedef struct StackNode{
	BiTree E;
	struct StackNode *next;
}StackNode;

typedef struct Stack{
	StackNode *top;
}Stack;

void Push(Stack *S, BiTree E);
BiTree Pop(Stack *S);
int InitStack(Stack *S);
int IsEmpty(Stack *S);
BiTree GetTop(Stack *S);
//End Stack

//Queue
typedef struct QueueNode{
	BiTree E;
	struct QueueNode *next;
}QueueNode;
typedef struct Queue{
	QueueNode *front;
	QueueNode *rear;
}Queue;
void EnQueue(Queue *Q, BiTree E);
BiTree OutQueue(Queue *Q);
int InitQueue(Queue *Q);
//End Queue

//------------------------------
int InitStack(Stack *S)
{
	S->top = NULL;
}
void Push(Stack *S, BiTree E)
{
	StackNode *n;
	n = (StackNode *)malloc(sizeof(StackNode));
	n->E = E;
	n->next = S->top;
	S->top = n;
}
BiTree Pop(Stack *S)
{
	BiTree temp;
	temp = S->top->E;
	S->top = S->top->next;
	return temp;
}
int IsEmpty(Stack *S)
{
	if(S->top) return 0;
	else return 1;
}
BiTree GetTop(Stack *S)
{
	return S->top->E;
}
//------------------------------
void EnQueue(Queue *Q, BiTree E)
{
	QueueNode *n;
	n = (QueueNode *)malloc(sizeof(QueueNode));
	n->E = E;
	n->next = NULL;
	if(!Q->front) Q->front = n;
	if(Q->rear) Q->rear->next = n;
	Q->rear = n;
}
BiTree OutQueue(Queue *Q)
{
	BiTree temp;
	temp = Q->front->E;
	Q->front = Q->front->next;
	return temp;
}
int InitQueue(Queue *Q)
{
	Q->front = NULL;
	Q->rear = NULL;
}
//------------------------------
int PrintElement(BiTree T)
{
	cprintf("%c ",T->data);
	return 1;
}

void PrintTree(BiTree T, int D)
{
	int i;
	if(T!=NULL)
	{
		PrintTree(T->r, D+1);
		for(i=1;i<D;i++) cprintf("  ");
		cprintf("%c\r\n",T->data);
		PrintTree(T->l, D+1);
	}
}

void CreateBiTree(BiTree *T)
{
	char ch;
	char t;
	//scanf(&ch);
	//scanf(&t);
	ch = getchar();
	t = getchar();
	if(ch == ' ') *T=NULL;
	else
	{
		*T = (BiTree)malloc(sizeof(BiTNode));
		(*T)->data = ch;
		(*T)->fw = (*T)->bw = NULL;
		CreateBiTree(&((*T)->l));
		CreateBiTree(&((*T)->r));
	}
}

void PreOrderTraverse(BiTree T, int(*Visit)(BiTree))
{
	Stack S;
	BiTree p;
	InitStack(&S);
	p = T;
	while(p || !IsEmpty(&S))
	{
		if(p)
		{
			Visit(p);
			Push(&S, p);
			p = p->l;
		}
		else
		{
			p = Pop(&S)->r;
		}
	}
}

void InOrderTraverse(BiTree T, int(*Visit)(BiTree))
{
	Stack S;
	BiTree p;
	InitStack(&S);
	p = T;
	while(p || !IsEmpty(&S))
	{
		if(p)
		{
			Push(&S, p);
			p = p->l;
		}
		else
		{
			p = Pop(&S);
			Visit(p);
			p = p->r;
		}
	}
}

void PostOrderTraverse(BiTree T, int(*Visit)(BiTree))
{
	if(T)
	{
		PostOrderTraverse(T->l, Visit);
		PostOrderTraverse(T->r, Visit);
		Visit(T);
	}
	return;
}

void LevelOrderTraverse(BiTree T, int(*Visit)(BiTree))
{
	BiTree p;
	Queue Q;
	InitQueue(&Q);
	p = T;
	EnQueue(&Q, p);
	while(Q.front)
	{
		p = OutQueue(&Q);
		Visit(p);
		if(p->l) EnQueue(&Q, p->l);
		if(p->r) EnQueue(&Q, p->r);
	}
}

void PreOrderThreading(BiTree T)
{
	Stack S;
	BiTree p, pre;
	InitStack(&S);
	p = T; pre = NULL;
	while(p || !IsEmpty(&S))
	{
		if(p)
		{
			p->fw = pre;
			if(pre) pre->bw = p;
			pre = p;
			Push(&S, p);
			p = p->l;
		}
		else
		{
			p = Pop(&S)->r;
		}
	}
	pre->bw = NULL;
}

void InOrderThreading(BiTree T)
{
	Stack S;
	BiTree p, pre;
	InitStack(&S);
	p = T; pre = NULL;
	while(p || !IsEmpty(&S))
	{
		if(p)
		{
			p->fw = pre;
			if(pre) pre->bw = p;
			pre = p;
			Push(&S, p);
			p = p->l;
		}
		else
		{
			p = Pop(&S);
			p->fw = pre;
			if(pre) pre->bw = p;
			pre = p;
			p = p->r;
		}
	}
	pre->bw = NULL;
}