本文内容
- 环境
- 基本结构 basic.h 文件
- 链式二叉树 bitree.h 文件
- 链式二叉树 bitree.c 文件
- 测试
本文主要是创建一棵链式二叉树，有两种方法：一是手动，输入树节点；二是通过一个数组，毕竟要是测试什么算法的话，总得有一棵树。
环境
- codeblock 12.11
- Windows 7 旗舰版 64位
基本结构 basic.h 文件
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Status;
typedef int TElementType;
链式二叉树 bitree.h 文件
#ifndef BITREE_H_INCLUDED
#define BITREE_H_INCLUDED
#include "basic.h"
struct BiTreeNode;
typedef struct BiTreeNode *BiTreePrt;
typedef BiTreePrt BiTree;
typedef BiTreePrt BiTreePos;
/* 创建二叉树 */
BiTree CreateBiTreeHand();
BiTree CreateBiTreeArray(TElementType a[], int *i, int n);
/* 置空二叉树 */
BiTree MakeEmptyBiTree( BiTree T );
/* 二叉树是否为空 */
Status IsEmpytBiTree( BiTree T);
/* 先序 中序 后序遍历 */
void BiTreePreOrder( BiTree T );
void BiTreeInOrder( BiTree T );
void BiTreePostOrder( BiTree T );
int BiTreeDepth(BiTree T);
#endif
链式二叉树 bitree.c 文件
#include "basic.h"
#include "bitree.h"
#include
#include "fatal.h"
#include
struct BiTreeNode
{ TElementType Element;
BiTreePrt Left;
BiTreePrt Right;
};
BiTree CreateBiTreeHand()
{ TElementType e;
BiTree T;
scanf("%d", &e); if(e<0) T = NULL;
else
{ T = ( BiTree )malloc(sizeof( struct BiTreeNode ) );
T->Element = e;
T->Left = CreateBiTreeHand();
T->Right = CreateBiTreeHand();
}
return T;
}
BiTree CreateBiTreeArray(TElementType a[], int *i, int n)
{ BiTree T;
TElementType e=a[(*i)++];
if(e<0) { T = NULL;} else
{ T = ( BiTree )malloc(sizeof( struct BiTreeNode ) );
T->Element = e;
T->Left = CreateBiTreeArray(a, i, n);
T->Right = CreateBiTreeArray(a, i, n);
}
return T;
}
BiTree MakeEmptyBiTree( BiTree T )
{ if( !T )
{ MakeEmptyBiTree( T->Left );
MakeEmptyBiTree( T->Right );
free( T );
}
return NULL;
}
Status IsEmpytBiTree( BiTree T)
{ if(!T) return TRUE;
else return FALSE;
}
int BiTreeDepth(BiTree T)
{ int h1,h2;
if(!T)
return 0;
else
{ h1=BiTreeDepth(T->Left);
h2=BiTreeDepth(T->Right);
if(h1>h2)
return h1+1;
else
return h2+1;
}
}
void BiTreePreOrder( BiTree T )
{ if( T != NULL )
{ printf("%d\t", T->Element); BiTreePreOrder(T->Left);
BiTreePreOrder(T->Right);
}
}
void BiTreeInOrder( BiTree T )
{ if(T)
{ BiTreeInOrder(T->Left);
printf("%d\t", T->Element); BiTreeInOrder(T->Right);
}
}
void BiTreePostOrder( BiTree T )
{ if(T)
{ BiTreePostOrder(T->Left);
BiTreePostOrder(T->Right);
printf("%d\t", T->Element); }
}
测试
BiTree T = NULL;
printf("\n请输入元素，例如:1,2,-1,-1,3,-1,-1\n"); T = CreateBiTreeHand();
printf("\n先序遍历：(高度 %d)，是否为空 %d\n", BiTreeDepth(T), IsEmpytBiTree(T)); BiTreePreOrder(T);
printf("\n--END.\n\n"); printf("\n中序遍历：(高度 %d)，是否为空 %d\n", BiTreeDepth(T), IsEmpytBiTree(T)); BiTreeInOrder(T);
printf("\n--END.\n\n"); printf("\n后序遍历：(高度 %d)，是否为空 %d\n", BiTreeDepth(T), IsEmpytBiTree(T)); BiTreePostOrder(T);
printf("\n--END.\n\n"); MakeEmptyBiTree(T);
BiTree T1 = NULL, T2 = NULL;
int i,n;
TElementType a1[] = {1, 2, -1, -1, 3, -1, -1}; TElementType a2[] = {10, 20, -1, 30, -1, -1, -1}; i=0;
n=7;
T1 = CreateBiTreeArray(a1, &i, n);
printf("\nT1 二叉树\n"); printf("\n先序遍历：(高度 %d)，是否为空 %d\n", BiTreeDepth(T1), IsEmpytBiTree(T1)); BiTreePreOrder(T1);
printf("\n--END.\n\n"); printf("\n中序遍历：(高度 %d)，是否为空 %d\n", BiTreeDepth(T1), IsEmpytBiTree(T1)); BiTreeInOrder(T1);
printf("\n--END.\n\n"); printf("\n后序遍历：(高度 %d)，是否为空 %d\n", BiTreeDepth(T1), IsEmpytBiTree(T1)); BiTreePostOrder(T1);
printf("\n--END.\n\n"); MakeEmptyBiTree(T1);
i=0;
n=7;
T2 = CreateBiTreeArray(a2, &i, n);
printf("\nT2 二叉树\n"); printf("\n先序遍历：(高度 %d)，是否为空 %d\n", BiTreeDepth(T2), IsEmpytBiTree(T2)); BiTreePreOrder(T2);
printf("\n--END.\n\n"); printf("\n中序遍历：(高度 %d)，是否为空 %d\n", BiTreeDepth(T2), IsEmpytBiTree(T2)); BiTreeInOrder(T2);
printf("\n--END.\n\n"); printf("\n后序遍历：(高度 %d)，是否为空 %d\n", BiTreeDepth(T2), IsEmpytBiTree(T2)); BiTreePostOrder(T2);
printf("\n--END.\n\n"); MakeEmptyBiTree(T2);