数据结构（二叉树-2）

文章目录

一、 实现链式结构二叉树

　　1.1 Tree.h

　　1.2 Tree.c 前中后序遍历

　　　　前序遍历

　　　　中序遍历

　　　　后续遍历

　　1.2 Tree.c 结点个数

　　1.3Tree.c 叶子节点个数

　　1.4 Tree.c 二叉树的高度

　　1.5 Tree.c 层序遍历

　　1.6 判断是否为完全二叉树

　　1.7 销毁二叉树

　　test.c

一、 实现链式结构二叉树

⽤链表来表⽰⼀棵⼆叉树，即⽤链来指⽰元素的逻辑关系。 通常的⽅法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别⽤来给出该结点左孩⼦和右孩⼦所在的链结点的存储地址 ，其结构如下：

1.1 Tree.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
//定义二叉树的链式结构
//二叉树结点的结构
typedef int BTDataType;
typedef struct BinaryTreeNode
{
    int data;
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
}BTNode;
//前序遍历
void PreOrder(BTNode* root);
//中序遍历
void InOrder(BTNode* root);
//后序遍历 
void PostOrder(BTNode* root);
// ⼆叉树结点个数
int BinaryTreeSize(BTNode* root);
// ⼆叉树叶⼦结点个数
int BinaryTreeLeafSize(BTNode* root);
// ⼆叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
//⼆叉树的深度/⾼度
int BinaryTreeDepth(BTNode* root);
// ⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// ⼆叉树销毁
void BinaryTreeDestory(BTNode** root);
//层序遍历
void LevelOrder(BTNode* root);
//判断二叉树是否为完全二叉树
bool BinaryTreeComplete(BTNode* root);

下面我们可以在下方 test.c 文件中手动创建一棵链式二叉树，方便对链式结构二叉树遍历方式以及各种方法的实现的研究：

1.2 Tree.c 前中后序遍历

1. 前序遍历(Preorder Traversal 亦称先序遍历)：访问根结点的操作发⽣在遍历其左右⼦树之前 访问顺序为：根结点、左⼦树、右⼦树
2. 中序遍历(Inorder Traversal)：访问根结点的操作发⽣在遍历其左右⼦树之中（间） 访问顺序为：左⼦树、根结点、右⼦树
3. 后序遍历(Postorder Traversal)：访问根结点的操作发⽣在遍历其左右⼦树之后 访问顺序为：左⼦树、右⼦树、根结点

前序遍历

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

输出结果为： 1 2 4 3

其他两种遍历方式的递归过程也是一样的做法，下面就只展示代码部分了。

中序遍历

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

输出结果为： 4 2 1 3

后续遍历

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

输出结果为： 4 2 3 1

1.2 Tree.c 结点个数

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

1.3Tree.c 叶子节点个数

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

• 当一棵二叉树中的节点的左右孩都为空时，证明他就是最后的结点，也叫做 “叶子节点” ，上述代码就运用了这一特点进行函数递归 ，if (root->left == NULL && root->right == NULL) 成立则返回 1 ，不成立就继续对其左右孩创建函数栈帧进行递归。

1.4 Tree.c 二叉树的高度

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

• 此处的递归方式与查找节点个数的递归方式相同，但是这里是求树的高度，所以当我们返回根节点的左右孩子的节点个数时（也就是求出左孩和右孩分别的高度），要进行比较，选出较高的树的高度，此高度就是整棵树的高度。

1.5 Tree.c 层序遍历

在上述构建好的二叉树中，如果要对其进行层序遍历的话，期待输出的结果为 1 2 3 4 ，

此时我们可以借助队列这一数据结构实现，所以在编写代码时先要包括 “Queue.h” 的头文件，具体队列的实现可以参考 数据结构（队列）-CSDN博客。

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);
    }
    //队列为空
    QueueDestroy(&q);
}

1.6 判断是否为完全二叉树

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))
    {
        if (front != NULL)
        {
            QueueDestory(&q);
                return false;
        }
    }
    QueueDestory(&q);
    return true;
}

• 如果是完全二叉树，跳出一个循环之后队列中剩下的全是NULL节点；
• 如果不是完全二叉树，跳出一个循环之后队列还有非空节点。

1.7 销毁二叉树

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

• 销毁左子树 + 销毁右子树 + 销毁根节点

test.c

#include"Tree.h"
BTNode* buyNode(BTDataType x)
{
    //创建结点
    BTNode* newnode = (BTNode*)malloc(sizeof(BTDataType));
    if (newnode == NULL)
    {
        perror("malloc fail!");
        exit(1);
    }
    newnode->data = x;
    newnode->left = newnode->right = NULL;
    return newnode;
}
void treetest()
{
    BTNode* node1 = buyNode(1);
    BTNode* node2 = buyNode(2);
    BTNode* node3 = buyNode(3);
    BTNode* node4 = buyNode(4);
    node1->left = node2;
    node1->right = node3;
    node2->light = node4;
}
int main()
{
    treetest();
    return 0;
}

未完待续~~