链式结构二叉树的实现与操作详解

链式结构二叉树的实现与操作详解

引用

CSDN

1.

https://blog.csdn.net/braveact/article/details/143481942

本文详细介绍了链式结构二叉树的实现，包括二叉树的概念、结构以及相关操作的实现。通过代码示例和图解的方式，帮助读者理解二叉树的递归实现。

1. 链式结构二叉树的实现

1.1 二叉树的概念与结构

1.1.1 链式二叉树概念

用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。

1.1.2 链式二叉树结构

typedef int BTDataType;
typedef struct BinaryTreeNode  
{  
    BTDataType data;  
    struct BinaryTreeNode* left;  
    struct BinaryTreeNode* right;  
}BTNode;

1.2 创建二叉树

二叉树的创建方式比较复杂，为了更好地步入到二叉树内容中，我们先手动创建一棵链式二叉树

BTNode* BuyBTNode(int val)
{
    BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
    if (newnode == NULL)
    {
        perror("malloc fail");
        return NULL;
    }
    newnode->val = val;
    newnode->left = NULL;
    newnode->right = NULL;
    return newnode;
}
BTNode* CreateTree()
{
    BTNode* n1 = BuyBTNode(1);
    BTNode* n2 = BuyBTNode(2);
    BTNode* n3 = BuyBTNode(3);
    BTNode* n4 = BuyBTNode(4);
    BTNode* n5 = BuyBTNode(5);
    BTNode* n6 = BuyBTNode(6);
    BTNode* n7 = BuyBTNode(7);
    n1->left = n2;
    n1->right = n4;
    n2->left = n3;
    n4->left = n5;
    n4->right = n6;
    n5->left = n7;
    return n1;
}  

2. 二叉树的基本操作

2.1 二叉树的遍历

2.1.1 遍历规则

按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：

1. 前序遍历(Preorder Traversal 亦称先序遍历)：访问根结点的操作发生在遍历其左右子树之前
   访问顺序为：根结点、左子树、右子树

2. 中序遍历(Inorder Traversal)：访问根结点的操作发生在遍历其左右子树之中（间）
   访问顺序为：左子树、根结点、右子树

3. 后序遍历(Postorder Traversal)：访问根结点的操作发生在遍历其左右子树之后
   访问顺序为：左子树、右子树、根结点

偷偷告诉大家我是如何记这个规则，自我感觉很有用，子树都是从左往右遍历，看什么遍历，例如前序遍历，就说明根在前。

2.1.1.1 前序遍历

核心思想：递归(先递推，再递归)

首先递归一定要有结束条件，没有则会无限递归，死循环。

当递归到叶子节点，左右节点都为NULL，结束递推，逐次递归回上一次创建函数栈帧。

即root==NULL

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

图示：

2.1.1.2 中序遍历

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

2.1.1.3 后序遍历

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

2.2 二叉树节点个数

本节点+左节点+右节点

当节点为空，返回0

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

图解：

2.3 二叉树叶子节点个数

叶子结点：度为0,即没有孩子节点

// 二叉树叶子结点个数
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);
}

图解：

2.4 二叉树第k层节点个数

求第k层左子树节点个数+第k层右子树节点个数

// 二叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
    if (root == NULL)
    {
        return 0;
    }
    if (k == 1)
    {
        return 1;
    }
    return BinaryTreeLevelKSize(root->left, k - 1)
        + BinaryTreeLevelKSize(root->right, k - 1);
}

图解：

2.5 二叉树的深度/高度

• 要求高度，即子树高度的最大值+1，子树高度的最大值又是其子树高度最大值+1，以此类推
• 当递推到空节点时结束——>返回0（空节点不算高度）
• 回归时每次返回左右子树高度取最大值+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;
}

2.6 二叉树的查找

// 二叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType 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;
}

2.7 二叉树的销毁

// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{
    if (*root == NULL)
    {
        return;
    }
    BinaryTreeDestory(&((*root)->left));
    BinaryTreeDestory(&((*root)->right));
    free(*root);
    *root = NULL;
}

相信通过这篇文章你对二叉树递归暴力的有了初步的了解。如果此篇文章对你学习数据结构（二叉树）有帮助，期待你的三连，你的支持就是我创作的动力！！！