精华内容
下载资源
问答
  • 多叉树
    2021-04-12 20:20:09

    目录

    一,N叉树、多叉树

    二,多叉树遍历

    1,DFS遍历

    力扣 589. N 叉树的前序遍历

    力扣 590. N 叉树的后序遍历

    力扣 690. 员工的重要性

    2,BFS遍历

    力扣 429. N叉树的层序遍历

    三,多叉树求深度

    力扣 559. N 叉树的最大深度


    一,N叉树、多叉树

    N叉树一般指的是孩子节点可以超过2但是上限为N的树,

    多叉树指的是孩子数量没有上限的树。

    多叉树的结构体:

    class Node {
    public:
        int val;
        vector<Node*> children;
    
        Node() {}
    
        Node(int _val) {
            val = _val;
        }
    
        Node(int _val, vector<Node*> _children) {
            val = _val;
            children = _children;
        }
    };

    二,多叉树遍历

    二叉树 二叉树_csuzhucong的博客-CSDN博客_二叉树csdn

    1,DFS遍历

    多叉树的DFS遍历就只有前序和后序,没有中序了。

    力扣 589. N 叉树的前序遍历

    给定一个 N 叉树,返回其节点值的 前序遍历 。

    N 叉树 在输入中按层序遍历进行序列化表示,每组子节点由空值 null 分隔(请参见示例)。

    进阶:

    递归法很简单,你可以使用迭代法完成此题吗?

    示例 1:

    输入:root = [1,null,3,2,4,null,5,6]
    输出:[1,3,5,6,2,4]
    示例 2:


    输入:root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
    输出:[1,2,3,6,7,11,14,4,8,12,5,9,13,10]
     

    提示:

    N 叉树的高度小于或等于 1000
    节点总数在范围 [0, 10^4] 内

    class Solution {
    public:
        vector<int> preorder(Node* root) {
            vector<int>v1,v2;
            if (root == NULL)return v1;
            v1.insert(v1.end(), root->val);
            for(int i=0;i<root->children.size();i++) {
                v2 = preorder(root->children[i]);
                v1.insert(v1.end(), v2.begin(), v2.end());
            }
            return v1;
        }
    };

    力扣 590. N 叉树的后序遍历

    给定一个 N 叉树,返回其节点值的 后序遍历 。

    N 叉树 在输入中按层序遍历进行序列化表示,每组子节点由空值 null 分隔(请参见示例)。

    进阶:

    递归法很简单,你可以使用迭代法完成此题吗?

    示例 1:

    输入:root = [1,null,3,2,4,null,5,6]
    输出:[5,6,3,2,4,1]
    示例 2:

    输入:root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
    输出:[2,6,14,11,7,3,12,8,4,13,9,10,5,1]
     

    提示:

    N 叉树的高度小于或等于 1000
    节点总数在范围 [0, 10^4] 内

    class Solution {
    public:
        vector<int> postorder(Node* root) {
            vector<int>v1,v2;
            if (root == NULL)return v1;
            for(int i=0;i<root->children.size();i++) {
                v2 = postorder(root->children[i]);
                v1.insert(v1.end(), v2.begin(), v2.end());
            }
            v1.insert(v1.end(), root->val);
            return v1;
        }
    };

    力扣 690. 员工的重要性

    给定一个保存员工信息的数据结构,它包含了员工 唯一的 id ,重要度 和 直系下属的 id 。

    比如,员工 1 是员工 2 的领导,员工 2 是员工 3 的领导。他们相应的重要度为 15 , 10 , 5 。那么员工 1 的数据结构是 [1, 15, [2]] ,员工 2的 数据结构是 [2, 10, [3]] ,员工 3 的数据结构是 [3, 5, []] 。注意虽然员工 3 也是员工 1 的一个下属,但是由于 并不是直系 下属,因此没有体现在员工 1 的数据结构中。

    现在输入一个公司的所有员工信息,以及单个员工 id ,返回这个员工和他所有下属的重要度之和。

    示例:

    输入:[[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1
    输出:11
    解释:
    员工 1 自身的重要度是 5 ,他有两个直系下属 2 和 3 ,而且 2 和 3 的重要度均为 3 。因此员工 1 的总重要度是 5 + 3 + 3 = 11 。
     

    提示:

    一个员工最多有一个 直系 领导,但是可以有多个 直系 下属
    员工数量不超过 2000 。

    /*
    // Definition for Employee.
    class Employee {
    public:
        int id;
        int importance;
        vector<int> subordinates;
    };
    */
    class Solution {
    public:
    	int getImportance(map<int, Employee*> &m, int id)
    	{
    		int s = m[id]->importance;
    		for (auto id : m[id]->subordinates)s += getImportance(m, id);
    		return s;
    	}
    	int getImportance(vector<Employee*> employees, int id) {
    		map<int, Employee*>m;
    		for (auto vi : employees)m[vi->id] = vi;
    		return getImportance(m, id);
    	}
    };

    2,BFS遍历

    力扣 429. N叉树的层序遍历

    题目:

    给定一个 N 叉树,返回其节点值的层序遍历。 (即从左到右,逐层遍历)。

    例如,给定一个 3叉树 :

    返回其层序遍历:

    [
         [1],
         [3,2,4],
         [5,6]
    ]
     

    说明:

    树的深度不会超过 1000。
    树的节点总数不会超过 5000。

    代码:

    class Solution {
    public:
    	vector<vector<int>> levelOrder(Node* root) {
    		vector<int>tmp1;
    		vector<Node*>tmp2, tmp3;
    		vector<vector<int>>ans;
    		if (!root)return ans;
    		tmp2.insert(tmp2.end(), root);
    		while (!tmp2.empty())
    		{
    			tmp1.clear();
    			int k = tmp2.size();
    			while (k--)
    			{
    				tmp1.insert(tmp1.end(), tmp2[0]->val);
    				tmp3 = tmp2[0]->children;
    				for (int j = 0; j < tmp3.size(); j++)tmp2.insert(tmp2.end(), tmp3[j]);
    				tmp2.erase(tmp2.begin());
    			}
    			ans.insert(ans.end(),tmp1);
    		}
    		return ans;
    	}
    };

    三,多叉树求深度

    力扣 559. N 叉树的最大深度

    给定一个 N 叉树,找到其最大深度。

    最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

    N 叉树输入按层序遍历序列化表示,每组子节点由空值分隔(请参见示例)。

    示例 1:

    输入:root = [1,null,3,2,4,null,5,6]
    输出:3
    示例 2:

    输入:root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
    输出:5
     

    提示:

    树的深度不会超过 1000 。
    树的节点数目位于 [0, 104] 之间。

    class Solution {
    public:
        int maxDepth(Node* root) {
            if(!root)return 0;
            int ans=1;
            for(int i=0;i<root->children.size();i++)ans=max(ans,maxDepth(root->children[i])+1);
            return ans;
        }
    };

    更多相关内容
  • Java实现多叉树查找

    2020-12-22 20:07:26
    1 package tree;  2  3 import java.util.List;  4 import java.util.ArrayList;  5 import java.io.Serializable;  6  7 public class TreeNode implements Serializable {  8 private int parentId...
  • 本主要是树状数据(多叉树)在数据库中存储的示例源码,同时包含数据表的设计示例,满满的代码干货
  • 主要介绍了JavaScript实现多叉树的递归遍历和非递归遍历算法,结合实例形式详细分析了JavaScript多叉树针对json节点的递归与非递归遍历相关操作技巧,需要的朋友可以参考下
  • 本文实例讲述了javascript数据结构之多叉树经典操作。分享给大家供大家参考,具体如下: 多叉树可以实现复杂的数据结构的存储,通过遍历方法可以方便高效的查找数据,提高查找的效率,同时方便管理节点数据。...
  • java多叉树的实现:节点集合生成多叉树,单个节点添加到多叉树,深度遍历,广度遍历
  • 多叉树的树形显示

    2018-04-09 18:00:57
    说明地址 http://www.cnblogs.com/l2017/p/8660089.html
  • 本文实例讲述了Python实现的多叉树寻找最短路径算法。分享给大家供大家参考,具体如下: 多叉树的最短路径: 思想:  传入start 和 end 两个 目标值  1 找到从根节点到目标节点的路径  2 从所在路径,寻找最近的...
  • c++ 多叉树

    2021-01-27 03:30:14
    c++实现的多叉树,文件里面有文档,操作说明。代码有注释,基本按照编码规范来的。 c++实现的多叉树,文件里面有文档,操作说明。代码有注释,基本按照编码规范来的。
  • 今天小编就为大家分享一篇Python多叉树的构造及取出节点数据(treelib)的方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
  • TreeNde 多叉树

    2014-07-27 16:58:26
    动态生成多叉树,实现多叉树的自动化遍历,能生成XML文本。 指定子节点和父节点自动生成多叉树
  • 本程序主要介绍使用c语言的树数据结构,比较全面的介绍和使用多叉树
  • 决策树 id3算法实现多叉树树形图显示,使用matlab编程实现多叉树生成结构体,再对结构体进行处理,生成树形图。
  • 多叉树的建立以及后序非递归遍历,希望对学习数据结构的同学有所帮助,也对树一部分有更深的了解。
  • 基于多叉树确定K值的动态K-means聚类算法.pdf
  • 多叉树转二叉树图示: 将同一个父节点的所有子节点用虚线相连起来 将上面的红线断开 然后将虚线顺时针旋转45°,虚线变实线 这样即可完成多叉树转二叉树 简单来说,就是以a为头结点的多叉树,其第一...

    多叉树转二叉树图示:

    将同一个父节点的所有子节点用虚线相连起来

    将上面的红线断开

     然后将虚线顺时针旋转45°,虚线变实线

     这样即可完成多叉树转二叉树

    简单来说,就是以a为头结点的多叉树,其第一个孩子节点挂在其左侧,然后第二个孩子节点c,挂在第一个孩子节点b的右侧,第三个孩子节点d挂在第二个孩子节点c的右侧。以b为头结点的多叉树,以c为头结点的多叉树也是同理。即将a的所有孩子节点连成一条链表,该链表是从水平变成顺时针旋转旋转45°。b.right=c   c.right=d即可实现将链表链表是从水平变成顺时针旋转旋转45°。

    那么用深度优先遍历算法如何将多叉树转成二叉树呢?

    如下是深度优先遍历算法将多叉树转成二叉树的代码实现

        /**
         * 多叉树节点类
         */
        public static class Node {
    
            public int val;
    
            public List<Node> children;
    
            public Node() {
            }
    
            public Node(int val, List<Node> children) {
                this.val = val;
                this.children = children;
            }
        }
    
        /**
         * 二叉树节点类
         */
        public static class TreeNode {
    
            public int value;
    
            public TreeNode left;
    
            public TreeNode right;
    
            public TreeNode(int value) {
                this.value = value;
            }
        }
    
    
    public static TreeNode encode(Node root) {
            if (root == null) {
                return null;
            }
            TreeNode head = new TreeNode(root.val);
            head.left = processEncode(root.children);
            return head;
        }
    
        /**
         * 按照深度优先遍历构建二叉树
         *
         * @param children
         * @return
         */
        public static TreeNode processEncode(List<Node> children) {
            //二叉树头结点
            TreeNode head=null;
            //当前节点
            TreeNode cur=null;
            for (Node child:children){
                //每遍历一个child,创建一个TreeNode节点
                TreeNode node=new TreeNode(child.val);
                if (head==null){ //若二叉树头结点为null,则node直接成为头结点
                    head=node;
                }else { //若二叉树头结点不为null,则让cur的right指针指向node
                    cur.right=node;
                }
                cur=node;
                //处理以cur为头的二叉树,让其直系孩子向右
                cur.left=processEncode(child.children);
            }
            return head;
        }
    

    二叉树又如何转回多叉树呢?

     将b和f,c和h,a和c,a和d用虚线相连,如下图

    将如下的红线断开,虚线变实线

     修改如下

    将上图摆正,即将二叉树还原成多叉树

     

    二叉树转多叉树的代码实现

        /**
         * 多叉树节点类
         */
        public static class Node {
    
            public int val;
    
            public List<Node> children;
    
            public Node() {
            }
    
            public Node(int val, List<Node> children) {
                this.val = val;
                this.children = children;
            }
        }
    
        /**
         * 二叉树节点类
         */
        public static class TreeNode {
    
            public int value;
    
            public TreeNode left;
    
            public TreeNode right;
    
            public TreeNode(int value) {
                this.value = value;
            }
        }
    
    
        /**
         * 利用深度优先遍历将二叉树转成多叉树
         *
         * @param root
         * @return
         */
        public Node decode(TreeNode root) {
            if (root == null) {
                return null;
            }
            return new Node(root.value, processDecode(root.left));
        }
    
        public List<Node> processDecode(TreeNode root) {
            List<Node> children = new ArrayList<>();
            while (root != null) {
                Node cur = new Node(root.value, processDecode(root.left));
                children.add(cur);
                root = root.right;
            }
            return children;
        }

     

    展开全文
  • 遍历多叉树.rar

    2019-07-20 22:45:56
    C#实现多叉树的后序遍历。高效地实现后序遍历多叉树
  • 在实现基本多叉树的基础上,个性化拓展了实现了得到某个节点的全部递归子节点,孤独子节点,第一层级子节点对应的全部递归子节点等数据的功能处理。
  • js如何通过递归实现多叉树的遍历呢? 一、实现的效果/功能 说明:删除图片这个目录及其所有的子级目录 二、如何实现? 1.首先看一下数据表的数据机构: //部分代码 const arr = [ { "_id": "60e66c854

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档


    前言

    js如何实现删除某个文件及其所有的子级文件、子级的子级文件…
    js如何通过递归实现多叉树的遍历呢?


    一、实现的效果/功能

    在这里插入图片描述

    说明:删除图片这个目录及其所有的子级目录

    二、如何实现?

    1.首先看一下数据表的数据机构:

    //部分代码

    const arr = [
        {
            "_id": "60e66c854cb0900001598c46",
            "father_id": "//:",
            "file": {
                "name": "图片",
                "fileType": "fileder",
                "url": "",
                "size": "未知"
            },
            "createTime": 1625713795988,
            "sort": 100
        },
        {
            "_id": "60e66c8bacc1cf00011fff2f",
            "father_id": "60e66c854cb0900001598c46",
            "file": {
                "name": "imgs",
                "fileType": "fileder",
                "url": "",
                "size": "未知"
            },
            "createTime": 1625713802650,
            "sort": 100
        },
        {
            "_id": "60e66c92e22fbe0001adf45f",
            "father_id": "60e66c8bacc1cf00011fff2f",
            "file": {
                "name": "2.jpg",
                "fileType": "image/jpeg",
                "url": "https://vkceyugu.cdn.bspapp.com/VKCEYUGU-a3eacf9e-6821-4c0d-b2ca-3efa3779ac92/f7ae9b6e-3e06-4b88-9587-61e54c4f9dfa.jpg",
                "size": 22288
            },
            "createTime": 1625713809055
        },
        {
            "_id": "60e6770dacc1cf0001203d50",
            "father_id": "60e66c8bacc1cf00011fff2f",
            "file": {
                "name": "4.jpg",
                "fileType": "image/jpeg",
                "url": "https://vkceyugu.cdn.bspapp.com/VKCEYUGU-a3eacf9e-6821-4c0d-b2ca-3efa3779ac92/a2a84ea2-5945-4bb1-b9c7-065e7246cd8b.jpg",
                "size": 25730
            },
            "createTime": 1625716492032
        },
        {
            "_id": "60e69e7cf6a398000198098b",
            "father_id": "60e66c8bacc1cf00011fff2f",
            "file": {
                "name": "3.jpg",
                "fileType": "image/jpeg",
                "url": "https://vkceyugu.cdn.bspapp.com/VKCEYUGU-a3eacf9e-6821-4c0d-b2ca-3efa3779ac92/13da3630-a1e7-45cf-9e15-d137cb23f22d.jpg",
                "size": 16885
            },
            "createTime": 1625726586149
        }
        {
            "_id": "60e6772eacc1cf0001203e1b",
            "father_id": "60e677249dad8500018b082c",
            "file": {
                "name": "微信图片_20210706115238.png",
                "fileType": "image/png",
                "url": "https://vkceyugu.cdn.bspapp.com/VKCEYUGU-a3eacf9e-6821-4c0d-b2ca-3efa3779ac92/19b5dccd-d66f-4471-9475-fc4f56a74bbe.png",
                "size": 34141
            },
            "createTime": 1625716525580
        }
    ]
    

    结构说明:每一条数据都有一个"_id"以及“father_id”,"_id"是每条数据的id具有唯一性(相当于主键),“father_id"是上级目录的”_id"

    2.具体实现代码(全部代码)

    //这是从数据表中随便复制的几条数据
    const arr = [
        {
            "_id": "60e66c854cb0900001598c46",
            "father_id": "//:",
            "file": {
                "name": "图片",
                "fileType": "fileder",
                "url": "",
                "size": "未知"
            },
            "createTime": 1625713795988,
            "sort": 100
        },
        {
            "_id": "60e66c8bacc1cf00011fff2f",
            "father_id": "60e66c854cb0900001598c46",
            "file": {
                "name": "imgs",
                "fileType": "fileder",
                "url": "",
                "size": "未知"
            },
            "createTime": 1625713802650,
            "sort": 100
        },
        {
            "_id": "60e66c92e22fbe0001adf45f",
            "father_id": "60e66c8bacc1cf00011fff2f",
            "file": {
                "name": "2.jpg",
                "fileType": "image/jpeg",
                "url": "https://vkceyugu.cdn.bspapp.com/VKCEYUGU-a3eacf9e-6821-4c0d-b2ca-3efa3779ac92/f7ae9b6e-3e06-4b88-9587-61e54c4f9dfa.jpg",
                "size": 22288
            },
            "createTime": 1625713809055
        },
        {
            "_id": "60e6770dacc1cf0001203d50",
            "father_id": "60e66c8bacc1cf00011fff2f",
            "file": {
                "name": "4.jpg",
                "fileType": "image/jpeg",
                "url": "https://vkceyugu.cdn.bspapp.com/VKCEYUGU-a3eacf9e-6821-4c0d-b2ca-3efa3779ac92/a2a84ea2-5945-4bb1-b9c7-065e7246cd8b.jpg",
                "size": 25730
            },
            "createTime": 1625716492032
        },
        {
            "_id": "60e69e7cf6a398000198098b",
            "father_id": "60e66c8bacc1cf00011fff2f",
            "file": {
                "name": "3.jpg",
                "fileType": "image/jpeg",
                "url": "https://vkceyugu.cdn.bspapp.com/VKCEYUGU-a3eacf9e-6821-4c0d-b2ca-3efa3779ac92/13da3630-a1e7-45cf-9e15-d137cb23f22d.jpg",
                "size": 16885
            },
            "createTime": 1625726586149
        },
        {
            "_id": "60e677165c44840001087275",
            "father_id": "60e66c854cb0900001598c46",
            "file": {
                "name": "icons",
                "fileType": "fileder",
                "url": "",
                "size": "未知"
            },
            "createTime": 1625716500940,
            "sort": 100
        },
        {
            "_id": "60e6771b8a69dc0001e4b35a",
            "father_id": "60e677165c44840001087275",
            "file": {
                "name": "1.png",
                "fileType": "image/png",
                "url": "https://vkceyugu.cdn.bspapp.com/VKCEYUGU-a3eacf9e-6821-4c0d-b2ca-3efa3779ac92/725bdbb1-15fd-451b-84c7-9b4fe9c1eae0.png",
                "size": 118235
            },
            "createTime": 1625716506809
        },
        {
            "_id": "60e677249dad8500018b082c",
            "father_id": "//:",
            "file": {
                "name": "musics",
                "fileType": "fileder",
                "url": "",
                "size": "未知"
            },
            "createTime": 1625716515809,
            "sort": 100
        },
        {
            "_id": "60e6772eacc1cf0001203e1b",
            "father_id": "60e677249dad8500018b082c",
            "file": {
                "name": "微信图片_20210706115238.png",
                "fileType": "image/png",
                "url": "https://vkceyugu.cdn.bspapp.com/VKCEYUGU-a3eacf9e-6821-4c0d-b2ca-3efa3779ac92/19b5dccd-d66f-4471-9475-fc4f56a74bbe.png",
                "size": 34141
            },
            "createTime": 1625716525580
        }
    ]
    //装取其目录下的所有子级数据
    let alls = [];
    /**
     * 通过id查找其子级以及子级的子级以及...
     * @param {Arrow} directory 当前目录
     * @param {*} count 
     */
    function gets(directory, count = 2) {
        let temp = [];//用于装取当前_id下的子级元素
        directory.forEach(ite => {
            arr.forEach((item, index) => {
                // 判断数据中是否有当前的子级元素
                if (item.father_id == ite._id) {
                    temp.push(item);
                    // 性能优化:如果当前文件不是文件夹类型,就将其删除,减少后面arr的遍历。
                    // item.file.fileType != 'fileder' ? arr.splice(index, 1) : '';
                }
            });
        })
        alls.push(...temp);
        if (temp.length > 0) {
            // 判断是否第一次进来,如果不是则删除temp中的第一项(因为第一项已经遍历完成);
            if (count != 1) {
                temp.splice(0, 1);
            }
            // 递归  将子级进行递归取值
            gets(temp);
        }
    }
    gets([arr[0]], 1);
    
    // console.log(alls);
    // console.log(alls.length);
    
    alls.forEach(item => {
        // 查看其 所有子级的name
        console.log(item.file.name);
    });
    

    总结

    实现起来也并不是太难,主要是需要有清晰的逻辑以及对一些基础语法的掌握(如:递归级循环);

    展开全文
  • 一种基于多叉树的并行Apriori算法
  • 多叉树的实现

    2018-05-22 00:29:44
    多叉树的实现,本算法采用5比较合适,纵向遍历靠递归调用
  • QT C++ 学习之 多叉树

    2022-06-21 11:30:55
    基于C++ QT 从零实现多叉树,锻炼递归和迭代的用法

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档


    前言

    经常使用得都是二叉树,今天记录一下多叉树的基本实现步骤,其他的后续慢慢增加。

    一、初始化节点结构体

    //这里因为想尝试新的方式,没有使用struct作为基础
    class DataNode
    {
    public:
        DataNode *m_parent{nullptr};//节点的父亲
        QString m_data; //节点数据
        QList<DataNode*> m_child_list;//节点的子节点列表
        DataNode(DataNode* parent, QString data) {m_parent = parent; m_data = data;}//节点的构造方法
    };
    

    二、初始化树结构

    class MyTree
    {
    public:
        MyTree(DataNode *root);//目前只提供有参构造函数
    
        void add_node(DataNode* parent, DataNode *node); //增加子节点
        bool is_realy_contains_node(DataNode *node); //判断其是否含有某个节点
        void remove_node(DataNode *node);//删除某个节点
        void destroy_tree(DataNode* parent);//销毁树
        void ergodicTree(DataNode* root);//遍历树
    
    private:
        DataNode *Root{nullptr};//保存根节点
    };
    

    具体实现函数

    //demo使用QT编写,所以引入和使用了QT的数据类型
    #include "mytree.h"
    #include <QDebug>
    #include <QQueue>
    
    MyTree::MyTree(DataNode *root)
    {
        Root = root;
    }
    
    //给指定的父节点增加子节点
    void MyTree::add_node(DataNode *parent, DataNode *node)
    {
        parent->m_child_list.append(node);
        node->m_parent = parent;
    }
    //判断节点是否存在树中,通过递归的形式,访问节点的父节点,直到其父节点为空时,判断此节点是否和Root相同,同则存在;
    bool MyTree::is_realy_contains_node(DataNode *node)
    {
        if(node->m_parent == NULL)
        {
            if(node == Root)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
        bool val = is_realy_contains_node(node->m_parent);
        return val;
    }
    //从树中删除指定节点
    void MyTree::remove_node(DataNode *node)
    {
    	//首先调用上述函数,判定节点是否存在,不存在则不处理
        if(is_realy_contains_node(node))
        {
        	//这里要区别处理,当删除根节时,是不需要处理其子节点链表的
            if(node == Root)
            {
                destroy_tree(node);
            }
            else
            {
                destroy_tree(node);
                node->m_parent->m_child_list.removeOne(node);
            }
        }
    }
    
    //销毁树或某子树,递归执行
    void MyTree::destroy_tree(DataNode *node)
    {
    	//传入节点为空,不执行
        if(!node)
        {
            return;
        }
        //当前节点的孩子节点链表为空时,delete
        if(node->m_child_list.isEmpty())
        {
            delete node;
            qDebug() << "delete "  + node->m_data << endl;
            return;
        }
        //遍历孩子节点链表,执行递归
        for(int i = 0; i< node->m_child_list.size(); i++)
        {
            destroy_tree(node->m_child_list.at(i));
        }
        node->m_child_list.clear(); //清空链表
        delete node;//delte根节点
        qDebug() << "delete "  + node->m_data << endl;
    }
    //遍历Tree,实现了先序、后续、层次遍历
    void MyTree::ergodicTree(DataNode *root)
    {
        //先序遍历
    //    qDebug() << root->m_data <<endl;
    //    if(root->m_child_list.isEmpty())
    //    {
    //        return;
    //    }
    //    for(int i=0; i < root->m_child_list.size(); i++)
    //    {
    //        ergodicTree(root->m_child_list.at(i));
    //    }
    
        //后序遍历
    //    if(root->m_child_list.isEmpty())
    //    {
    //        qDebug() << root->m_data <<endl;
    //        return;
    //    }
    //    for(int i=0; i < root->m_child_list.size(); i++)
    //    {
    //        ergodicTree(root->m_child_list.at(i));
    //    }
    //    qDebug() << root->m_data <<endl;
    
        //层次遍历
        QQueue<DataNode*> Q;//缓存节点队列,访问的节点都追加进去
        Q.append(root);
        while (!Q.isEmpty()) {
            DataNode *node = Q.dequeue(); //弹出队列首节点
            qDebug() << node->m_data << endl;
            if(!node->m_child_list.isEmpty())
            {
                for(int i = 0; i < node->m_child_list.size(); i++)
                {
                    Q.append(node->m_child_list.at(i));
                }
            }
        }
    
    }
    };
    

    代码如下(示例):

    import numpy as np
    import pandas as pd
    import matplotlib.pyplot as plt
    import seaborn as sns
    import warnings
    warnings.filterwarnings('ignore')
    import  ssl
    ssl._create_default_https_context = ssl._create_unverified_context
    

    三、使用QT的TreeView进行验证

    //数据结构形式
    在这里插入图片描述

    demo源码如下(示例):

    //----------------————————————————————-——————————————————>源码
    
    //----------------------------------------------------------------->tree.h
    #ifndef MYTREE_H
    #define MYTREE_H
    #include <QString>
    #include <QList>
    
    class DataNode
    {
    public:
        DataNode *m_parent{nullptr};
        QString m_data;
        QList<DataNode*> m_child_list;
        DataNode(DataNode* parent, QString data) {m_parent = parent; m_data = data;}
        void init(DataNode* parent, QString data) {m_parent = parent; m_data = data;}
    };
    
    class MyTree
    {
    public:
        MyTree(DataNode *root);
        ~MyTree();
    
        void add_node(DataNode* parent, DataNode *node);
        bool is_realy_contains_node(DataNode *node);
        void remove_node(DataNode *node);
        void destroy_tree(DataNode* parent);
        void ergodicTree(DataNode* root);
    
    private:
        DataNode *Root{nullptr};
    };
    
    #endif // MYTREE_H
    
    //------------------------------------------------------------>tree.cpp
    
    #include "mytree.h"
    #include <QDebug>
    #include <QQueue>
    
    MyTree::MyTree(DataNode *root)
    {
        Root = root;
    }
    
    MyTree::~MyTree()
    {
        destroy_tree(Root);
    }
    
    void MyTree::add_node(DataNode *parent, DataNode *node)
    {
        parent->m_child_list.append(node);
        node->m_parent = parent;
    }
    
    bool MyTree::is_realy_contains_node(DataNode *node)
    {
        if(node->m_parent == NULL)
        {
            if(node == Root)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
        bool val = is_realy_contains_node(node->m_parent);
        return val;
    }
    
    void MyTree::remove_node(DataNode *node)
    {
        if(is_realy_contains_node(node))
        {
            if(node == Root)
            {
                destroy_tree(node);
            }
            else
            {
                destroy_tree(node);
                node->m_parent->m_child_list.removeOne(node);
            }
        }
    }
    
    void MyTree::destroy_tree(DataNode *node)
    {
        if(!node)
        {
            return;
        }
        if(node->m_child_list.isEmpty())
        {
            delete node;
            qDebug() << "delete "  + node->m_data << endl;
            return;
        }
        for(int i = 0; i< node->m_child_list.size(); i++)
        {
            destroy_tree(node->m_child_list.at(i));
        }
        node->m_child_list.clear();
        delete node;
        qDebug() << "delete "  + node->m_data << endl;
    }
    
    void MyTree::ergodicTree(DataNode *root)
    {
        //先序遍历
    //    qDebug() << root->m_data <<endl;
    //    if(root->m_child_list.isEmpty())
    //    {
    //        return;
    //    }
    //    for(int i=0; i < root->m_child_list.size(); i++)
    //    {
    //        ergodicTree(root->m_child_list.at(i));
    //    }
    
        //后序遍历
    
    //    if(root->m_child_list.isEmpty())
    //    {
    //        qDebug() << root->m_data <<endl;
    //        return;
    //    }
    
    //    for(int i=0; i < root->m_child_list.size(); i++)
    //    {
    //        ergodicTree(root->m_child_list.at(i));
    //    }
    //    qDebug() << root->m_data <<endl;
    
        //层次遍历
        QQueue<DataNode*> Q;
        Q.append(root);
        while (!Q.isEmpty())
         {
            DataNode *node = Q.dequeue();
            qDebug() << node->m_data << endl;
            if(!node->m_child_list.isEmpty())
            {
                for(int i = 0; i < node->m_child_list.size(); i++)
                {
                    Q.append(node->m_child_list.at(i));
                }
            }
        }
    }
    
    //------------------------------------------------------------>mainwindow.h
    #ifndef MAINWINDOW_H
    #define MAINWINDOW_H
    
    #include <QMainWindow>
    #include <QStandardItemModel>
    
    //前置声明
    class DataNode;
    
    QT_BEGIN_NAMESPACE
    namespace Ui { class MainWindow; }
    QT_END_NAMESPACE
    
    class MainWindow : public QMainWindow
    {
        Q_OBJECT
    
    public:
        MainWindow(QWidget *parent = nullptr);
        ~MainWindow();
    
        void treeView_init(DataNode *root);
    
    private:
        Ui::MainWindow *ui;
        QStandardItemModel *model{nullptr};
    
    };
    #endif // MAINWINDOW_H
    
    //------------------------------------------------------------>mainwindow.cpp
    
    #include "mainwindow.h"
    #include "ui_mainwindow.h"
    #include "mytree.h"
    #include <QDebug>
    #include <QQueue>
    
    MainWindow::MainWindow(QWidget *parent)
        : QMainWindow(parent)
        , ui(new Ui::MainWindow)
    {
        ui->setupUi(this);
        //创建treeview model
        model = new QStandardItemModel(ui->treeView);
        ui->treeView->setModel(model);
    
        //初始化树
        DataNode *Root = new DataNode(NULL, "Root");
        MyTree tree(Root);
    
        DataNode *data1_1 = new DataNode(Root, "data1_1");
        DataNode *data1_2= new DataNode(Root, "data1_2");
        DataNode *data1_3 = new DataNode(Root, "data1_3");
    
        DataNode *data2_1 = new DataNode(Root, "data2_1");
        DataNode *data2_2 = new DataNode(Root, "data2_2");
        DataNode *data2_3 = new DataNode(Root, "data2_3");
    
        DataNode *data3_1 = new DataNode(Root, "data3_1");
        DataNode *data3_2 = new DataNode(Root, "data3_2");
        DataNode *data3_3 = new DataNode(Root, "data3_3");
    
        tree.add_node(Root, data1_1);
        tree.add_node(Root, data1_2);
        tree.add_node(Root, data1_3);
    
        tree.add_node(data1_2, data2_1);
        tree.add_node(data1_2, data2_2);
        tree.add_node(data1_2, data2_3);
    
        tree.add_node(data2_2, data3_1);
        tree.add_node(data2_2, data3_2);
        tree.add_node(data2_2, data3_3);
    
        //根据Tree,初始化TreeView
        treeView_init(Root);
    }
    
    MainWindow::~MainWindow()
    {
        delete ui;
    }
    
    void MainWindow::treeView_init(DataNode *root)
    {
    	//清空model
    	model->clear();
    	//以层次遍历的方式进行Tree View的创建
        QQueue<DataNode*> Q;//节点队列
        Q.append(root);
        QQueue<QStandardItem*> QS;//QStandModel队列
        QStandardItem *item_Root = new QStandardItem();
        model->appendRow(item_Root);
        QS.append(item_Root);
    
        while (!Q.isEmpty()) {
            DataNode *node = Q.dequeue();
            QStandardItem *item_root = QS.dequeue();
            if(!node->m_child_list.isEmpty())
            {
                for(int i = 0; i < node->m_child_list.size(); i++)
                {
                    qDebug() << node->m_child_list.at(i)->m_data << endl;
                    QStandardItem *item = new QStandardItem(node->m_child_list.at(i)->m_data);
                    item_root->appendRow(item);
                    QS.append(item);
                    Q.append(node->m_child_list.at(i));
                }
            }
        }
    }
    

    实现效果如下—》
    在这里插入图片描述


    总结

    一步步进行多叉树的创建、节点增加、节点删除、输的销毁,一步步的实现过程中,增加了对递归、迭代算法的理解,后续可能进一步增加功能,目前浅浅记录一下。

    展开全文
  • 请将该字典的构造为多叉树结构,使用root表示数的根节点,并打印每个节点的值及其子节点的值。(这里确保OrderDict字典的第一个key为树的根节点)。 运行结果: 对于第二种输出格式,其关系为:......
  • 提出将动态多叉树算法应用于大气环境质量评价系统中,实现知识增值和继承。当系统扩充时,只需对增加的模式类别或训练样本构建新的分类器,其余的分类器可保持不变,从而很好地解决现有评价识别系统在学时新知识会...
  • 多叉树的基本操作(C++实现)

    千次阅读 多人点赞 2020-11-12 00:40:17
    文章目录前言创建多叉树展示多叉树销毁一颗多叉树前序遍历(递归&非递归)递归写法非递归写法后序遍历(递归&非递归)递归写法非递归写法层次遍历计算多叉树的高度计算多叉树叶子节点的个数打印输出根节点到所有...
  • 多叉树 遍历

    2019-05-25 02:32:26
    NULL 博文链接:https://zw7534313.iteye.com/blog/473446

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 14,869
精华内容 5,947
关键字:

多叉树