【数据结构】二叉树的链式结构

目录

一.二叉树的遍历

1.前序遍历

2.中序遍历

3.后序遍历

4.层序遍历

二.二叉树查询的基本操作

1.二叉树节点的个数

2.二叉树叶子节点的个数

3.二叉树的高度

4.二叉树第k层节点的个数

5.二叉树查询值为x的节点

6.判断二叉树是否为完全二叉树

7.二叉树基础oj练习

三.二叉树的创建和销毁

1.创建

2.销毁

---

一.二叉树的遍历

学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉 树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历 是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。

为了使遍历更加的形象，在这里我们先受搓一颗二叉树来说明二叉树的遍历。

typedef int BTDataType;
 
typedef struct BinaryTreeNode
{
    BTDataType data;
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
}BTNode;
 
BTNode* BuyNode(BTDataType x)
{
    BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
    if (newnode == NULL)
    {
        perror("malloc");
        return;
    }
    newnode->data = x;
    newnode->left = NULL;
    newnode->right = NULL;
    return newnode;
}
 
BTNode* CreateBinaryTree()
{
    BTNode* node1 = BuyNode(1);
    BTNode* node2 = BuyNode(2);
    BTNode* node3 = BuyNode(3);
    BTNode* node4 = BuyNode(4);
    BTNode* node5 = BuyNode(5);
    BTNode* node6 = BuyNode(6);
 
    node1->left = node2;
    node1->right = node4;
    node2->left = node3;
    node4->left = node5;
    node4->right = node6;
    return node1;
}

注意：上述代码并不是创建二叉树的方式 

再看二叉树基本操作前，再回顾下二叉树的概念，二叉树是：

1. 空树

2. 非空：根节点，根节点的左子树、根节点的右子树组成的。

从概念中可以看出，二叉树定义是递归式的，因此后序基本操作中基本都是按照该概念实现的。 

1.前序遍历

前序遍历是以根———左子树——右子树的顺序进行遍历的。

这里的N表示的是NULL。

用代码表示：

void PreOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("N ");
        return;
    }
    printf("%d ", root->data);
    PreOrder(root->left);
    PreOrder(root->right);
}

2.中序遍历

前序遍历是以左子树———根——右子树的顺序进行遍历的。

用代码表示：

void MiddleOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("N ");
        return;
    }
    MiddleOrder(root->left);
    printf("%d ", root->data);
    MiddleOrder(root->right);
}

3.后序遍历

前序遍历是以左子树———右子树——根的顺序进行遍历的。

用代码表示：

void PostOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("N ");
        return;
    }
    PostOrder(root->left);
    PostOrder(root->right);
    printf("%d ", root->data);
}

4.层序遍历

层序遍历需要用到队列的代码，所以我们要将之前队列的代码【数据结构】栈和队列-CSDN博客移动到现在所在的工程文件中。

思路：首先创建一个队列，将二叉树的根节点插入到队列当中。接着用while循环判断队列是否为空作为判断条件，pop掉队头的数据，然后将队头数据的左右子树分别带出来，前提是左右子树都不为空。最后销毁队列就可以了。

void TreeLevelOrder(BTNode* root)
{
    Queue pq;
    QueueInit(&pq);
    if (root)
    {
        QueuePush(&pq, root);
    }
    while (!QueueEmpty(&pq))
    {
        BTNode* front = QueueFront(&pq);
        QueuePop(&pq);
        printf("%d ", front->data);
        if (front->left)
        {
            QueuePush(&pq, front->left);
        }
        if (front->right)
        {
            QueuePush(&pq, front->right);
        }
    }
    QueueDestroy(&pq);
}

二.二叉树查询的基本操作

1.二叉树节点的个数

int BinaryTreeSize(BTNode* root)
{
    if (root == NULL)
    {
        return 0;
    }
    int left = BinaryTreeSize(root->left);
    int right = BinaryTreeSize(root->right);
    return left + right + 1;
}

在这里，我们采用递归的方法，递归的结束条件是节点为NULL，子问题是左右子树在加上根节点的数量（也就是1）。

2.二叉树叶子节点的个数

int BinaryTreeLeafSize(BTNode* root)
{
    if (root == NULL)
    {
        return 0;
    }
    if (root->left == NULL && root->right == NULL)
    {
        return 1;
    }
    int left = BinaryTreeLeafSize(root->left);
    int right = BinaryTreeLeafSize(root->right);
    return left + right;
}

递归的结束条件是左右子树都为空，且结束时需要返回1。

3.二叉树的高度

int BinaryTreeHeight(BTNode* root)
{
    if (root == NULL)
    {
        return 0;
    }
    int left = BinaryTreeHeight(root->left);
    int right = BinaryTreeHeight(root->right);
    return left > right ? left + 1 : right + 1;
}

递归的结束条件是节点为空，子问题是计算左右子树的高度并且返回高度比较高的子树。

4.二叉树第k层节点的个数

int BinaryTreeLevelKSize(BTNode* root, int k)
{
    if (root == NULL)
    {
        return 0;
    }
    if (k == 1)
    {
        return 1;
    }
    int left = BinaryTreeLevelKSize(root->left, k - 1);
    int right = BinaryTreeLevelKSize(root->right, k - 1);
    return left + right;
}

递归的结束条件是k==1，并且返回1。

如果k的值为3，则可以得到如下流程图：

5.二叉树查询值为x的节点

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
    if (root == NULL)
    {
        return NULL;
    }
    if (root->data == x)
    {
        return root;
    }
    BTNode* left = BinaryTreeFind(root->left, x);
    if (left)
    {
        return left;
    }
    BTNode* right = BinaryTreeFind(root->right, x);
    if (right)
    {
        return right;
    }
    return NULL;
}

这里思路是遍历一遍二叉树，若找到，则返回给上一层。最后，若左子树或者右子树不为空，则说明找到了指定的节点。若没有找到，则返回NULL。

6.判断二叉树是否为完全二叉树

思路：这道题需要我们用到层序遍历，与层序遍历不同的是，我们要将NULL也带入到队列之中。当遇到第一个NULL时，break跳出来。然后判断之后队列之中的指针是否为空，若有空指针，返回假。若循环完，则返回真。

// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
    Queue pq;
    QueueInit(&pq);
    if (root)
    {
        QueuePush(&pq, root);
    }
    while (!QueueEmpty(&pq))
    {
        BTNode* front = QueueFront(&pq);
        QueuePop(&pq);
        if (front == NULL)
        {
            break;
        }
        QueuePush(&pq, front->left);
        QueuePush(&pq, front->right);
    }
    while (!QueueEmpty(&pq))
    {
        BTNode* front = QueueFront(&pq);
        QueuePop(&pq);
        if (front!=NULL)
        {
            QueueDestroy(&pq);
            return false;
        }
    }
    QueueDestroy(&pq);
    return true;
}

7.二叉树基础oj练习

接下来，我们根据刚才介绍的几种基本操作为基础完成几道oj练习：

965. 单值二叉树 - 力扣（LeetCode）

思路：为了方便操作，我们可以在创建一个函数，将根节点的值作为参数传给所创建的函数。依然采用递归的方法，结束条件是root为空或者root的值不等于val值。子问题是左右子树是否为单值二叉树。

100. 相同的树 - 力扣（LeetCode）

思路：用递归，结束条件是两个节点都为空，返回true，或者一个为空一个不为空，返回false，或者两个节点的值不相等，返回false。子问题是左右子树是否相等。

 101. 对称二叉树 - 力扣（LeetCode）

 思路：这道题同样是先创建一个新的函数，将左右子树的根节点传过去，再使用递归解决问题，结束条件是两个节点都为空，返回true，或者一个为空一个不为空，返回false，或者两个节点的值不相等，返回false。子问题是左子树的右节点是否跟右子树的左节点是否相等。

144. 二叉树的前序遍历 - 力扣（LeetCode）

思路：先用递归将二叉树遍历一遍，计算出二叉树节点的个数returnSize。在开辟returnSize个整形的空间，然后使用前序遍历将二叉树中的节点放到开辟的空间里面。

572. 另一棵树的子树 - 力扣（LeetCode）

思路：先创建一个函数，作用是判断两颗二叉树是否相等，参数是两颗二叉树的根节点。然后使用递归的方法，结束条件是节点为空，返回NULL，或者判断两颗是相等的，返回true。子问题是遍历一遍二叉树，判断是否有子树和指定的数相等。

三.二叉树的创建和销毁

1.创建

关于二叉树的创建，我们利用一道OJ题目来展示：

二叉树遍历_牛客题霸_牛客网 (nowcoder.com)

这道题输入的数据展开的数据所组成的二叉树为上图。

思路：将输入的数组组成一颗二叉树，再将二叉树一中序遍历的方法输出出来。

2.销毁

void TreeDestory(BTNode* root)
{
    if (root == NULL)
        return;
 
    TreeDestory(root->left);
    TreeDestory(root->right);
    free(root);
}