数据结构C语言版 二叉链表树

高中物理教学艺术

数据结构C语言版 二叉链表树.txt
/*
数据结构C语言版 二叉链表树
P127
编译环境：Dev-C++ 4.9.9.2
日期：2011年2月13日
*/
#include <stdio.h>
#include <malloc.h>

// 用链表存储结构表示二叉树。
typedef char TElemType;

typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild, *rchild; // 左右孩子指针
}BiTNode, *BiTree;

typedef BiTree QElemType; // 设队列元素类型为二叉树的指针类型
typedef BiTree SElemType; // 设栈元素类型为二叉树的指针类型

// 单链队列－－队列的链式存储结构
typedef struct QNode
{
QElemType data; //数据域
struct QNode *next; //指针域
}QNode, *QueuePtr;

typedef struct
{
QueuePtr front, //队头指针，指针域指向队头元素
rear; //队尾指针，指向队尾元素
}LinkQueue;

#define STACK_INIT_SIZE 10 // 存储空间初始分配量
#define STACKINCREMENT 2 // 存储空间分配增量
// 栈的顺序存储表示 P46
typedef struct SqStack
{
SElemType *base; // 在栈构造之前和销毁之后，base的值为NULL
SElemType *top; // 栈顶指针
int stacksize; // 当前已分配的存储空间，以元素为单位
}SqStack; // 顺序栈


TElemType Nil=' '; // 字符型以空格符为空

// 构造空二叉树T
int InitBiTree(BiTree *T)
{
*T=NULL;
return 1;
}

// 销毁二叉树T
void DestroyBiTree(BiTree *T)
{
if(*T) // 非空树
{
if((*T)->lchild) // 有左孩子
DestroyBiTree(&(*T)->lchild); // 销毁左孩子子树
if((*T)->rchild) // 有右孩子
DestroyBiTree(&(*T)->rchild); // 销毁右孩子子树
free(*T); // 释放根结点
*T=NULL; // 空指针赋0
}
}

#define ClearBiTree DestroyBiTree

// 算法6.4 P131 有改动
// 按先序次序输入二叉树中结点的值，构造二叉链表表示的二叉树T
// 变量Nil表示空（子）树。
void CreateBiTree(BiTree *T)
{
TElemType ch;
scanf("%c",&ch);

if(ch==Nil) // 空
*T=NULL;
else
{
*T=(BiTree)malloc(sizeof(BiTNode));
if(!*T)
exit(0);
(*T)->data=ch; // 生成根结点
CreateBiTree(&(*T)->lchild); // 构造左子树
CreateBiTree(&(*T)->rchild); // 构造右子树
}
}

// 若T为空二叉树,则返回1,否则0
int BiTreeEmpty(BiTree T)
{
if(T)
return 0;
else
return 1;
}

// 返回T的深度
int BiTreeDepth(BiTree T)
{
int i,j;
if(!T)
return 0;
if(T->lchild)
i=BiTreeDepth(T->lchild); //递归求深度
else
i=0;
if(T->rchild)
j=BiTreeDepth(T->rchild);
else
j=0;
return i>j ? i+1 : j+1;
}

// 返回T的根
TElemType Root(BiTree T)
{
if(BiTreeEmpty(T))
return Nil;
else
return T->data;
}

// 返回p所指结点的值
TElemType Value(BiTree p)
{
return p->data;
}

// 给p所指结点赋值为value
void Assign(BiTree p,TElemType value)
{
p->data=value;
}

// 构造一个空队列Q
int InitQueue(LinkQueue *Q)
{