阅读:0       作者:严长生

二叉树的链式存储结构及实现(C语言完整代码+详细注释)

链式存储结构存储二叉树,实际上就是采用链表存储二叉

既然是使用链表,首先需要构建链表中节点的结构。考虑到存储对象为二叉树,其各个节点最多包含 3 部分,依次是:左孩子、节点数据和右孩子,因此,链表的每个节点都由这 3 部分组成:


1 二叉链表结点构成

图 1 中,Lchild 代表指向左孩子的指针域;data 为数据域;Rchild 代表指向右孩子的指针域。使用此种结点构建的二叉树称为“二叉链表”

结点结构用代码表示为:
typedef struct BiTNode{
    TElemType data;//数据域
    struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;
如果后期再使用链表的过程中需要频繁地访问某结点的父结点,可以在构建链表时使用下面这种结点结构:


图 2 三叉链表结点构成

图 2 中,Lchild 指向左孩子;Rchild 指向右孩子;data 为数据域;parent 指向父结点。使用这种结构的结点创建的树称为“三叉链表”

结点结构代码表示:
typedef struct BiTNode{
    TElemType data;//数据域
    struct BiTNode *lchild,*rchild;//左右孩子指针
    struct BiTNode *parent;
}BiTNode,*BiTree;
例如,下图为分别用以上两种节点结构构建的二叉树:
 


图 3 单支树示意图

图 3 中二叉链表的C语言实现代码如下:
#include <stdio.h>
#include <stdlib.h>
#define TElemType int

typedef struct BiTNode{
    TElemType data;//数据域
    struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;

void CreateBiTree(BiTree *T){
    *T=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->data=1;
    (*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->rchild=NULL;
    (*T)->lchild->data=2;            
    (*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->rchild=NULL;
    (*T)->lchild->lchild->data=3;
    (*T)->lchild->lchild->lchild=NULL;
    (*T)->lchild->lchild->rchild=NULL;
}
int main() {
    BiTree Tree;
    CreateBiTree(&Tree);
    printf("%d",Tree->lchild->lchild->data);
    return 0;
}
运行结果:
3