Skip to content

Instantly share code, notes, and snippets.

@limboinf
Created January 18, 2017 04:14
Show Gist options
  • Save limboinf/4d9581d50ee75c24d2c194dd565fb668 to your computer and use it in GitHub Desktop.
Save limboinf/4d9581d50ee75c24d2c194dd565fb668 to your computer and use it in GitHub Desktop.
重点就是:递归和链表的运用。
//
// Created by 方朋 on 2017/1/4.
//
#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码,如OK等 */
typedef char TElemType;
TElemType Nil = ' '; // 字符型以空格为空
typedef struct BiTNode // 结点结构
{
TElemType data; // 结点数据
struct BiTNode *lchild, *rchild; // 左右孩子指针
}BiTNode, *BiTree;
/* 构造空二叉树T */
Status InitBiTree(BiTree *T)
{
*T=NULL;
return OK;
}
/* 按前序输入二叉树中结点的值(一个字符) */
/* #表示空树,构造二叉链表表示二叉树T。 */
/* 大话数据结构树: C6.9 小结 */
void CreateBiTree(BiTree *T)
{
TElemType ch;
scanf ("%c", &ch);
if (ch == '#')
*T = NULL;
else
{
*T = (BiTree)malloc (sizeof (struct BiTNode));
if(!*T)
exit (2);
(*T)->data = ch; // 生成根结点
CreateBiTree (&(*T)->lchild); // 构造左子树
CreateBiTree (&(*T)->rchild); // 构造右子树
}
}
int BiTreeEmpty (BiTree T)
{
return T ? 0 : 1;
}
int BiTreeDepth(BiTree T)
{
int i, j;
if (!T) return 0;
i = T->lchild ? BiTreeEmpty (T->lchild) : 0;
j = T->rchild ? BiTreeEmpty (T->rchild) : 0;
return i > j ? i+1 : j+1;
}
TElemType Root(BiTree T)
{
return T ? T->data : Nil;
}
void PreOrderTraverse(BiTree T)
{
if (T == NULL) return;
printf ("%c", T->data);
PreOrderTraverse (T->lchild);
PreOrderTraverse (T->rchild);
}
void InOrderTraverse(BiTree T)
{
if (T == NULL) return;
PreOrderTraverse (T->lchild);
printf ("%c", T->data);
PreOrderTraverse (T->rchild);
}
void PostOrderTraverse(BiTree T)
{
if (T == NULL) return;
PreOrderTraverse (T->lchild);
PreOrderTraverse (T->rchild);
printf ("%c", T->data);
}
/* 初始条件: 二叉树T存在。操作结果: 销毁二叉树T */
void DestroyBiTree(BiTree *T)
{
if (*T)
{
if ((*T)->lchild) // 如有左孩子则递归销毁左孩子
DestroyBiTree (&(*T)->lchild);
if ((*T)->rchild) // 如有右孩子则递归销毁右孩子
DestroyBiTree (&(*T)->lchild);
free (*T); // 释放根结点
*T = NULL; // 空指针赋null
}
}
#define ClearBiTree DestroyBiTree
int main()
{
int i;
BiTree T;
TElemType e1;
InitBiTree(&T);
CreateBiTree(&T);
printf("构造空二叉树后,树空否?%d(1:是 0:否) 树的深度=%d\n",BiTreeEmpty(T),BiTreeDepth(T));
e1=Root(T);
printf("二叉树的根为: %c\n",e1);
printf("\n前序遍历二叉树:");
PreOrderTraverse(T);
printf("\n中序遍历二叉树:");
InOrderTraverse(T);
printf("\n后序遍历二叉树:");
PostOrderTraverse(T);
ClearBiTree(&T);
printf("\n清除二叉树后,树空否?%d(1:是 0:否) 树的深度=%d\n",BiTreeEmpty(T),BiTreeDepth(T));
i=Root(T);
if(!i)
printf("树空,无根\n");
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment