（数据结构）二叉树的链式存储结构_二叉树链式存储结构

二叉树的顺序存储的缺点

因为并不是每个二叉树都是完全二叉树，普通二叉树使用顺序表存储或多或少会存在空间浪费的现象

图 1 普通二叉树的转化

如上图 1，普通二叉树里只有二个元素，最好的存储方式当然是开辟相对应的空间，但是顺序存储结构却让我们不能这么做！也就是说我们此时必须花更多的空间去存储相对少的元素

二叉树的链式存储

先慢慢介绍一下链式存储的节点结构！！！

图 2 普通二叉树示意图

如上图 2 所示，若将其采用链式存储，则只需从树的根节点开始，将各个节点及其左右孩子使用链表存储

因此，图 2 对应的链式存储结构如下图 3 所示：

图 3 二叉树链式存储结构示意图

 由上图 3 可知，采用链式存储二叉树时，其节点结构由 3 部分构成：

图 4 二叉树节点结构

 此时我们直接用结构体声明一下节点的类型！！！and 头文件

#include <stdio.h>
#include <stdlib.h>
 
typedef struct MyBiTNode{
    int data;  // 数据域
    struct MyBiTNode *lchild, *rchild;  // 左右孩子指针
} BiTNode;

然后根据图 3 来定义主要函数体（自行消化）

BiTNode *CreateBiTree(BiTNode *T){
	// 结点 1 
    T = (BiTNode*)malloc(sizeof(BiTNode));
    T->data = 1;
    // 结点 2
	T->lchild = (BiTNode*)malloc(sizeof(BiTNode));
	T->lchild->data = 2;
	T->lchild->rchild = NULL;
	// 结点 3
	T->rchild = (BiTNode*)malloc(sizeof(BiTNode));
    T->rchild->data = 3;
	T->rchild->lchild = NULL; 
	T->rchild->rchild = NULL;
	// 结点 4 
	T->lchild->lchild = (BiTNode*)malloc(sizeof(BiTNode));
	T->lchild->lchild->data = 4;
	T->lchild->lchild->lchild = NULL;
	T->lchild->lchild->rchild = NULL;
	return T;
}
 
int main() {
    BiTNode *Tree = NULL;  // 结构体指针指向空 
    Tree = CreateBiTree(Tree);  // 传入结构体指针 
    printf("%d\n",Tree->lchild->lchild->data);  // 4 
    return 0;
}

但是还不能算真的实现了二叉树的链式存储（还不够完善）

在某些实际场景中，可能需要查找某节点的父节点，这时可以在节点结构中再添加一个指针域，用于各个节点指向其父亲节点

优化后的链式存储结构如下图 5 所示（通常称为三叉链表）：

图 5 优化后二叉树的链式存储结构

 此时我们直接用结构体声明一下节点的类型！！！and 头文件

#include <stdio.h>
#include <stdlib.h>
 
typedef struct MyBiTNode{
    int data;  // 数据域
    struct MyBiTNode *lchild, *rchild;  // 左右孩子指针
    struct MyBiTNode *parent;  // 父指针
} BiTNode;

 然后根据图 5 来定义主要函数体（自行消化）

BiTNode *CreateBiTree(BiTNode *T){
	// 结点 1 
    T = (BiTNode*)malloc(sizeof(BiTNode));
    T->data = 1;
    T->parent = NULL;
    // 结点 2
	T->lchild = (BiTNode*)malloc(sizeof(BiTNode));
	T->lchild->data = 2;
	T->lchild->rchild = NULL;
	T->lchild->parent = T;
	// 结点 3
	T->rchild = (BiTNode*)malloc(sizeof(BiTNode));
    T->rchild->data = 3;
	T->rchild->lchild = NULL; 
	T->rchild->rchild = NULL;
	T->rchild->parent = T;
	// 结点 4 
	T->lchild->lchild = (BiTNode*)malloc(sizeof(BiTNode));
	T->lchild->lchild->data = 4;
	T->lchild->lchild->lchild = NULL;
	T->lchild->lchild->rchild = NULL;
	T->lchild->lchild->parent = T->lchild;
	return T;
}
 
int main() {
    BiTNode *Tree = NULL;  // 结构体指针指向空 
    Tree = CreateBiTree(Tree);  // 传入结构体指针 
    printf("%d\n",Tree->lchild->lchild->parent->data);  // 2
    return 0;
}