Created
January 18, 2017 04:14
-
-
Save limboinf/4d9581d50ee75c24d2c194dd565fb668 to your computer and use it in GitHub Desktop.
重点就是:递归和链表的运用。
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// | |
// 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