数据结构与算法——C语言描述 二叉树的存储结构

上一篇 树和二叉树的概念和定义：https://www.cnblogs.com/prinzeugen/p/12805870.html

二叉树的存储结构

二叉树的顺序存储结构

二叉树的顺序结构就是将所有的结点按照一定的次序，顺序存储在一维数组当中，并且结点的存储位置，也就是数组的下标要能够体现出节点之间的逻辑关系，例如双亲和孩子的关系、左右兄弟的关系等。

将这棵二叉树存入数组中，相应的下标对应同样的位置。

如果某一结点的左孩子或者右孩子空缺，则数组中的相应位置也空出来。

这样的设计可以更方便地用二叉树的性质在数组中定位二叉树的孩子结点和双亲节点。比如上图中的结点4（他的下标也是4），结点4是结点2的孩子，结点2的下标可以直接通过计算来得出：

结点2的下标：4/2=2

但是，用顺序存储结构来表示二叉树也有着明显的缺点。对于一个稀疏的二叉树来说，用数组表示法是非常浪费空间的。在坏的情况下，一棵深度为k、只有k个结点的右斜树，却需要为其分配2^k-1个存储单元空间。因此，顺序存储结构一般只用于完全二叉树。

二叉链表

对于较为稀疏的二叉树，我们就要考虑链式存储结构。二叉树每个结点最多有两个孩子，因此人们就为它设计了一个数据域和两个指针域，这样的链表就被称为二叉链表。

如果二叉树含有n个结点，则它的二叉链表必含有2n个指针域，其中必有n+1个是空的链域。

二叉树结点及定义

/*二叉树的二叉链表结点结构定义*/
typedef struct Node{
    TElemType data;//结点的数据域
    struct Node *LChild;//左孩子指针域
    struct Node *RChild;//右孩子指针域
}BitNode,*BiTree

其中data是数据域，LChild和RChild都是指向左右孩子的指针域。

遍历二叉树

1.前序遍历

若二叉树为空，则空操作返回，否则：

1. 访问根结点
2. 按先序遍历左子树
3. 按先序遍历右子树

例如下图，遍历的顺序为：ABCDEFGHK

二叉树的前序遍历算法代码：

void PreOrderTraverse(BiTree tree){
    if(tree!=NULL){
        printf("%c",tree->data);    //输出其结点的值
        PreOrderTraverse(tree->LeftChild);  //访问其左子树
        PreOrderTraverse(tree->RightChild); //访问其右子树
    }
}

2.中序遍历

若二叉树为空，则空操作返回，否则：

1. 按中序遍历左子树
2. 访问根结点
3. 按中序遍历右子树

上图的中序遍历为：BDCAEHGKF

二叉树的中序遍历算法代码：

void InOrderTraverse(BiTree tree){
    if(tree!=NULL){
        InOrderTraverse(tree->LeftChild);  //访问其左子树
        printf("%c",tree->data);    //输出其结点的值
        InOrderTraverse(tree->RightChild); //访问其右子树
    }
}

3.后续遍历

若二叉树为空，则空操作返回，否则：

1. 按后续遍历访问左子树
2. 按后续遍历访问右子树
3. 访问根结点

上图的后续遍历为：DCBHKGFEA

二叉树的后序遍历算法代码：

void PostOrderTraverse(BiTree tree){
    if(tree!=NULL){
        InOrderTraverse(tree->LeftChild);  //访问其左子树
        InOrderTraverse(tree->RightChild); //访问其右子树
        printf("%c",tree->data);    //输出其结点的值
    }
}

可以得到二叉树遍历的两个性质

1. 已知前序遍历和中序遍历，可以唯一确定一棵二叉树。
2. 已知后序遍历和中序遍历，可以唯一确定一棵二叉树。
3. 但是前序遍历和后序遍历，是不可以确定一棵二叉树的。

二叉树的建立

为了要让在每个结点是否有其左右孩子，我们需要在二叉树每个结点的空指针引出一个虚结点，其数据域用一定的特定值表示，例如“#”。这样的二叉树就被称为原来二叉树的扩展二叉树，它就可以做到一个遍历序列确定一棵二叉树。

例如我们要实现上面的那棵二叉树，我们只要将AB#DF##G##C#E#H##用键盘依次输入即可。

代码如下：

void CreateBiTree(BiTree *tree){
    char input; //用于接收新结点的数据
    printf("请输入新结点的内容:");
    scanf_s("%c",&input);
    getchar();
    if(input==‘#‘)  //若输入“#”时，停止创建该结点
        *tree=NULL;
    else{
        *tree=(BiTree)malloc(sizeof(BitNode));
        (*tree)->data=input;    //将接收的输入值赋给新结点的数据域
        CreateBiTree(&((*tree)->LeftChild));    //生成其左子树
        CreateBiTree(&((*tree)->RightChild));    //生成其右子树
    }
}

建立二叉树，其实也使用了递归的原理。

完整代码如下：

/**
 * @brief 二叉树结点结构定义
 */
typedef struct Node{
    char data;   //结点数据
    struct Node *LeftChild; //左孩子的指针
    struct Node *RightChild;//右孩子的指针
}BitNode,*BiTree;

/**
 * @brief 创建二叉树
 * @param tree
 */
void CreateBiTree(BiTree *tree){
    char input; //用于接收新结点的数据
    printf("请输入新结点的内容:");
    scanf_s("%c",&input);
    getchar();
    if(input==‘.‘)  //若输入“.”时，停止创建该结点
        *tree=NULL;
    else{
        *tree=(BiTree)malloc(sizeof(BitNode));
        (*tree)->data=input;    //将接收的输入值赋给新结点的数据域
        CreateBiTree(&((*tree)->LeftChild));    //生成其左子树
        CreateBiTree(&((*tree)->RightChild));    //生成其右子树
    }
}

/**
 * @brief 前序遍历二叉树
 * @param tree
 */
void PreOrderTraverse(BiTree tree){
    if(tree!=NULL){
        printf("%c",tree->data);    //输出其结点的值
        PreOrderTraverse(tree->LeftChild);  //访问其左子树
        PreOrderTraverse(tree->RightChild); //访问其右子树
    }
}

/**
 * @brief 中序遍历二叉树
 * @param tree
 */
void InOrderTraverse(BiTree tree){
    if(tree!=NULL){
        InOrderTraverse(tree->LeftChild);  //访问其左子树
        printf("%c",tree->data);    //输出其结点的值
        InOrderTraverse(tree->RightChild); //访问其右子树
    }
}

/**
 * @brief 后序遍历二叉树
 * @param tree
 */
void PostOrderTraverse(BiTree tree){
    if(tree!=NULL){
        InOrderTraverse(tree->LeftChild);  //访问其左子树
        InOrderTraverse(tree->RightChild); //访问其右子树
        printf("%c",tree->data);    //输出其结点的值
    }
}

int main() {
    char target=‘0‘;
    BiTree tree;
    CreateBiTree(&tree);    //创建二叉树
    printf("前序遍历结果:");
    PreOrderTraverse(tree); //前序遍历二叉树
    printf("\n中序遍历结果:");
    InOrderTraverse(tree);  //中序遍历二叉树
    printf("\n后序遍历结果:");
    PostOrderTraverse(tree);//后续遍历二叉树
    return 0;
}