队列建立完全二叉树

时间:2022-12-15 17:31:59

完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

比如下面这棵树就是一棵完全二叉树

队列建立完全二叉树

通过图片我们可以了解到它的创建过程是从上到下,从左至右的,也就是说,它是一层一层建立的。

完全二叉树有以下基本性质:

  1. 对于一棵有n个结点的完全二叉树,其任意结点 i (1<=i<=n),如果 i = 1, 则结点 i 是二叉树的根,无双亲; 如果 i>1,则其双亲parent(i)是结点 i/2.

  2. 如果 2i>n; 则结点 i 无左孩子(结点 i 为叶子结点 ); 否则其左孩子lchild(i)是结点 2i.

  3. 如果 2i+1>n, 则结点 i 无右孩子; 否则其右孩子rchild(i)是结点 2i+1.

    建立一棵完全二叉树,关键要处理好亲子之间的关系,对此我做出了如下总结:

一种是边生孩子边找关系,在生成新结点时把它的父亲结点指出来; 还有一种就是 生完孩子在找关系,即先生成树中的所有结点,再去指出结点之间的父子关系.

为了确定树之间的这种关系,我们需要借助一个辅助的存储空间,比如一个数组或是堆栈或队列,这里我用一个顺序队列来实现.

采用先生孩子后找关系的顺序来生成这颗二叉树,先生成树中所有结点并将其入队,再指出其父子关系,图片描述如下:
队列建立完全二叉树

具体实现代码如下:

#include<stdio.h>
#include<stdlib.h>

typedef struct bitree
{
int data;
struct bitree *lchild,*rchild;
}BiTNode;

//////////////函数声明
BiTNode* CreateBiTree(int *,int);
void PreOderTraverse(BiTNode *);
void DestoryBiTree(BiTNode *);

int main()
{
BiTNode *t;

int a[10] = {1,4,6,7,2,5,3,9,8}; //树中结点的数据

t = CreateBiTree(a,10);

PreOderTraverse(t);

DestoryBiTree(t);

return 0;
}

///////////////////创建二叉树
BiTNode* CreateBiTree(int *a,int n)
{
BiTNode *root,*p;
BiTNode *bitQueue[n]; //定义一个队列用来存放完全二叉树
int front=1,rear=1; //初始化队列

////////////////////////////////////////////////生成结点并入队
for(int i=0; i<n; i++)
{
if(*(a+i) == 0)
p = NULL;
else
{
p = (BiTNode *)malloc(sizeof(BiTNode));
p->data = *(a+i);
p->lchild = p->rchild = NULL;
}
bitQueue[rear++] = p; //p结点入队,队尾指针加 1
if(i==0) root = p; //初始化根节点
}
/////////////////////////////////////////////找出结点间的父子关系
while(front != rear) //如果队列不为空
{
p = bitQueue[front]; //当前要找关系的结点
if(p != NULL)
{
if(2*front <= n) p->lchild = bitQueue[2*front];
//根据完全二叉树性质,如果2i<n,(n为该二叉树中总结点个数),则该结点有左孩子为2i
if(2*front+1 <= n) p->rchild = bitQueue[2*front+1];
//如果2i<n,(n为该二叉树中总结点个数),则该结点有左孩子为2i+1
}
front++; //队头指针加 1,指向下一个结点
}

return root;
}

//////////////////前序遍历
void PreOderTraverse(BiTNode *t)
{
if(t) //如果树不为空
{
printf("%d ",t->data);
PreOderTraverse(t->lchild);
PreOderTraverse(t->rchild);
}
}

//////////////////销毁二叉树
void DestoryBiTree(BiTNode *t)
{
if(t)
{
if(t->lchild)
DestoryBiTree(t->lchild);
if(t->rchild)
DestoryBiTree(t->rchild);
free(t);
t = NULL;
}
}