首页 > 其他分享 >浅谈【数据结构】树与二叉树二

浅谈【数据结构】树与二叉树二

时间：2024-08-25 17:51:40浏览次数：16  
标签：node lchild 结点 浅谈 tree 二叉树 数据结构 data ptr

目录

1、二叉排序树

1.1二叉树排序树插入

1.1.1两种插入方法

1.1.2循环法

1.1.3递归法

1.2二叉树的打印

1.3二叉树的结点删除

1.4销毁二叉树

1.5层次打印

谢谢帅气美丽且优秀的你看完我的文章还要点赞、收藏加关注

没错，说的就是你，不用再怀疑！！！

希望我的文章内容能对你有帮助，一起努力吧！！！

1、二叉排序树

二叉树排序树：以某个结点为准，该结点的左子树内所有的结点都会比该结点要小。该结点的右子树内 的所有结点都会大于该结点。

1.1二叉树排序树插入

  • 插入结点
    • 树为空的时候
      • 把结点作为根结点插入
    • 树不为空时候
      • 和根结点比较
        • 如果比根结点小，则判断根结点左子结点是否存在
          • 如果左子结点存在的话，将根结点的左子结点作为根结点继续比较
          • 如果不存在，直接将新数据作为该根结点的左子结点插入
        • 如果比根结点大，则判断根结点右子结点是否存在
          • 如果右子结点存在的话，将根结点的右子结点作为根结点继续比较
          • 如果不存在，直接将新数据作为该根结点的右子结点插入
      • 插入新节点无法就是重复上述步骤

1.1.1两种插入方法

1.1.2循环法

  • 逻辑
    • 如果根结点为空，那么新结点直接作为根结点返回
    • 如果不为空
      • 通过前后指针，循环移动来找到待插入的位置
      • 循环结束之后，待插入的位置
        • 父结点指针的下一级
          • 需要通过再对父结点数据比较一次，来确定插入方向（左右）

1.1.3递归法

1.2二叉树的打印

  • 先序访问
    • 先访问根结点，再访问左子树，最后访问右子树（根左右）
  • 中序访问
    • 先访问左子树，再访问根结点，最后访问右子树（左根右）
  • 后序访问
    • 先访问左子树，再访问右子树，最后访问根结点（左右根）

示例代码：

#include <iostream>


// 树结点类型
typedef struct treenode
{
    int value;
    struct treenode *lchild;
    struct treenode *rchild;
}Tree;

/*
    @brief 增加新的结点进入二叉树中（循环法）
    @param tree 需要增加结点的树的根结点指针
    @param data 需要增加进树的新结点数据
    @return 返回树的根结点
*/
Tree *addNewNodeLoop(Tree *tree,int data)
{
    // 如果树为空作为根结点插入
    if(tree == nullptr)
    {
        Tree *node_ptr = new Tree;
        node_ptr->value = data;
        node_ptr->lchild = nullptr;
        node_ptr->rchild = nullptr;
        return node_ptr;   
    }

    // 如果树不为空的时候，需要和根结点进行比较
    Tree *father = nullptr; // 父结点
    Tree *current_node = tree; // 当前结点

    while(current_node)
    {
        father = current_node; // 将当前结点作为下一个结点的父结点
        // 当前结点的数据大于data，需要往左查
        if(current_node->value > data)
            current_node = current_node->lchild; // 将当前结点的左子结点作为新的根结点来继续下次比较
        // 当前结点的数据小于data，需要往右查
        else if(current_node->value < data)
            current_node = current_node->rchild; // 将当前结点的右子结点作为新的根结点来继续下次比较
        else
            return tree; // 不能存在相等情况，所以直接返回
    }

    // 出来循环：找到了插入的位置
    current_node = new Tree;
    current_node->value = data;
    current_node->lchild = nullptr;
    current_node->rchild = nullptr;

    // 确定是左插还是右插
    if(father->value > data)
        // 左插
        father->lchild = current_node;
    else
        // 右插
        father->rchild = current_node;

    return tree;
}

/*
    @brief 增加新的结点进入二叉树中（递归法）
    @param tree 需要增加结点的树的根结点指针
    @param data 需要增加进树的新结点数据
    @return 返回树的根结点
*/
Tree *addNewNode(Tree *tree,int data)
{
    // 如果树为空作为根结点插入
    if(tree == nullptr)
    {
        Tree *node_ptr = new Tree;
        node_ptr->value = data;
        node_ptr->lchild = nullptr;
        node_ptr->rchild = nullptr;
        return node_ptr;   
    }

    // 如果树不为空的时候，需要和根结点进行比较
    if(tree->value > data)
        // 左插
        tree->lchild = addNewNode(tree->lchild,data);
    else if(tree->value < data)
        // 右插
        tree->rchild = addNewNode(tree->rchild,data);
    return tree;
}

/*
    @brief 创建一棵二叉排序树
    @return 成功返回创建好的树的首地址
*/
Tree *createNewTree()
{
    // 一棵空树
    Tree *tree = nullptr;

    while(1)
    {
        int data = -1;
        std::cin >> data;
        if(data == -1)
            break;

        // 插入到树中
        tree = addNewNode(tree,data);
    }

    // 返回创建好的树
    return  tree;
}

/*
    @brief 先序遍历二叉树的结点 根左右
    @param tree 需要先序遍历的二叉树根结点指针
*/
void frontPrintTree(Tree *tree)
{
    // 判断一下根结点是否为空
    if(tree == nullptr)
        return;
    
    // 把传入的结点直接作为根结点使用

    // 打印根结点
    std::cout << tree->value;

    // 打印左子树：这里的tree->lchild其实就是左子树的根
    frontPrintTree(tree->lchild);

    // 打印右子树：这里的tree->rchild其实就是右子树的根
    frontPrintTree(tree->rchild);
}

/*
    @brief 中序遍历二叉树的结点 左根右
    @param tree 需要先序遍历的二叉树根结点指针
*/
void middlePrintTree(Tree *tree)
{
    // 判断一下根结点是否为空
    if(tree == nullptr)
        return;
    
    // 把传入的结点直接作为根结点使用

    // 打印左子树：这里的tree->lchild其实就是左子树的根
    middlePrintTree(tree->lchild);

    // 打印根结点
    std::cout << tree->value;

    // 打印右子树：这里的tree->rchild其实就是右子树的根
    middlePrintTree(tree->rchild);
}

/*
    @brief 后序遍历二叉树的结点 左右根
    @param tree 需要先序遍历的二叉树根结点指针
*/
void backPrintTree(Tree *tree)
{
    // 判断一下根结点是否为空
    if(tree == nullptr)
        return;
    
    // 把传入的结点直接作为根结点使用

    // 打印左子树：这里的tree->lchild其实就是左子树的根
    backPrintTree(tree->lchild);

    // 打印右子树：这里的tree->rchild其实就是右子树的根
    backPrintTree(tree->rchild);

    // 打印根结点
    std::cout << tree->value;
}

int main()
{
    // 创建一棵树
    Tree * tree = createNewTree();

    //  先序后序中序的打印
    frontPrintTree(tree);
    std::cout << std::endl;

    middlePrintTree(tree);
    std::cout << std::endl;

    backPrintTree(tree);
    std::cout << std::endl;
    return 0;
}

1.3二叉树的结点删除

  • 删除一个结点
    • 第一种情况：被删除的结点是叶子结点，直接删除
      • 释放叶子结点空间
      • 返回空指针
    • 第二种情况：被删除结点只有左子树，将左子树中最大的结点替换为需要删除的结点
      • 如果左子树中的第一个结点为最大结点（表示该左子树是没有右子树的）
        • 将被删除结点的 lchild 指向最大的那个结点的 lchild
        • 释放左子树中的第一个结点的空间
        • 返回被删除节点
      • 如果左子树中第一个节点不为最大结点（表示该左子树是有右子树）
        • 将最大结点的父结点的 rchild 指向最大结点的 lchild
        • 释放左子树中最大结点的空间
        • 返回被删除结点
    • 第三种情况：被删除的结点只有右子树，将右子树中的最小结点替换为需要删除的结点
      • 如果右子树的第一个结点不为最小结点
        • 将最小结点的父结点的 lchild 指向最小结点的 rchild
        • 释放最小结点
        • 返回被删除结点
      • 如果右子树的第一个结点为最小结点
        • 将被删除结点的 rchild 指向最小结点的 rchild
        • 释放最小结点
        • 返回被删除结点
    • 第四种情况：被删除结点即存在左子树也存在右子树
      • 可以在右子树中找最小的结点替换，操作和第三种情况方式一样
      • 可以在左子树中找最大的结点替换，操作和第二种情况方式一样

1.4销毁二叉树

1.5层次打印

  • 1、先入队根结点
  • 2、出队结点
    • 判断当前出队的结点左子树是否存在
      • 如果存在将左子树入队
    • 判断当前出队的结点右子树是否存在
      • 如果存在右子树入队
  • 3、打印结点数据
  • 重复以上步骤直到队列为空

***二叉树排序树示例代码***

#include <iostream>

#include <queue>

using std::queue;

template <typename T>
class sort_tree
{
private:
    typedef struct tree_node
    {
        T data;
        struct tree_node *lchild;
        struct tree_node *rchild;
    }TreeNode;
    
    TreeNode *root;

public:
    // 默认构造
    sort_tree()
    : root(nullptr)
    {}

    // 拷贝构造
    sort_tree(const sort_tree &object)
    {
        
    }

    // 带参构造
    sort_tree(std::initializer_list<T> list) 
        : root(nullptr) // root 如果不置空，那么就是一个野指针
    {
        // 遍历list列表
        for(auto var : list)
            add(var); // 通过add来增加结点进树
    }
    
    // 先序打印
    void frontPrint(TreeNode *tn = nullptr)
    {
        TreeNode *tree_node =nullptr;
        if(tn == nullptr)
            tree_node = root;
        else 
            tree_node = tn;



        if(tree_node == nullptr)
            return;
        std::cout << tree_node->data << " ";
        if(tree_node->lchild)
            frontPrint(tree_node->lchild);
        if(tree_node->rchild)
            frontPrint(tree_node->rchild);
    }

    // 层次打印
    void levelPrint()
    {
        if(root == nullptr)
            return;

        queue<TreeNode *> q;

        // 先入根结点
        q.push(root);

        while(!q.empty())
        {
            // 获取队头元素
            TreeNode *node_ptr = q.front();

            // 出队元素
            q.pop();

            // 打印元素
            std::cout << node_ptr->data << " ";

            // 判断左右子树是否存在
            if(node_ptr->lchild)
                q.push(node_ptr->lchild);
            
            if(node_ptr->rchild)
                q.push(node_ptr->rchild);
        }
        std::cout << std::endl;
    }

    // 销毁删除
    TreeNode *destory(TreeNode *tn = nullptr)
    {
        TreeNode *tree_node = nullptr;
        if(tn == nullptr)
            tree_node = root;
        else
            tree_node = tn;

        if(tree_node->lchild)
            // 通过回溯去更新子树指针指向
            tree_node->lchild = destory(tree_node->lchild);

        if(tree_node->rchild)
            // 通过回溯去更新子树指针指向
            tree_node->rchild = destory(tree_node->rchild);

        // 根就是需要删除
        std::cout << "我被删除了" << tree_node->data << std::endl;
        delete tree_node;
        return nullptr;
    }

    // 析构/销毁
    ~sort_tree()
    {
        // 从叶子结点开始删除
        // 左右根进行遍历销毁
        destory();
    }

    // 增加结点
    bool add(T &data)
    {
        // 判断是不是空树
        if(root == nullptr)
        {
            root = new TreeNode;
            root->data = data;
            root->lchild = nullptr;
            root->rchild = nullptr;
            return true;
        }

        // 如果不为空，查找挂载的位置
        TreeNode *father_node = root;
        do
        {
            if(father_node->data > data)
            {
                // 判断左子结点存不存在
                // 如果存在将左子结点设为新的父结点
                if(father_node->lchild)
                    father_node = father_node->lchild;
                else // 如果不存在就挂载到father结点的左边
                {
                    father_node->lchild = new TreeNode;
                    father_node->lchild->data = data;
                    father_node->lchild->lchild = nullptr;
                    father_node->lchild->rchild = nullptr;
                    return true;
                }
            }
            else if(father_node->data < data)
            {
                // 判断右子结点存不存在
                // 如果存在将右子结点设为新的父结点
                if(father_node->rchild)
                    father_node = father_node->rchild;
                else // 如果不存在就挂载到father结点的右边
                {
                    father_node->rchild = new TreeNode;
                    father_node->rchild->data = data;
                    father_node->rchild->lchild = nullptr;
                    father_node->rchild->rchild = nullptr;
                    return true;
                }
            }
            else
                return false;
        } while (1);
    }

    // 删除结点
    bool del(T &data)
    {
        // 是不是空树
        if(root == nullptr)
            return false;
        
        // 不是空树
        
        // 找需要删除的结点
        TreeNode *father_ptr  = nullptr;
        TreeNode *delNode_ptr = root;
        do
        {
            // 如果小于当前结点，那么说明被删除的结点在树的左边
            if(delNode_ptr->data > data)
            { 
                // 更新父结点指针
                father_ptr = delNode_ptr;
                delNode_ptr = delNode_ptr->lchild;
            }
             // 如果大于当前结点，那么说明被删除的结点在树的右边
            else if(delNode_ptr->data < data)
            {
                // 更新父结点指针
                father_ptr = delNode_ptr;
                delNode_ptr = delNode_ptr->rchild;
            }
            else 
                break; // 找到了需要删除的结点
            
            // 为空表示树中没有找到删除的结点
            if(delNode_ptr == nullptr)
                return false;

        } while (1);
        
        // 能来到这位置。说明找到了需要删除的结点

        // 第一种情况：叶子结点
        if(!delNode_ptr->lchild&&!delNode_ptr->rchild)
        {
            // 改变父结点中子树指针的指向。避免父结点中的子树指针成为野指针
            if(father_ptr->data > data)
                father_ptr->lchild = nullptr;
            else if(father_ptr->data < data)
                father_ptr->rchild = nullptr;

            // 删除结点，释放空间
            delete delNode_ptr;
            delNode_ptr = nullptr;
            return true;
        }

        // 存在左子树：包含了第四种情况
        else if(delNode_ptr->lchild)
        {
            // 找左子树中最大的结点
            TreeNode *maxFather_ptr = nullptr;
            TreeNode *maxNode_ptr = delNode_ptr->lchild;

            // 一路向右
            while(maxNode_ptr->rchild)
            {
                maxFather_ptr = maxNode_ptr;
                maxNode_ptr = maxNode_ptr->rchild;
            }
            // 第一种情况：被删除结点的lchild指向左子树种最大结点的lchild
            if(maxNode_ptr == delNode_ptr->lchild)
                delNode_ptr->lchild = maxNode_ptr->lchild;
            else
                maxFather_ptr->rchild = maxNode_ptr->lchild;

            // 值交换
            std::swap(delNode_ptr->data,maxNode_ptr->data);

            // 删除左子树种最大结点
            maxNode_ptr->lchild = nullptr;
            delete maxNode_ptr;
            maxNode_ptr = nullptr;
            return true;
        }
        
        // 只有右子树不为空
        else
        {
            // 找右子树中最小的结点
            TreeNode *minFather_ptr = nullptr;
            TreeNode *minNode_ptr = delNode_ptr->rchild;

            // 一路向左
            while(minNode_ptr->lchild)
            {
                minFather_ptr = minNode_ptr;
                minNode_ptr = minNode_ptr->lchild;
            }
            // 第一种情况：被删除结点的rchild指向右子树种最小结点的rchild
            if(minNode_ptr == delNode_ptr->rchild)
                delNode_ptr->rchild = minNode_ptr->rchild;
            else
                minFather_ptr->lchild = minNode_ptr->rchild;

            // 值交换
            std::swap(delNode_ptr->data,minNode_ptr->data);

            // 删除右子树种最小结点
            minNode_ptr->rchild = nullptr;
            delete minNode_ptr;
            minNode_ptr = nullptr;
            return true;
        }
    }
};



int main()
{
    sort_tree<int> tree({3,1,5,6,4,2,8,9,7});

    // do
    // {
    //     int data = -1;
    //     std::cin >> data;
    //     if(data == -1)
    //         break;

    //     tree.add(data);
    // } while (1);
    
    tree.levelPrint();
    return 0;
}

标签：node,lchild,结点,浅谈,tree,二叉树,数据结构,data,ptr
From： https://blog.csdn.net/weixin_67526434/article/details/141531601

相关文章

  • 数据结构：189（轮转数组）leetcode(OJ)
    给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。示例1:输入:nums=[1,2,3,4,5,6,7],k=3输出:[5,6,7,1,2,3,4]解释:向右轮转1步:[7,1,2,3,4,5,6]向右轮转2步:[6,7,1,2,3,4,5]向右轮转3步:[5,6,7,1,2,3,4]示例 2:输入：n......
  • Java行为型设计模式-访问者模式（含二叉树场景示例）
    1.访问者模式简介访问者模式（VisitorPattern）是一种行为型设计模式，其主要目的是将数据结构与数据操作解耦。用于将数据结构和在数据结构上的操作分离开来。‌这种模式允许在不修改数据结构的情况下，定义新的操作。2.访问者模式角色访问者模式的主要角色包括：2.1抽象访问......
  • 浅谈二分图
    定义二分图，又称二部图，英文名叫Bipartitegraph。二分图是什么？节点由两个集合组成，且两个集合内部没有边的图。换言之，存在一种方案，将节点划分成满足以上性质的两个集合。性质如果两个集合中的点分别染成黑色和白色，可以发现二分图中的每一条边都一定是连接一个黑色点和一个白......
  • 秋招力扣Hot100刷题总结——二叉树
    二叉树相关的题目基本上都会使用递归，因此做二叉树的题目时首先使用递归，明确递归结束的条件。1.二叉树的层序遍历题目链接题目要求：给你二叉树的根节点root，返回其节点值的层序遍历。（即逐层地，从左到右访问所有节点）。代码及思路使用队列存储每一层的节点，左边节点先......
  • 集合及数据结构第九节————树和二叉树
    系列文章目录集合及数据结构第九节————树和二叉树树和二叉树树型结构的概念树的概念树的表示形式（了解）树的应用二叉树的概念两种特殊的二叉树二叉树的性质二叉树的性质练习二叉树的存储二叉树的遍历二叉树的基本操作二叉树相关练习题文章目录系列文章目录集合及......
  • 浅谈一类第 k 大问题
    浅谈一类第k大问题IntroductiontoK-thLargestProblems本文介绍一类第k大问题的处理方法。LuoguP1631序列合并LuoguP2048[NOI2010]超级钢琴LuoguP5283[十二省联考2019]异或粽子CodeForces241BFriends基本思想：先找到部分答案，通过这部分答案更新可能的......
  • 软考-软件设计师（数据结构习题一）
       ......
  • 数据结构和算法学习日志-第十章：树
    第十章树思维导图：1.树的定义和树的存储结构1.1树的定义1.1.1定义树（Tree）是n（n>=0）个节点的有限集。当n=0时称为空树。在任意一棵非空树中：有且仅有一个特定的被称为根（Root）的节点当n>1时，其余节点可分为m（m>0）个互不相交的有限集T1、T2、……、Tm，其中每个集合本身又是一棵树，并......
  • 二叉树刷题（1）
    二叉树题目讲解（1）一、构建二叉树并且遍历（1）思路（2）代码二、对称二叉树1、思路2、代码三、相同的树1、思路2、代码四、单值二叉树1、思路2、代码五、另一棵树的子树1、思路2、代码一、构建二叉树并且遍历题目描述：编一个程序，读入用户输入的一串先序遍历字符串，根据此字......
  • 数据结构（Java）：揭开二叉搜索树删除机制的奥秘
    目录1、二叉搜索树1.1概念2、代码模拟实现2.1插入操作2.2查找操作2.3......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99