二叉树
二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”。
相关术语
一棵深度为k，且有2^k-1 个结点的二叉树，称为满二叉树；
在一棵二叉树中，除最后一层外，若其余层都是满的，并且或者最后一层是满的，或者是在右边缺少连续若干结点，则此二叉树为完全二叉树；
所有节点都只有左子树，称为左斜树；
所有节点都只有右子树，称为右斜树；
性质
在二叉树的第i层上最多有2^i-1 个结点
深度为K的二叉树最多有2^k -1 个结点(K>=1)
对于任何一颗二叉树T,如果其终端结点数为n0,度为2的结 点数为n2,则n0 = n2 + 1;
具有n个结点的完全二叉树的深度为[log2n] + 1
顺序结构
初始化
BOOL InitBiTree(SqBiTree T){
for (int i = 0; i < MAXSIZE;i++)
{
T[i] = Nil;
}
return true;
}
创建二叉树
BOOL createBiTree(SqBiTree T) {
int i = 0;
while (i < 10) {
T[i] = i+1;
printf("%d ",T[i]);
//结点不为空,且无双亲结点
if (i != 0 && T[(i+1)/2-1] == Nil && T[i] != Nil) {
printf("出现无双亲的非根结点%d\n",T[i]);
exit(0);
}
i++;
}
//将空赋值给T的后面的结点
while (i < MAXSIZE) {
T[i] = Nil;
i++;
}
return true;
}
是否空树
//是否空树
BOOL isEmpty(SqBiTree T){
return T[0] == Nil;
}
获取深度
int BiTreeDepth(SqBiTree T){
int j = -1;
int i;
for (i = MAXSIZE - 1; i >= 0; i--)
{
if (T[i] != Nil)
{
break;
}
}
do{
j++;
}while(pow(2,j) <= i);
return j;
}
获取E点的值
//获取E点的结点值
CElemType getValue(SqBiTree T,Position e){
return T[pow(2,e.level - 1) + e.order - 2];
}
//插入值至位置e
BOOL Assign(SqBiTree T,Position e ,CElemType value){
int i = pow(2,e.level - 1) + e.order - 2;
if (T[(i + 1) / 2 - 1] == Nil ){
return false;
}
T[i] = value;
return true;
}
插入结点
//插入值至位置e
BOOL Assign(SqBiTree T,Position e ,CElemType value){
int i = pow(2,e.level - 1) + e.order - 2;
if (T[(i + 1) / 2 - 1] == Nil ){
return false;
}
T[i] = value;
return true;
}
左子结点
int leftChild(SqBiTree T,Position e){
return T[(int)(pow(2, e.level-1)+e.order-2) * 2 + 1 ];
}
右子结点
int rightChild(SqBiTree T,Position e){
return T[(int)(pow(2, e.level-1)+e.order-2) * 2 + 2 ];
}
双亲结点
int fatherNode(SqBiTree T,Position e){
if (e.level != 1)
{
return T[(int)(pow(2, e.level-1)+e.order-2) / 2 - 1];
}
return -1;
}
前序遍历（中左右）
void PreTraverse(SqBiTree T,int e){
//打印结点数据
printf("%d ",T[e]);
//先序遍历左子树
if (T[2 * e + 1] != Nil) {
PreTraverse(T, 2*e+1);
}
//最后先序遍历右子树
if (T[2 * e + 2] != Nil) {
PreTraverse(T, 2*e+2);
}
}
BOOL PreOrderTraverse(SqBiTree T){
//树不为空
if (!isEmpty(T)) {
PreTraverse(T, 0);
}
printf("\n");
return true;
}
中序遍历（左中右）
void InTraverse(SqBiTree T, int e){
/* 左子树不空 */
if (T[2*e+1] != Nil)
InTraverse(T, 2*e+1);
printf("%d ",T[e]);
/* 右子树不空 */
if (T[2*e+2] != Nil)
InTraverse(T, 2*e+2);
}
BOOL InOrderTraverse(SqBiTree T){
/* 树不空 */
if (!isEmpty(T)) {
InTraverse(T, 0);
}
printf("\n");
return true;
}
后序遍历
void PostTraverse(SqBiTree T,int e)
{ /* 左子树不空 */
if(T[2*e+1]!=Nil)
PostTraverse(T,2*e+1);
/* 右子树不空 */
if(T[2*e+2]!=Nil)
PostTraverse(T,2*e+2);
printf("%d ",T[e]);
}
BOOL PostOrderTraverse(SqBiTree T)
{
if(!isEmpty(T)) /* 树不空 */
PostTraverse(T,0);
printf("\n");
return true;
}
链式存储
结构
typedef char CElemType;
CElemType Nil=' '; /* 字符型以空格符为空 */
typedef struct BiTNode /* 结点结构 */
{
CElemType data; /* 结点数据 */
struct BiTNode *lchild,*rchild; /* 左右孩子指针 */
}BiTNode,*BiTree;
初始化
BOOL InitBiTree(BiTree *T)
{
*T=NULL;
return true;
}
销毁二叉树
void DestroyBiTree(BiTree *T)
{
if(*T)
{
/* 有左孩子 */
if((*T)->lchild)
DestroyBiTree(&(*T)->lchild); /* 销毁左孩子子树 */
/* 有右孩子 */
if((*T)->rchild)
DestroyBiTree(&(*T)->rchild); /* 销毁右孩子子树 */
free(*T); /* 释放根结点 */
*T=NULL; /* 空指针赋0 */
}
}
创建二叉树,#表示空树
void CreateBiTree(BiTree *T){
CElemType ch;
//获取字符
ch = str[indexs++];
//判断当前字符是否为'#'
if (ch == '#') {
*T = NULL;
}else
{
//创建新的结点
*T = (BiTree)malloc(sizeof(BiTNode));
//是否创建成功
if (!*T) {
exit(OVERFLOW);
}
/* 生成根结点 */
(*T)->data = ch;
/* 构造左子树 */
CreateBiTree(&(*T)->lchild);
/* 构造右子树 */
CreateBiTree(&(*T)->rchild);
}
}
判断二叉树是否为空
BOOL BiTreeEmpty(BiTree T)
{
if(T)
return false;
else
return true;
}
二叉树的深度
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;
//比较i和j
return i>j?i+1:j+1;
}
根结点
CElemType getRoot(BiTree T){
if (BiTreeEmpty(T))
return Nil;
return T->data;
}
获取结点的值
CElemType getValue(BiTree p){
return p->data;
}
给结点赋值
void Assign(BiTree p,CElemType value)
{
p->data=value;
}
前序遍历
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 ;
InOrderTraverse(T->lchild); /* 中序遍历左子树 */
printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */
InOrderTraverse(T->rchild); /* 最后中序遍历右子树 */
}
后序遍历
void PostOrderTraverse(BiTree T)
{
if(T==NULL)
return;
PostOrderTraverse(T->lchild); /* 先后序遍历左子树 */
PostOrderTraverse(T->rchild); /* 再后序遍历右子树 */
printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */
}
网友评论