“二叉树”——链表表示

二叉树相关定义：

二叉树有三种表示方法，今天就以这三种表示方法分别讨论。

1.二叉链表表示

那么二叉树的基本遍历方式有三种（前序、中序、后序）

代码层次：

tree.h

#ifndef _TREE_H
#define _TREE_H

typedef struct node
{
	char data;
	struct node *lchild,*rchild;
}TREE;

#endif

tree.c

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include "tree.h"
#include "stack.h"
#include "stackInt.h"
#include "queue.h"


TREE * MakeTree()
{
	TREE *t = NULL;
	char ch;
	ch = getche();
	if(ch == '#')
		return NULL;
	t = (TREE *)malloc(sizeof(TREE));
	if(t == NULL) return NULL;
	t->data = ch;
	t->lchild = MakeTree();
	t->rchild = MakeTree();
	return t;
}

void PrintTreeByBefore(TREE *t)
{
	if(t == NULL)
		return ;
	printf("[%c]",t->data);
	PrintTreeByBefore(t->lchild);
	PrintTreeByBefore(t->rchild);
}

void PrintTreeByMid(TREE *t)
{
	TREE *p = t;
	STACK *s = InitStack();
	Push(s,&t);
	while(!IsEmpty(s))
	{
		while(p)
		{
			p = p->lchild;
			Push(s,&p);
		}
		Pop(s,&p);
		if(!IsEmpty(s))
		{
			Pop(s,&p);
			printf("[%c]",p->data);
			p = p->rchild;
			Push(s,&p);
		}
	}
	DestroyStack(s);
}

void PrintTreeByBack(TREE *t)
{
	STACK *s = InitStack();
	STACK2 *f = InitStack2();
	TREE *p = t;
	int flag = 1;
	while(p || !IsEmpty(s))
	{
		if(p)
		{
			flag = 1;
			Push(s,&p);Push2(f,&flag);
			p = p->lchild;
		}else{
			Pop(s,&p);Pop2(f,&flag);
			if(flag == 1)
			{
				flag = 2;
				Push(s,&p);Push2(f,&flag);
				p = p->rchild;
			}else{
				printf("[%c]",p->data);
				p = NULL;
			}
		}
	}
}

void PrintTreeByLevel(TREE *t)
{
	TREE *p;
	QUEUE *q = InitQueue();
	InQueue(q,t);
	while(!QueueEmpty(q))
	{
		OutQueue(q,&p);
		if(p!=NULL)
		{
			printf("[%c]",p->data);
			InQueue(q,p->lchild);
			InQueue(q,p->rchild);
		}
	}
}

void main()
{
	TREE *tree = MakeTree();
	PrintTreeByBefore(tree);
	printf("\n\n***\n");
	PrintTreeByMid(tree);
	printf("\n\n***\n");
	PrintTreeByBack(tree);
	printf("\n\n***\n");
	PrintTreeByLevel(tree);
}

测试与应用：

附上相关的代码：、

data.h

#ifndef _DATA_H
#define _DATA_H
#include "tree.h"
//typedef int ElemType;
typedef  TREE* ElemType ;

#endif

dataInt.h

#ifndef _DATA_H2
#define _DATA_H2

typedef int ElemType2;
//typedef TREE* ElemType;

#endif

stack.h

//条件定义，避免相同头文件重复导入
#ifndef _STACK_H
#define _STACK_H
#include "tree.h"
#include"data.h"

#define STACK_INIT_SIZE 10
#define STACK_INCREME   10

typedef struct
{
	ElemType * base;
	ElemType * top;
	int size;
}STACK;

STACK * InitStack();

void DestroyStack(STACK *s);

int Push(STACK *s,ElemType *e);

int Pop(STACK *s,ElemType *e);

int IsEmpty(STACK *s);


#endif

stackInt.h

//条件定义，避免相同头文件重复导入
#ifndef _STACK2_H
#define _STACK2_H
#include"dataInt.h"

#define STACK2_INIT_SIZE 10
#define STACK2_INCREME   10

typedef struct
{
	ElemType2 * base;
	ElemType2 * top;
	int size;
}STACK2;

STACK2 * InitStack2();

void DestroyStack2(STACK2 *s);

int Push2(STACK2 *s,ElemType2 *e);

int Pop2(STACK2 *s,ElemType2 *e);

int IsEmpty2(STACK2 *s);


#endif

queue.h

#ifndef _QUEUE_H
#define _QUEUE_H
#define MAX_SIZE 10
#include "data.h"


typedef struct
{
	ElemType data[MAX_SIZE];
	int front,rear;
}QUEUE;

QUEUE *InitQueue();

int InQueue(QUEUE *q,ElemType value);

int OutQueue(QUEUE *q,ElemType *value);

int QueueEmpty(QUEUE *q);

void FreeQueue(QUEUE *q);

#endif

stack.c

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

STACK * InitStack()
{
	STACK *s = (STACK *)malloc(sizeof(STACK));
	if(s == NULL)
		exit(0);
	s->base = (ElemType *)malloc(STACK_INIT_SIZE *sizeof(ElemType));
	if(s->base == NULL) exit(0);
	s->top = s->base;
	s->size = STACK_INIT_SIZE;
	return s;
}

void DestroyStack(STACK *s)
{
	free(s->base);
	free(s);
}

int Push(STACK *s,ElemType *e)
{
	if(s == NULL || e == NULL)
		return 0;
	if(s->top - s->base >= s->size)
	{
		s->base = (ElemType *)realloc(s->base,
			(s->size + STACK_INCREME)*sizeof(ElemType));
		if(s->base == NULL)
			return 0;
		s->top = s->base + s->size;
		s->size = s->size +	STACK_INCREME;
	}
	*s->top++ = *e;
	return 1;
}

int Pop(STACK *s,ElemType *e)
{
	if(s == NULL || e == NULL)
		return 0;
	if(s->base == s->top) return 0;
	*e = *--s->top;
	return 1;
}

int IsEmpty(STACK *s)
{
	return s->top == s->base ? 1 : 0;
}

stackInt.c

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

STACK2 * InitStack2()
{
	STACK2 *s = (STACK2 *)malloc(sizeof(STACK2));
	if(s == NULL)
		exit(0);
	s->base = (ElemType2 *)malloc(STACK2_INIT_SIZE *sizeof(ElemType2));
	if(s->base == NULL) exit(0);
	s->top = s->base;
	s->size = STACK2_INIT_SIZE;
	return s;
}

void DestroyStack2(STACK2 *s)
{
	free(s->base);
	free(s);
}

int Push2(STACK2 *s,ElemType2 *e)
{
	if(s == NULL || e == NULL)
		return 0;
	if(s->top - s->base >= s->size)
	{
		s->base = (ElemType2 *)realloc(s->base,
			(s->size + STACK2_INCREME)*sizeof(ElemType2));
		if(s->base == NULL)
			return 0;
		s->top = s->base + s->size;
		s->size = s->size +	STACK2_INCREME;
	}
	*s->top++ = *e;
	return 1;
}

int Pop2(STACK2 *s,ElemType2 *e)
{
	if(s == NULL || e == NULL)
		return 0;
	if(s->base == s->top) return 0;
	*e = *--s->top;
	return 1;
}

int IsEmpty2(STACK2 *s)
{
	return s->top == s->base ? 1 : 0;
}

queue.c

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


QUEUE *InitQueue()
{
	QUEUE *q = (QUEUE *)malloc(sizeof(QUEUE));
	if(q == NULL)return 0;
	//指针指向同一个值表示队空
	q->rear = 0;
	q->front = 0;
	return q;
}


int InQueue(QUEUE *q,ElemType value)
{
	//判断队满就是front比rear大1
	if((q->rear+1)%MAX_SIZE == q->front)
		return 0;
	q->data[q->rear] = value;
	q->rear = (q->rear+1) % MAX_SIZE;
	return 1;
}

int OutQueue(QUEUE *q,ElemType *value)
{
	if(q->rear == q->front)
		return 0;
	*value = q->data[q->front];
	q->front = (q->front+1) % MAX_SIZE;
	return 1;
}

int QueueEmpty(QUEUE *q)
{
	return q->rear == q->front;
}

void FreeQueue(QUEUE *q)
{
	free(q);
}

2.顺序存储表示

3.三叉链表表示

这两种表示方式将后续写上哈。