数据结构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)
{

高中物理教学艺术

//动态分配一个空间
(*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode));
if(!(*Q).front)
exit(0);
//队头指针指向空，无数据域，这样构成了一个空队列
(*Q).front->next=NULL;
return 1;
}

// 插入元素e为Q的新的队尾元素
int EnQueue(LinkQueue *Q,QElemType e)
{
QueuePtr p=(QueuePtr)malloc(sizeof(QNode));
if(!p) // 存储分配失败
exit(0);
//生成一个以为e为数据域的队列元素
p->data=e;
p->next=NULL;
//将该新队列元素接在队尾的后面
(*Q).rear->next=p;
(*Q).rear=p;
return 1;
}

// 若队列不空,删除Q的队头元素,用e返回其值,并返回1,否则返回0
int DeQueue(LinkQueue *Q,QElemType *e)
{
QueuePtr p;
if((*Q).front==(*Q).rear)
return 0;
p=(*Q).front->next;//队头元素
*e=p->data;
(*Q).front->next=p->next;
if((*Q).rear==p)
(*Q).rear=(*Q).front;
free(p);
return 1;
}

// 若Q为空队列,则返回1,否则返回0
int QueueEmpty(LinkQueue Q)
{
if(Q.front==Q.rear)
return 1;
else
return 0;
}

// 若e是T的非根结点,则返回它的双亲,否则返回＂空＂
TElemType Parent(BiTree T,TElemType e)
{
LinkQueue q;
QElemType a;

if(T) // 非空树
{
InitQueue(&q); // 初始化队列
EnQueue(&q,T); // 树根入队
while(!QueueEmpty(q)) // 队不空
{
DeQueue(&q,&a); // 出队,队列元素赋给a
if(a->lchild&&a->lchild->data==e||a->rchild
&&a->rchild->data==e)
// 找到e(是其左或右孩子)
return a->data; // 返回e的双亲的值
else // 没找到e,则入队其左右孩子指针(如果非空)
{
if(a->lchild)
EnQueue(&q,a->lchild);
if(a->rchild)
EnQueue(&q,a->rchild);
}
}
}
return Nil; // 树空或没找到e
}

// 返回二叉树T中指向元素值为s的结点的指针。
BiTree Point(BiTree T,TElemType s)
{
LinkQueue q;
QElemType a;
if(T) // 非空树
{
InitQueue(&q); // 初始化队列
EnQueue(&q,T); // 根结 …… 此处隐藏：8218字，全部文档内容请下载后查看。喜欢就下载吧 ……