硬核技术——二叉树的存储方式

CC老师

发布于 2022-01-13 14:56:55

1360

发布于 2022-01-13 14:56:55

文章被收录于专栏：HelloCode开发者学习平台HelloCode开发者学习平台

二叉树

二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”。

性质

在二叉树的第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);/* 显示结点数据，可以更改为其它对结点操作 */
}

（滑动显示更多）

- END -

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2021-09-23，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树

编程算法

本文分享自 HelloCoder全栈小集微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

二叉树

编程算法

登录后参与评论

0 条评论

热度

硬核技术——二叉树的存储方式

硬核技术——二叉树的存储方式

相关术语

性质

顺序结构

链式存储

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐