初阶数据结构之二叉树

那么本篇文是初阶数据结构这个系列的最后一篇文章，那么闲话少叙，我们直接进入正题

在讲二叉树的一些之前知识点之前，我先给大家送个小礼物哈

手搓二叉树

typedef int BTDataType ;

typedef struct BinaryTreeNode

{

BTDataType _data ;

struct BinaryTreeNode * _left ;

struct BinaryTreeNode * _right ;

} BTNode ;

BTNode * CreatBinaryTree ()

{

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 ;

}

手搓二叉树的思路

首先创建一个结构体，且结构体里的元素也是需要自己设置，就拿链表来举例，结构体内必须包含数据以及指向下一个节点的指针next,那么返回到二叉树这里，结构体需要包含的就是数据，以及左右指针，然后创建子节点以及子节点之间相互连接

前序遍历

那么我们可以先从这个图中得到一个结论

前序遍历：根  左子树   右子树

这里我也是给大家准备了一个小视频，大家可以参考一下

二叉树前序遍历思路讲解

源代码

void FrontOrder(TFT* node)
{
    if (node == NULL)
    {
        printf("N ");
        return;
    }
    printf("%d ", node->data);
    FrontOrder(node->left);
    FrontOrder(node->right);
}

中序遍历

我们先来说一下结论

中序遍历：左子树    根     右子树

这里的操作我也给大家准备了 一个小视频，大家可以参考一下

二叉树中序遍历思路讲解

源代码

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

后序遍历

还是一样，我们先讲结论

后序遍历：左子树   右子树   根

这里的操作我也给大家准备了 一个小视频，大家可以参考一下

二叉树的后序遍历

源代码

void BehindOrder(TFT* node)
{
    if (node == NULL)
    {
        printf("N ");
        return;
    }
    BehindOrder(node->left);
    BehindOrder(node->right);
    printf("%d ", node->data);
}

前中后序的共同特点

通过递归的方法，进行遍历

节点计数

思路：当节点不为空时，计数器+1，节点为空时，计数器+0，然后用递归进行遍历

源代码

int TreeSize(TFT* root)
{
    /*int size = 0;*/
    if (root == NULL)
        return 0;
    else
        ++size;

    TreeSize(root->left);
    TreeSize(root->right);
    return size;
}

计算树的高度

思路：进入函数后先判空，如果为空，则返回0，不为空时，先记录当前左右两科树的高点，然后进行左右判断，谁大谁加1

源代码

int TreeHighSize(TFT* node)
{
    if (node == NULL)
        return 0;
    int left = TreeHighSize(node->left);
    int right = TreeHighSize(node->right);
    return left > right ? left + 1 : right + 1;
}

树的销毁

树的销毁其实不难，基本上就是还原变量指针等等

源代码

void DestroyTree(TFT* node)
{
    if (node == NULL)
        return;
    DestroyTree(node->left);
    DestroyTree(node->right);
    free(node);
}

那么初阶数据结构系列的文章就先给大家更新到这里，如果喜欢我的文章，还请各位观众老爷们留个赞谢谢，我们下期再见