二叉树的链式存储结构----二叉链表

头文件：head.h

#include<string.h>
#include<ctype.h>
#include<malloc.h> /* malloc()等 */
#include<limits.h> /* INT_MAX等 */
#include<stdio.h> /* EOF(=^Z或F6),NULL */
#include<stdlib.h> /* atoi() */
#include<io.h> /* eof() */
#include<math.h> /* floor(),ceil(),abs() */
#include<process.h> /* exit() */
/* 函数结果状态代码 */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
/* #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行 */
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */

#define CHAR//定义字符型
//#define INT//定义整型(二选一)

#ifdef CHAR
typedef char TElemType;
//TElemType Nil = ' ';//字符型以空格为空
#define form "%c%*c"//输出输出的格式为%c
#endif

#ifdef INT
typedef int Elemtype;
//TElemType Nil = 0;//整型以0为空
#define form "%d"//输入输出格式为%d
#endif

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

Status InitBiTree(BiTree *T);

Status DeleteChild(BiTree p, int LR);
//
Status DestroyBiTree(BiTree *T);

Status ClearBiTree(BiTree *T);
//
Status PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e));
//
Status InOrderTraverse(BiTree T, Status(*Visit)(TElemType e));
//
Status CreateBiTree(BiTree *T);
//
Boolean BiTreeEmpty(BiTree T);
//
int BiTreeDepth(BiTree T);
//
TElemType Root(BiTree T);
//
TElemType Value(BiTree p);
//
Status Assign(BiTree T, TElemType value);
//
TElemType Parent(BiTree T, TElemType e);
//
BiTree Point(BiTree T, TElemType s);
//
TElemType LeftChild(BiTree T, TElemType e);
//
TElemType RightChild(BiTree T, TElemType e);
//
TElemType LeftSibling(BiTree T, TElemType e);
//
TElemType RightSibling(BiTree T, TElemType e);
//
Status InsertChild(BiTree p, int LR, BiTree c);
//
Status DeleteChile(BiTree p, int LR);
//
Status InOrderTraverse1(BiTree T, void(*Visit)(TElemType));
//
Status InOrderTraverse2(BiTree T, void(*Visit)(TElemType));
//
void PostOrderTraverse(BiTree T, Status(*Visit)(TElemType));
//
void LevelOrderTraverse(BiTree T, Status(*Visit)(TElemType));

算法实现：

#include"head.h"

#ifdef CHAR
TElemType Nil = ' ';//字符型以空格为空
#endif

#ifdef INT
TElemType Nil = 0;//整型以0为空
#endif


#define ClearBiTree DestroyBiTree

Status InitBiTree(BiTree *T)
{
//操作结果：构造空的二叉树T
//注意：空的和已销毁的二叉树结构都是一样的

*T = NULL;
return OK;
}

Status DestroyBiTree(BiTree *T)
{
//初始条件：二叉树T存在
//操作结果：销毁二叉树T

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

return OK;
}

Status PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e))
{
//初始条件：二叉树存在，Visit是对结点操作的应用函数
//操作结果：先序递归遍历T，对每个结点调用函数Visit一次且仅一次

if (T)//T不为空
{
Visit(T->data);//先访问根节点
//if (T->lchild)
PreOrderTraverse(T->lchild, Visit);//再先序遍历左子树
//if (T->rchild)
PreOrderTraverse(T->rchild, Visit);//最后先序遍历右子树
}

return OK;
}

Status InOrderTraverse(BiTree T, Status(*Visit)(TElemType e))
{
//初始条件：二叉树存在，Visit是对结点操作的应用函数
//操作结果：中序递归遍历T，对每个结点调用函数Visit一次且仅一次

if (T)
{
InOrderTraverse(T->lchild, Visit);
Visit(T->data);
InOrderTraverse(T->rchild, Visit);
}
return OK;
}

Status CreateBiTree(BiTree *T)
{
//按照先序次序输入二叉树中结点的值(一个字符)，空格字符表示空树
//构造二叉链表表示的二叉树T

TElemType ch;
#ifdef CHAR
scanf_s("%c", &ch, 1);
#endif
#ifdef INT
scanf_s("%d", ch);
#endif
if (ch == Nil)
*T = NULL;
else
{
(*T) = (BiTree)malloc(sizeof(BiTNode));
if (!(*T))
{
printf("生成树失败！");
system("pause");
exit(-1);
}
(*T)->data = ch;//生成根结点
CreateBiTree(&(*T)->lchild);//构造左子树
CreateBiTree(&(*T)->rchild);//构造右子树
}

return OK;
}

Boolean BiTreeEmpty(BiTree T)
{
//初始条件：二叉树T存在
//操作结果:若二叉树为空树，返回TRUE；否则，返回FALSE;

if (T)
return FALSE;
else
return TRUE;
}

int BiTreeDepth(BiTree T)
{
//初始条件：二叉树T存在
//操作结果：返回T的深度

int l, r;//l为左子树的深度，r为右子树的深度

//如果树为空，返回深度为0
if (!T)
return 0;

if (T->lchild)//左子树的深度
l = BiTreeDepth(T->lchild);
else
l = 0;

if (T->rchild)//右子树的深度
r = BiTreeDepth(T->rchild);
else
r = 0;

return l > r ? l + 1 : r + 1;//深度为其左右子树的深度中的大者加1
}

TElemType Root(BiTree T)
{
//初始条件：二叉树T存在
//操作结果：返回T的根

if (BiTreeEmpty(T))
return Nil;
else
return T->data;
}

TElemType Value(BiTree p)
{
//初始条件：二叉树T存在，p指向T中某个结点
//操作结果：返回p所指向的值

return p->data;
}

Status Assign(BiTree T, TElemType value)
{
//给T所指定的结点赋值为value
T->data = value;

return OK;
}

//**************************************************************************

typedef BiTree QElemType;//和队列相结合
#include"Queue.h"
#include"Queue.c"

TElemType Parent(BiTree T, TElemType e)
{
//初始条件：二叉树T存在，e是T的某个结点
//操作结果：若e是T的非根结点，则返回它的双亲，否则返回空

if (BiTreeEmpty(T))
return Nil;

LinkQueue q;
QElemType a;
//InitBiTree(&a);
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)
return a->data;//找到该元素
else
{
if (a->lchild)//若果左孩子不为空，则插入左孩子
EnQueue(&q, a->lchild);
if (a->rchild)//若果右孩子不为空，则插入右孩子
EnQueue(&q, a->rchild);
}
}

return Nil;//树为空或者没有找到e
}

BiTree Point(BiTree T, TElemType s)
{
//初始条件：树T不为空
//操作结果：返回二叉树中指向元素值为s的结点的指针

LinkQueue q;
QElemType a;

if (T)
{
InitQueue(&q);//初始化队列
EnQueue(&q, T);
while (!QueueEmpty(q))
{
DeQueue(&q, &a);
if (a->data == s)
return a;
if (a->lchild)
EnQueue(&q, a->lchild);
if (a->rchild)
EnQueue(&q, a->rchild);
}
}
return NULL;
}

TElemType LeftChild(BiTree T, TElemType e)
{
//初始条件：二叉树T存在，e是T中某个结点
//操作结果：返回e的左孩子，若e无左孩子，则返回“空”

BiTree a;

if (BiTreeEmpty(T))
return Nil;

a = Point(T, e);
if (a && a->lchild)
return a->lchild->data;

return Nil;
}

TElemType RightChild(BiTree T, TElemType e)
{
//初始条件：二叉树T存在，e是T中某个结点
//操作结果：返回e的右孩子，若e无右孩子，则返回“空”

BiTree a;

if (BiTreeEmpty(T))
return Nil;

a = Point(T, e);
if (a && a->rchild)
return a->rchild->data;

return Nil;
}

TElemType LeftSibling(BiTree T, TElemType e)
{
//初始条件：二叉树T存在，e是T中某个结点
//操作结果：返回e的左兄弟，若e无左兄弟，则返回“空”

TElemType a;
BiTree p;

if (BiTreeEmpty(T))//树为空则退出，不再查找
return Nil;

a = Parent(T, e);//a元素为e的双亲
if (a != Nil)//a的双亲不为空
{
p = Point(T, a);//定位双亲指针
if (p->lchild && p->rchild && p->rchild->data == e)//p存在左右孩子且右孩子等于e
return p->lchild->data;
}

return Nil;
}

TElemType RightSibling(BiTree T, TElemType e)
{
//初始条件：二叉树T存在，e是T中某个结点
//操作结果：返回e的右兄弟，若e无右兄弟，则返回“空”

TElemType a;
BiTree p;

if (BiTreeEmpty(T))
return Nil;

a = Parent(T, e);
if (a != Nil)
{
p = Point(T, a);
if (p->rchild&&p->lchild&&(p->lchild->data) == e)
return p->rchild->data;
}

return Nil;
}

Status InsertChild(BiTree p, int LR, BiTree c)
{
//初始条件：二叉树T存在，p指向T中的某个结点，LR为0或1，非空二叉树c与T不相交且右子树为空
//操作结果：根据LR为0或1，插入c为T中p所指结点的左或右子树，p所指结点的原有左或右子树则成为c的右子树

if (p)
{
if (LR == 0)
{
c->rchild = p->lchild;
p->lchild = c;
}
else
{
c->rchild = p->rchild;
p->rchild = c;
}
return OK;
}

return ERROR;
}

Status DeleteChild(BiTree p, int LR)
{
//初始条件：二叉树存在，p指向T中某个结点，LR为0或1
//操作结果：根据LR为0或1，删除T中p所指结点的左或右子树

if (p)
{
if (LR == 0)
ClearBiTree(&(p->lchild));
else
ClearBiTree(&(p->rchild));
return OK;
}

return ERROR;
}

//***********************************************************************************

typedef BiTree SElemType;
#include"Stack.h"
#include"Stack.c"

Status InOrderTraverse1(BiTree T, void(*Visit)(TElemType))
{
//采用二叉链表存储结构，Visit是对数据元素操作的应用函数
//中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit

SqStack S;
InitStack(&S);
while (T || !StackEmpty(S))
{
if (T)//根指针入栈，遍历左子树
{
Push(&S, T);
T = T->lchild;
}
else                    //根指针退栈，遍历右子树
{
Pop(&S, &T);
Visit(T->data);
T=T->rchild;
}
}
printf("\n");

return OK;
}

Status InOrderTraverse2(BiTree T, void(*Visit)(TElemType))
{
//采用二叉树表存储结构，Visit是对数据元素操作的应用函数
//中序遍历二叉树T的非递归算法，对每个元素调用函数Visit

SqStack S;
BiTree p;
InitBiTree(&p);
InitStack(&S);
Push(&S, T);//根指针入栈
while (!StackEmpty(S))
{
while (GetTop(S, &p) && p)
Push(&S, p->lchild);//向左走到尽头
Pop(&S, &p);//空指针退栈
if (!StackEmpty(S))             //访问根节点，向右一步
{
Pop(&S, &p);
Visit(p->data);
Push(&S, p->rchild);
}
}
printf("\n");

return OK;
}

void PostOrderTraverse(BiTree T, Status(*Visit)(TElemType))
{ /* 初始条件: 二叉树T存在,Visit是对结点操作的应用函数 */
/* 操作结果: 后序递归遍历T,对每个结点调用函数Visit一次且仅一次 */
if (T) /* T不空 */
{
PostOrderTraverse(T->lchild, Visit); /* 先后序遍历左子树 */
PostOrderTraverse(T->rchild, Visit); /* 再后序遍历右子树 */
Visit(T->data); /* 最后访问根结点 */
}
}

void LevelOrderTraverse(BiTree T, Status(*Visit)(TElemType))
{ /* 初始条件：二叉树T存在,Visit是对结点操作的应用函数 */
/* 操作结果：层序递归遍历T(利用队列),对每个结点调用函数Visit一次且仅一次 */
LinkQueue q;
QElemType a;
if (T)
{
InitQueue(&q);
EnQueue(&q, T);
while (!QueueEmpty(q))
{
DeQueue(&q, &a);
Visit(a->data);
if (a->lchild != NULL)
EnQueue(&q, a->lchild);
if (a->rchild != NULL)
EnQueue(&q, a->rchild);
}
printf("\n");
}
}
//****************************************************************************************

引用文件： Queue.h

 /* 单链队列－－队列的链式存储结构 */

 typedef struct QNode
 {
   QElemType data;
   struct QNode *next;
 }QNode,*QueuePtr;

 typedef struct
 {
   QueuePtr front,rear; /* 队头、队尾指针 */
 }LinkQueue;

队列的算法实现部分：Queue.c

 /* 链队列(存储结构由Queue.h定义)的基本操作(9个) */
 Status InitQueue(LinkQueue *Q)
 { /* 构造一个空队列Q */
   (*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode));
   if(!(*Q).front)
     exit(OVERFLOW);
   (*Q).front->next=NULL;
   return OK;
 }

 Status DestroyQueue(LinkQueue *Q)
 { /* 销毁队列Q(无论空否均可) */
   while((*Q).front)
   {
     (*Q).rear=(*Q).front->next;
     free((*Q).front);
     (*Q).front=(*Q).rear;
   }
   return OK;
 }

 Status ClearQueue(LinkQueue *Q)
 { /* 将Q清为空队列 */
   QueuePtr p,q;
   (*Q).rear=(*Q).front;
   p=(*Q).front->next;
   (*Q).front->next=NULL;
   while(p)
   {
     q=p;
     p=p->next;
     free(q);
   }
   return OK;
 }

 Status QueueEmpty(LinkQueue Q)
 { /* 若Q为空队列,则返回TRUE,否则返回FALSE */
   if(Q.front==Q.rear)
     return TRUE;
   else
     return FALSE;
 }

 int QueueLength(LinkQueue Q)
 { /* 求队列的长度 */
   int i=0;
   QueuePtr p;
   p=Q.front;
   while(Q.rear!=p)
   {
     i++;
     p=p->next;
   }
   return i;
 }

 Status GetHead_Q(LinkQueue Q,QElemType *e) /* 避免与bo2-6.c重名 */
 { /* 若队列不空,则用e返回Q的队头元素,并返回OK,否则返回ERROR */
   QueuePtr p;
   if(Q.front==Q.rear)
     return ERROR;
   p=Q.front->next;
   *e=p->data;
   return OK;
 }

 Status EnQueue(LinkQueue *Q,QElemType e)
 { /* 插入元素e为Q的新的队尾元素 */
   QueuePtr p=(QueuePtr)malloc(sizeof(QNode));
   if(!p) /* 存储分配失败 */
     exit(OVERFLOW);
   p->data=e;
   p->next=NULL;
   (*Q).rear->next=p;
   (*Q).rear=p;
   return OK;
 }

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

 Status QueueTraverse(LinkQueue Q,void(*vi)(QElemType))
 { /* 从队头到队尾依次对队列Q中每个元素调用函数vi()。一旦vi失败,则操作失败 */
   QueuePtr p;
   p=Q.front->next;
   while(p)
   {
     vi(p->data);
     p=p->next;
   }
   printf("\n");
   return OK;
 }

引用文件：Stack.h

 /*栈的顺序存储表示 */
 #define STACK_INIT_SIZE 10 /* 存储空间初始分配量 */
 #define STACKINCREMENT 2 /* 存储空间分配增量 */

typedef BiTree SElemType;

 typedef struct SqStack
 {
   SElemType *base; /* 在栈构造之前和销毁之后，base的值为NULL */
   SElemType *top; /* 栈顶指针 */
   int stacksize; /* 当前已分配的存储空间，以元素为单位 */
 }SqStack; /* 顺序栈 */

栈的算法实现部分：Stack.c

 /* 顺序栈（存储结构由Stack.h定义）的基本操作（9个） */
 Status InitStack(SqStack *S)
 { /* 构造一个空栈S */
   (*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
   if(!(*S).base)
     exit(OVERFLOW); /* 存储分配失败 */
   (*S).top=(*S).base;
   (*S).stacksize=STACK_INIT_SIZE;
   return OK;
 }

 Status DestroyStack(SqStack *S)
 { /* 销毁栈S，S不再存在 */
   free((*S).base);
   (*S).base=NULL;
   (*S).top=NULL;
   (*S).stacksize=0;
   return OK;
 }

 Status ClearStack(SqStack *S)
 { /* 把S置为空栈 */
   (*S).top=(*S).base;
   return OK;
 }

 Status StackEmpty(SqStack S)
 { /* 若栈S为空栈，则返回TRUE，否则返回FALSE */
   if(S.top==S.base)
     return TRUE;
   else
     return FALSE;
 }

 int StackLength(SqStack S)
 { /* 返回S的元素个数，即栈的长度 */
   return S.top-S.base;
 }

 Status GetTop(SqStack S,SElemType *e)
 { /* 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR */
   if(S.top>S.base)
   {
     *e=*(S.top-1);
     return OK;
   }
   else
     return ERROR;
 }

 Status Push(SqStack *S,SElemType e)
 { /* 插入元素e为新的栈顶元素 */
   if((*S).top-(*S).base>=(*S).stacksize) /* 栈满，追加存储空间 */
   {
     (*S).base=(SElemType *)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType));
     if(!(*S).base)
       exit(OVERFLOW); /* 存储分配失败 */
     (*S).top=(*S).base+(*S).stacksize;
     (*S).stacksize+=STACKINCREMENT;
   }
   *((*S).top)++=e;
   return OK;
 }

 Status Pop(SqStack *S,SElemType *e)
 { /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
   if((*S).top==(*S).base)
     return ERROR;
   *e=*--(*S).top;
   return OK;
 }

 Status StackTraverse(SqStack S,Status(*visit)(SElemType))
 { /* 从栈底到栈顶依次对栈中每个元素调用函数visit()。 */
   /* 一旦visit()失败，则操作失败 */
   while(S.top>S.base)
     visit(*S.base++);
   printf("\n");
   return OK;
 }

测试文件：

#include"head.h"

TElemType nn = ' ';

Status visitT(TElemType e)
{
#ifdef CHAR
printf("%c ", e);
#endif
#ifdef INT
printf("%d ", e);
#endif
return OK;
}

void main()
{
int i;

BiTree T, p, c;
TElemType e1, e2, temp;
InitBiTree(&T);
printf("构造空二叉树后,树空否？%d(1:是 0:否) 树的深度=%d\n", BiTreeEmpty(T), BiTreeDepth(T));
e1 = Root(T);
if (e1 != nn)
#ifdef CHAR
printf("二叉树的根为: %c\n", e1);
#endif
#ifdef INT
printf("二叉树的根为: %d\n", e1);
#endif
else
printf("树空，无根\n");
#ifdef CHAR
printf("请先序输入二叉树(如:ab三个空格表示a为根结点,b为左子树的二叉树)\n");
#endif
#ifdef INT
printf("请先序输入二叉树(如:1 2 0 0 0表示1为根结点,2为左子树的二叉树)\n");
#endif
CreateBiTree(&T);
printf("建立二叉树后,树空否？%d(1:是 0:否) 树的深度=%d\n", BiTreeEmpty(T), BiTreeDepth(T));
e1 = Root(T);
if (e1 != nn)
#ifdef CHAR
printf("二叉树的根为: %c\n", e1);
#endif
#ifdef INT
printf("二叉树的根为: %d\n", e1);
#endif
else
printf("树空，无根\n");
printf("中序递归遍历二叉树:\n");
InOrderTraverse(T, visitT);
printf("\n中序非递归遍历二叉树:\n");
InOrderTraverse1(T, visitT);
printf("中序非递归遍历二叉树(另一种方法):\n");
InOrderTraverse2(T, visitT);
printf("后序递归遍历二叉树:\n");
PostOrderTraverse(T, visitT);
printf("\n层序遍历二叉树:\n");
LevelOrderTraverse(T, visitT);
printf("请输入一个结点的值: ");
#ifdef CHAR
while (getchar()!='\n');
e1 = getchar();
#endif
#ifdef INT
scanf_s("%d", &e1);
#endif
p = Point(T, e1); /* p为e1的指针 */
#ifdef CHAR
printf("结点的值为%c\n", Value(p));
#endif
#ifdef INT
printf("结点的值为%d\n", Value(p));
#endif
printf("欲改变此结点的值，请输入新值: ");
#ifdef CHAR
while (getchar() != '\n');
e2 = getchar();
#endif
#ifdef INT
scanf_s("%d", &e2);
#endif
Assign(p, e2);
printf("层序遍历二叉树:\n");
LevelOrderTraverse(T, visitT);
e1 = Parent(T, e2);
if (e1 != nn)
#ifdef CHAR
printf("%c的双亲是%c\n", e2, e1);
#endif
#ifdef INT
printf("%d的双亲是%d\n", e2, e1);
#endif
else
#ifdef CHAR
printf("%c没有双亲\n", e2);
#endif
#ifdef INT
printf("%d没有双亲\n", e2);
#endif
e1 = LeftChild(T, e2);
if (e1 != nn)
#ifdef CHAR
printf("%c的左孩子是%c\n", e2, e1);
#endif
#ifdef INT
printf("%d的左孩子是%d\n", e2, e1);
#endif
else
#ifdef CHAR
printf("%c没有左孩子\n", e2);
#endif
#ifdef INT
printf("%d没有左孩子\n", e2);
#endif
e1 = RightChild(T, e2);
if (e1 != nn)
#ifdef CHAR
printf("%c的右孩子是%c\n", e2, e1);
#endif
#ifdef INT
printf("%d的右孩子是%d\n", e2, e1);
#endif
else
#ifdef CHAR
printf("%c没有右孩子\n", e2);
#endif
#ifdef INT
printf("%d没有右孩子\n", e2);
#endif
e1 = LeftSibling(T, e2);
if (e1 != nn)
#ifdef CHAR
printf("%c的左兄弟是%c\n", e2, e1);
#endif
#ifdef INT
printf("%d的左兄弟是%d\n", e2, e1);
#endif
else
#ifdef CHAR
printf("%c没有左兄弟\n", e2);
#endif
#ifdef INT
printf("%d没有左兄弟\n", e2);
#endif
e1 = RightSibling(T, e2);
if (e1 != nn)
#ifdef CHAR
printf("%c的右兄弟是%c\n", e2, e1);
#endif
#ifdef INT
printf("%d的右兄弟是%d\n", e2, e1);
#endif
else
#ifdef CHAR
printf("%c没有右兄弟\n", e2);
#endif
#ifdef INT
printf("%d没有右兄弟\n", e2);
#endif
InitBiTree(&c);
printf("构造一个右子树为空的二叉树c:\n");
#ifdef CHAR
printf("请先序输入二叉树(如:ab三个空格表示a为根结点,b为左子树的二叉树)\n");
#endif
#ifdef INT
printf("请先序输入二叉树(如:1 2 0 0 0表示1为根结点,2为左子树的二叉树)\n");
#endif
while ((temp = getchar() != '\n') && temp != EOF);
CreateBiTree(&c);
printf("先序递归遍历二叉树c:\n");
PreOrderTraverse(c, visitT);
printf("\n树c插到树T中,请输入树T中树c的双亲结点 c为左(0)或右(1)子树: ");
#ifdef CHAR
while ((temp = getchar() != '\n') && temp != EOF);//清空多余的输入
//e1 = getchar();
scanf_s("%c %d", &e1, 1, &i);
#endif
#ifdef INT
scanf_s("%d%d", &e1, &i);
#endif
p = Point(T, e1); /* p是T中树c的双亲结点指针 */
InsertChild(p, i, c);
printf("先序递归遍历二叉树:\n");
PreOrderTraverse(T, visitT);
printf("\n删除子树,请输入待删除子树的双亲结点  左(0)或右(1)子树: ");
#ifdef CHAR
while ((temp = getchar() != '\n') && temp != EOF);//清空多余的输入
scanf_s("%c %d",&e1, 1, &i);
//scanf_s("%*c%c%d", &e1, &i);
#endif
#ifdef INT
scanf_s("%d%d", &e1, &i);
#endif
p = Point(T, e1);
DeleteChild(p, i);
printf("先序递归遍历二叉树:\n");
PreOrderTraverse(T, visitT);
printf("\n");
DestroyBiTree(&T);

system("pause");
}

Running Result：

构造空二叉树后,树空否？1(1:是 0:否) 树的深度=0
树空，无根
请先序输入二叉树(如:ab三个空格表示a为根结点,b为左子树的二叉树)
abdg   e  c f
建立二叉树后,树空否？0(1:是 0:否) 树的深度=4
二叉树的根为: a
中序递归遍历二叉树:
g d b e a c f
中序非递归遍历二叉树:
g d b e a c f
中序非递归遍历二叉树(另一种方法):
g d b e a c f
后序递归遍历二叉树:
g d e b f c a
层序遍历二叉树:
a b c d e f g
请输入一个结点的值: d
结点的值为d
欲改变此结点的值，请输入新值: m
层序遍历二叉树:
a b c m e f g
m的双亲是b
m的左孩子是g
m没有右孩子
m没有左兄弟
m的右兄弟是e
构造一个右子树为空的二叉树c:
请先序输入二叉树(如:ab三个空格表示a为根结点,b为左子树的二叉树)
hijl   k
先序递归遍历二叉树c:
h i j l k
树c插到树T中,请输入树T中树c的双亲结点 c为左(0)或右(1)子树: b 1
先序递归遍历二叉树:
a b m g h i j l k e c f
删除子树,请输入待删除子树的双亲结点  左(0)或右(1)子树: h 0
e1 = h, i = 0
先序递归遍历二叉树:
a b m g h e c f
请按任意键继续. . .