二叉树链式存储结构详解

二叉树链式存储结构详解

引用

CSDN

1.

https://blog.csdn.net/2302_79546368/article/details/142897795

二叉树链式存储结构详解

1. 回顾引入

回顾二叉树的概念，二叉树分为空树和非空树，非空二叉树由根节点，根节点的左子树和根节点的右子树组成。

根节点的左子树和右子树分别又是由子树节点，子树节点的左子树和子树节点的右子树组成的，因此二叉树定义是递归式的，后续链式二叉树的操作中基本都是按照该概念实现的。

2. 遍历规则的介绍

2.1 前序遍历

前序遍历又称先序遍历：访问根节点的操作发生在遍历其左右子树之前。

访问顺序：根节点，左子树，右子树

2.2 中序遍历

中序遍历：访问根节点的操作发生在遍历其左右子树之中（间）。

访问顺序：左子树，根节点，右子树

2.3 后序遍历

后序遍历：访问根节点的操作发生在遍历其左右子树之后。

访问顺序：左子树，右子树，根节点

3. 链式二叉树的实现

在这里我们还是将其实现的部分分为三个部分：tree.h(二叉树的节点的结构的定义以及函数的声明部分），tree.c(函数功能的实现部分），test.c(函数功能的测试部分）

3.1 tree.h(二叉树的节点的结构的定义以及函数的声明部分）

#pragma once
#include <stdio.h>
#include <assert.h>
#include<stdlib.h>
#include<stdbool.h>
//链式结构树的节点的定义以及函数的声明
typedef  int BTDatatype;
typedef struct TreeNode
{
    BTDatatype data;
    struct TreeNode* left;
    struct TreeNode* right;
}BTNode;
//前序遍历
void PreOrder(BTNode* root);
//中序遍历
void InOrder(BTNode* root);
//后序遍历
void PostOrder(BTNode* root);
//二叉树节点的个数
int BinaryTreeSize(BTNode* root);
//二叉树叶子节点的个数
int BinaryTreeLeafSzie(BTNode* root);
//二叉树第k层节点的个数
int BinaryTreeLevelKSzie(BTNode* root,int k);
//二叉树的深度
int BinaryTreeDepth(BTNode* root);
//在二叉树中查找值为x 的节点
BTNode* BinaryTreeFind(BTNode* root, int x);
//二叉树的销毁
void BinaryTreeDestroy(BTNode* root);
//二叉树的层序遍历
void LevelOrder(BTNode* root);
//判断二叉树是否为完全二叉树
bool BinaryTreeComplete(BTNode* root);

ps:目前，我们在最开始学习二叉树的时候对二叉树的限制较少，在这里实现插入，删除之类的操作没有意义，后续会给大家更新到平衡树或者红黑树，二叉树会有限制，敬请期待！

3.2 tree.c(函数功能的实现部分）

3.2.1 前，中，后序遍历的实现

注意：可以结合前面的遍历规则进行理解！！！

//前序遍历
void PreOrder(BTNode* root)
{
    if (root == NULL)
    {
        return;
    }
    printf("%d ", root->data);
    PreOrder(root->left);
    PreOrder(root->right);
}
//中序遍历
void InOrder(BTNode* root)
{
    if (root == NULL)
    {
        return;
    }
    InOrder(root->left);
    printf("%d ", root->data);
    InOrder(root->right);
}
//后序遍历
void PostOrder(BTNode* root)
{
    if (root == NULL)
    {
        return;
    }
    PostOrder(root->left);
    PostOrder(root->right);
    printf("%d ", root->data);
}

除此之外，需要认真的队2二叉树的递归式定义好好理解。在这里函数的实现的部分体现的尤为明显。

3.2.2 其余函数功能的实现

//二叉树节点的个数
int BinaryTreeSize(BTNode* root)
{
    if (root == 0)
    {
        return 0;
    }
    return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
//二叉树叶子节点的个数
int BinaryTreeLeafSzie(BTNode* root)
{
    if (root == NULL)
    {
        return 0;
    }
    if (root->left == NULL && root->right == NULL)
    {
        return 1;
    }
    return BinaryTreeLeafSzie(root->left) + BinaryTreeLeafSzie(root->right) ;
}
//二叉树第k层节点的个数
int BinaryTreeLevelKSzie(BTNode* root, int k)
{
    if (root == NULL)
    {
        return 0;
    }
    if (k == 1)//判断是不是第k层
    {
        return 1;
    }
    //如果不是第k层就向下遍历
    return BinaryTreeLevelKSzie(root->left, k - 1) + BinaryTreeLevelKSzie(root->right, k - 1);
}
//二叉树的深度  左右子树分别遍历取较大值
int BinaryTreeDepth(BTNode* root)
{
    if (root == NULL)
    {
        return 0;
    }
    int leftDep = BinaryTreeDepth(root->left);
    int rightDep = BinaryTreeDepth(root->right);
    return leftDep > rightDep ? leftDep + 1 : rightDep + 1;
}
//在二叉树中查找值为x 的节点
BTNode* BinaryTreeFind(BTNode* root, int x)
{
    if (root == NULL)
    {
        return NULL;
    }
    if (root->data == x)
    {
        return root;
    }
    BTNode* leftfind = BinaryTreeFind(root->left, x);
    if (leftfind)
    {
        return leftfind;
    }
    BTNode* rightfind = BinaryTreeFind(root->right, x);
    if (rightfind)
    {
        return rightfind;
    }
    return NULL;
}
//二叉树的销毁 注意理解： 销毁我们需要通过形参改变实参   通过递归销毁
//先销毁的是左子树 其次是右子树 最后是根节点
void BinaryTreeDestroy(BTNode** root)
{
    if (root == NULL)
    {
        return;
    }
    BinaryTreeDestroy((*root)->left);
    BinaryTreeDestroy((*root)->right);
    free(*root);
    *root = NULL;
}
//二叉树的层序遍历
void LevelOrder(BTNode* root)
{
    //这需要利用队列的性质进行遍历
    //注意：这里是将节点的地址放进队列之中
    Queue q;
    QueueInit(&q);
    QueuePush(&q, root);
    while (!QueueEmpty(&q))
    {
        //取队头的节点的地址
        BTNode* front = QueueFront(&q);
        printf("%d ", front->data);
        //让队头的节点进项出栈,如果当前节点的左右节点不为空，就让进栈
        QueuePop(&q);
        if (front->left)
        {
            QueuePush(&q, front->left);
        }
        if (front->right)
        {
            QueuePush(&q, front->right);
        }
    }
    printf("\n");
    QueueDestroy(&q);
}
//判断二叉树是否为完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
    Queue q;
    QueueInit(&q);
    QueuePush(&q, root);
    while (!QueueEmpty(&q))
    {
        //取队头的节点的地址
        BTNode* front = QueueFront(&q);
        //让队头的节点进项出栈,如果当前节点的左右节点不为空，就让进栈
        QueuePop(&q);
        if (front == NULL)
        {
            break;
        }
        QueuePush(&q, front->left);
        QueuePush(&q, front->right);
    }
    while (!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);
        if (front)
        {
            QueueDestroy(&q);
            return false;
        }
    }
    QueueDestroy(&q);
    return true;
}

值得注意的是在实现层序遍历和判断二叉树是否为完全二叉树的时候我们用到了前面所学的队列这一数据结构的性质，来帮助实现层序遍历和判断二叉树是否为完全二叉树。

3.3 test.c(函数功能的测试部分）

#define  _CRT_SECURE_NO_WARNINGS
#include "tree.h"
BTNode* BuyNode(int x)
{
    BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
    if (newnode == NULL)
    {
        perror("malloc fail");
        exit(1);
    }
    newnode->data = x;
    newnode->left = newnode->right = NULL;
    return newnode;
}
int main()
{
    BTNode* node1 = BuyNode(10);
    BTNode* node2 = BuyNode(5);
    BTNode* node3 = BuyNode(19);
    BTNode* node4 = BuyNode(4);
    BTNode* node5 = BuyNode(8);
    BTNode* node6 = BuyNode(13);
    BTNode* node7 = BuyNode(24);
                                                 //	 10
    node1->left = node2, node1->right = node3;//   5    19
    node2->left = node4, node2->right = node5;// 4  8  13 24
    node3->left = node6, node3->right = node7;
    BTNode* phead = node1;
    printf("前序遍历的结果:");
    PreOrder(phead);
    printf("\n");
    printf("中序遍历的结果:");
    InOrder(phead);
    printf("\n");
    printf("后序遍历的结果:");
    PostOrder(phead);
    printf("\n");
    printf("二叉树的节点的个数为:%d\n", BinaryTreeSize(phead));
    printf("二叉树的叶子节点的个数为:%d\n", BinaryTreeLeafSzie(phead));
    printf("二叉树的第%d层节点的个数为:%d\n",3, BinaryTreeLevelKSzie(phead,3));
    if (BinaryTreeFind(phead,13))
    {
        printf("找到了\n");
    }
    else printf("未找到\n");
    printf("层序遍历的结果为:");
    LevelOrder(phead);
    bool a=BinaryTreeComplete(phead);
    if (a)
    {
        printf("该二叉树是完全二叉树\n");
    }
    else printf("该二叉树不是完全二叉树\n");
    BinaryTreeDestroy(&phead);
    
    return 0;
}

运行结果如下：

以上是测试代码，注意自己每写完一个函数功能就去测试，不要等着所有的函数写完才去测试。上面的测试代码所建立的二叉树正是前面的遍历规则中个大家所呈现的二叉树。大家可以前后对照着理解。不要只看，记得自己动手实现一下。养成良好的代码习惯在必要的时候也会事半功倍的！！！