-
2020-02-12 14:51:41更多相关内容
-
C计算二叉树节点(节点总数,树深度,双,单,叶子)
2022-02-06 16:38:561、树深度 //树深度 int BinTreeDepth(BinTree* T) { //计入左右子树深度 int leftdep, rightdep; if (T == NULL) { return 0; } else { leftdep = BinTreeDepth(T->lchild); //遍历左子树 rightdep...1、树深度
//树深度 int BinTreeDepth(BinTree* T) { //计入左右子树深度 int leftdep, rightdep; if (T == NULL) { return 0; } else { leftdep = BinTreeDepth(T->lchild); //遍历左子树 rightdep = BinTreeDepth(T->rchild); //遍历右子树 } //判断左右子树,返回更深的一方加一 if (leftdep > rightdep) { return leftdep + 1; } else { return rightdep + 1; } }
2.计算节点总数
//二叉树节点总数 int NodeCount(BinTree* T) { if ( T == NULL ) { return 0; } else { //如果不为空,则返回左右子树个数之和加一 return ( NodeCount(T->lchild)+ NodeCount(T->rchild) + 1 ); } }
3.计算双孩子节点个数
//获取双孩子节点个数 int TowSonCount(BinTree* T) { if ( T == NULL ) { return 0; } //左右子树均不为空的时候,遍历左、右子树对返回值进行加1 if ( T->lchild && T->rchild ) { return ( TowSonCount(T->lchild) + TowSonCount(T->rchild) + 1 ); } else { return ( TowSonCount(T->lchild) + TowSonCount(T->rchild) ); } }
4.计算单孩子节点个数
//获取单孩子节点个数 int OneSonCount(BinTree* T) { if ( T == NULL ) { return 0; } //左子树不为空,右子树为空,或,左子树为空,右子树不为空的情况下,是单孩子节点 if ( (T->lchild && T->rchild == NULL) || (T->rchild && T->lchild == NULL) ) { return ( OneSonCount(T->lchild) + OneSonCount(T->rchild) + 1 ); } else { return ( OneSonCount(T->lchild) + OneSonCount(T->rchild) ); } }
5.计算叶子节点个数
//获取叶子节点个数 int LeafCount(BinTree* T) { if ( T ==NULL ) { return 0; } //左右子树都为空的时候是叶子节点 if ( T->lchild == NULL && T->rchild == NULL) { return ( LeafCount(T->lchild) + LeafCount(T->rchild) + 1 ); } else { return ( LeafCount(T->lchild) + LeafCount(T->rchild) ); } }
-
Java 实现树结构计算各个节点数的和
2020-03-02 13:48:38之前有个需求就是树结构展示需要计算每个节点的和,我就一直想怎么实现,到最后有思路但是有些问题还是卡在那里了,后来网上搜索给了灵感实现出来了,但是那个网址没有保存关闭以后就找不到了,那么我就就我的实现...之前有个需求就是树结构展示需要计算每个节点的和,我就一直想怎么实现,到最后有思路但是有些问题还是卡在那里了,后来网上搜索给了灵感实现出来了,但是那个网址没有保存关闭以后就找不到了,那么我就就我的实现方式记录在博客里把,最后实现的功能如下图:
1.父节点计算子节点的和,子节点在计算子子节点的和。。。
2.看了上面的图起码知道一定得先计算没有子节点的节点也就是最后一个节点,才能依次计算父节点,这样才能计算正确的数字和,那么怎么实现呢?上代码
先传输父节点的数据
public List<TreeDTO> queryTree() { // 查询库的数据 List<Map<String, Object>> list = modelBaseMapper.selectMaps(null); // *********************求节点的和-开始 if (list.size() > 0) { List<Map<String, Object>> templist = new ArrayList<>(); for (int i = 0; i < list.size(); i++) { if (list.get(i).containsKey("PARENTID")) { // 获取所有的父节点 if (list.get(i).get("PARENTID").toString().equals("0")) { // 求得各个节点的和 doCount(list.get(i), list); } } } } // *********************求节点的和-结束 // 封装树结构 }
3.list的结构就还是数据库查询的数据,此时还没生成树结构,大致结构如下:
[{"PARENTID":"0","MODELID":"24CBEFABDE274BE1B78119048FEC2A34","MODELNAME","xx管理","TOTALCOUNT":"0"},{"PARENTID":"1C20742A5B6945F7A9B3550E585D200E","MODELID":"41757D73A0424E3B8E4598A13EC9B2C1","MODELNAME","xxxxxx评价模型","TOTALCOUNT":"4"},{"PARENTID":"1C20742A5B6945F7A9B3550E585D200E","MODELID":"5CB4C8BA579E4A0A8D5D2EAC2850168F","MODELNAME","xxxxxx评价模型","TOTALCOUNT":"5"},。。。。。]
4.进行求和代码,主要是进行递归处理方式
/** * 实现给各节点计算总和 * * @param root 根 * @param allList 所有的数据 * @return */ public static Integer doCount(Map<String, Object> root, List<Map<String, Object>> allList) { Integer sum = 0; // 获得当前节点的子节点数据 List<Map<String, Object>> templist = findByQueryString(root.get("MODELID").toString(), allList); // 当前节点没有子节点的时候返回需要的数字。 if (templist == null || templist.size() == 0) { if (null != root.get("TOTALCOUNT")) { return Integer.parseInt(root.get("TOTALCOUNT").toString()); } else { return sum; } } // 当前节点有子节点的时候,进行循环查找子节点 if (templist != null && templist.size() > 0) { for (Map child : templist) { //递归 Integer numCount = doCount(child, allList); //求和计算 sum += numCount; } } // 给当前节点赋值为计算完毕的值 root.put("TOTALCOUNT", sum.intValue()); return sum; }
5.查找当前传递的节点的子节点数据,并返回代码
/** * 递归查找子节点 * * @param pid id * @param allList 所有的数据 * @return */ public static List<Map<String, Object>> findByQueryString(String pid, List<Map<String, Object>> allList) { List<Map<String, Object>> childist = new ArrayList<>(); // 查找子节点操作 for (Map<String, Object> map : allList) { if (map.get("PARENTID").toString().equals(pid)) { childist.add(map); } } return childist; }
6.以上就是所有的模型计算和的代码,希望可以帮助你!
-
树的介绍&树的节点计算公式(跑路人笔记)
2022-04-01 21:26:00对树和二叉树的部分介绍和节点计算公式的总结舒文未来目标: 进大厂啊进大厂~🤪.让我家人放松一些,努力让生活更棒,好耶!
舒文现状:大一菜鸡,从食品转码,目前已经结识了很多学习的朋友.(挺棒的👍)
博客目的:写博客是为了记录自己的学习路径.也是为了让面试官眼前一亮,然后就是装逼.
小小推荐: 我在CSDN和朋友创建管理了一个社区大家如果感兴趣的话可以来看看👉非科班转码社区.👈
现阶段目标: 好好学习基础知识多多了解计算机行业情况.保持良好的身体素质,多多交朋友,多多犯错多多从错误中学习😍.
之前的博客是整理了两道关于队列和栈的题目:👉设计循环队列(c实现)(链表和顺序表版)👈.前言
这篇主要讲解树的知识点,没有代码实现但是知识点较多,我会尽量细的向大家讲解.毕竟这也是俺的笔记.
最近朋友越来越卷了,我也要抓紧跟上,不然清明节就是给我过了,呜呜呜呜呜.
正文
树的基础概念
树一种非线性的数据结构,它是由n(n>=0)个有限节点组成的具有层次关系的集合.把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。
- 有一个节点是根节点,根节点是所有节点的唯一交点,及上图的A节点,根节点的分支是类似于根节点结构的子树
- 子树的结构一定是和树的结构类似的子树有且只有一个根
- 树的问题可以分为总问题和多个子问题所有树是通过递归定义的
- 树的之间是不能有交集的如果有交集就不能叫做树如下图p和I有交集就不可以叫做这个为树
因为上个特性所有我们的树在有N个节点的情况下也有着N-1个边(边就是连接两个节点的线😁).
除了根节点外每个节点有且只有一个父节点.
树的相关性质
节点的度:一个节点含有的子树的个数称为该节点的度; 如下图:A的为6
叶节点或终端节点:度为0的节点称为叶节点; 如下图:B、C、H、I…等节点为叶节点,及下面无连接节点的节点.
非终端节点或分支节点:度不为0的节点; 如上图:D、E、F、G…等节点为分支节点,这个和叶子节点或终端节点反着来除根节点(A)外其他非叶子节点都是非终端节点或分支节点
(记得是除A以外的)双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点; A是B的父节点.
孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点; 如上图:B是A的孩子节点
父亲节点和孩子可以一起理解如下图
A就是D和E的父亲节点相应的D和E就是A的孩子节点
兄弟节点: 具有相同父节点的节点互称为兄弟节点,这个兄弟只能是亲兄弟; 如上图:D,E就是兄弟节点
树的度:一棵树中,最大的节点的度称为树的度; 如上图:树的度为6;
简单易懂我们的A的度就是6所以树的度就和A的度相同节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;
树的高度或深度:树中节点的最大层次; 如上图:树的高度为4
堂兄弟节点:双亲在同一层的节点互为堂兄弟;
节点的祖先:从根到该节点所经分支上的所有节点;如上图:A是所有节点的祖先
子孙:以某节点为根的子树中任一节点都称为该节点的子孙。如上图:所有节点都是A的子孙
有趣的是如果得H的祖先和子孙H本身就可以算作他自己的祖先或子孙,不过具体情况还是要看一下题目要求,所以子孙和祖先算是一个比较模糊的概念了.森林:由m(m>0)棵互不相交的树的集合称为森林;多颗树便是森林
树的结构节点代码实现
树节点有多种形势的实现,不过舒文指向介绍最优秀的一种结构如下代码
typedef int DataType; struct Node { struct Node* _firstChild1; // 第一个孩子结点 struct Node* _pNextBrother; // 指向其下一个兄弟结点 DataType _data; // 结点中的数据域 };
这种结构无论下面是多少个孩子旁边有多少个兄弟我们都可以进行表示.
如下图表示了旁边的树图.
简化图如下
这种结构是公认的最优的结构,如果有更优的,请务必让俺瞅瞅,咱一定认真学习.二叉树的概念
树的特殊结构,是个被计划生育的树,及每个节点最多只有两个子节点.也就是树的度最大为2
二叉树的组成: 1. 为空 2. 由根和左右子树组成.
二叉树的结构: 二叉树的左树和右树是有区别的不可以交换所以二叉树有着更多的性质和特性,下面我们来介绍二叉树的特性.
特殊二叉树
满二叉树
每一层的节点数都达到了最大值,节点数目满足以二为公比的等比数列求和公式及2k-1,则他就是满二叉树
完全二叉树
完全二叉树要求若为k的深度的完全二叉树要求前k-1深度的节点未满第k层节点必须连续
二叉树的性质
- 若规定根节点的层数为1,则一棵非空二叉树的第i层上最多有2(i-1)个结点.
- 若规定根节点的层数为1,则深度为h的二叉树的最大结点数是2h-1.
- 对任何一棵二叉树, 如果度为0其叶结点个数为n0, 度为2的分支结点个数为n2,则有n0 = n2+1
- 若规定根节点的层数为1,具有n个结点的满二叉树的深度,h=log2(n+1) . (ps: 是log以2为底,n+1为对数)
- 对于具有n个结点的完全二叉树,如果按照从上至下从左至右的数组顺序对所有节点从0开始编号,则对于序号为i的结点有:
1.若i>0,i位置节点的双亲序号:(i-1)/2;i=0,i为根节点编号,无双亲节点
2.若2i+1<n,左孩子序号:2i+1,2i+1>=n否则无左孩子
3.若2i+2<n,右孩子序号:2i+2,2i+2>=n否则无右孩子
结尾
后续舒文会再给一些关于二叉树的计算类型的选择题(大约三天后)大家期待一下。ʕ ᵔᴥᵔ ʔ
-
全国计算机二级考试基础知识:计算树的节点数
2020-08-29 10:33:08则该树中度为2的节点数为:1 解析:树的度为3,表示树中只存在度为0、1、2、3的结点。设总结点树是n,则度为2的结点为n-9-20-0=n-29.根据树中的节点数=树中所有结点的度之和+1,得93+(n-29)2+01+200+1=n,则n=30,... -
二叉树(计算节点数)
2020-07-11 15:06:47题目链接:link. 这个????大概长这样 题目大意:现在给系统两个数m和n。 m:选定节点 ...不断的在内部调用leaf函数,每一次调用相当于在计算下一层所加入的节点数 #include<iostream> using namespac -
递归算法计算二叉树中叶子节点的数目
2016-04-28 11:54:05递归算法计算二叉树中叶子节点的数目 -
二叉树节点数该怎么计算?有几种算法?
2021-07-31 01:10:53每一棵二叉树中都有左右两棵子树,子树中又有无数节点,那你们知道子树中的节点该怎么计算吗?快来跟小编了解一下吧。二叉树算法概念对于任何一棵二叉树来说,其叶子结点的数目为n0,且其度数为2的结点数n2,则n0=n2+... -
java 计算树结构叶子节点总数
2020-08-12 10:55:16public int sumtotal(List<CommonTree> listCommon,int sum) { for(CommonTree commonTree:listCommon) { List<CommonTree> chList=commonTree.getChildren(); if(chList!=null&... -
数据结构——计算节点个数和二叉树高度(C语言版)
2020-12-12 23:27:09数据结构——计算节点个数、二叉树高度一、计算各种节点(1)计算总节点:(2)计算单分支节点:(3)计算双分支节点:二、计算二叉树高度代码...让根节点指针开始,进行二叉树的遍历,遍历树节点中不为NULL下,及存 -
二叉树所有节点数、叶子节点数的计算
2020-04-16 10:46:36一、假设二叉树采用二叉链存储结构,设计一个算法,计算一颗给定二叉树的所有节点数。 解法一 int n; void count(BTNode* p) { if(p) { ++n; count(p->left); count(p->right); } } 解法二 int ... -
二叉树-递归计算某节点的层数/深度
2020-10-14 13:38:26目标节点在已知节点的子树中才可以,通常传入整个树,如下 level = Rec_GetLevel(t, 1, target); #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define NOT_FOUND -999 ... -
二叉树节点数和深度的计算
2020-11-24 22:49:28先来计算二叉树节点的个数,首先我们可以根据先序遍历或者中序遍历或者后序遍历的次数,使用一个计数器对节点的个数进行计数操作。这里使用的是先序非递归遍历来实现: int PreOrder(BtNode* ptr) { int sum = 0; ... -
树的度、叶子节点相关计算问题
2019-09-12 11:41:37设树T的度为4,其中度为1,2,3,和4的结点个数分别为4,3,1,1。则T中的叶子数为? 规律总结 规律1: (节点个数)m=(边数)n+1 规律2: 度为节点的子女个数,可以看作几个出边就是几个度,叶子节点没有度 ... -
【算法】完全二叉树的节点数计算
2020-03-09 15:17:04再讲完全二叉树节点数计算之前,我们先来看什么是完全二叉树 完全二叉树就是,树的高度差最多为1,且最后一层的节点都是紧凑靠左排列的。 满二叉树就是一种特殊的完全二叉树**,每层都是满的,除叶子结点外,每一层... -
树的节点、度数、高度、深度、遍历
2019-09-27 21:35:341.节点的度与树的度 节点的度:结点拥有的子树数目称为结点的度,叶子结点 就是度为0的结点 ...节点数n=n0+n1+n2, ( n0:度为0的结点数,n1:度为1的结点 n2:度为2的结点数。 n是总结点) 非空二叉树,n0=n2... -
线段树节点个数的递推公式与通项公式
2015-03-13 16:16:19不用二叉堆而是用含有指针域的节点构造线段树的话,其所需节点个数与区间长度N的关系是什么呢? 递推公式 记f(x)表示根节点区间长度为x的线段树的节点个数, 那么有: / 2f(x/2) + 1, 当x>1且x为偶数时; f(x) = | ... -
求树的叶子节点个数
2018-07-22 10:43:06首先我们得知道什么事叶子节点,叶子节点就是只有根节点没有子节点的节点。下面我们就根据这个特性来写一下这个程序 typedef struct BiTNode ...//用来存放叶子节点个数 void CountLef(BiTNode *root) { ... -
数据结构——树中结点数的两种计算方式
2021-08-18 22:04:16学这个树的时候,经常因为这个树结点数的计算而头疼,因为不理解,可能是因为比较笨吧哈哈。在思考了很久后写下自己的理解。 总结 设一个度为4的树,其中度为0,1,2,3,4的结点数分别为n0,n1,n2,n3,n4 (n0... -
递归计算二叉树的叶子节点个数
2018-07-24 00:07:35#include "stdio.h" #include "malloc.h" typedef struct BiTNode{ ... /*计算二叉树中叶子结点的个数 */ printf("The number of leaves of BTree are %d\n",count); getchar(); getchar(); } -
二叉树节点数及叶子节点数
2018-12-19 17:05:42今天写的是求二叉树节点个数及叶子节点个数的代码。采用了递归的方法求解。 代码如下: #include "stdafx.h" #include "stdio.h" #include "stdlib.h" typedef struct BiTNode { ... -
java代码实现求树的高度和节点数
2018-10-23 19:56:54求二叉树的高度 public int getHeight(TreeNode node){ if(node == null){ return 0; } int i = getHeight(node.left); int j = getHeight(node.right);...求二叉树的节点数 public int getSize(... -
(树_11)求二叉树的所有节点个数
2020-10-01 21:03:56完全二叉树的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~2h个节点。 示例: 输入... -
Java给树加子节点个数统计
2017-10-26 11:38:00Java给树加子节点个数统计 通过后台实现 private List<Photo> getChildren(Photo photo) { List<Photo> children = new ArrayList<>(); if (!... -
数据结构之节点数与边数的计算(复习笔记)
2020-12-22 11:05:26数据结构之有关节点数的计算 一、树 1.1 二叉树 1、二叉树的基本概念: 二叉树是n(n>=0)个具有相同类型的数据元素的有限集合: (1)当n=0时为空二叉树 (2)当n>0时,数据元素分为:一个称为根的数据元素和... -
完全二叉树叶节点计算
2017-03-06 17:14:22当节点数N为奇数时,说明该树结构中没有度为1的节点。 当节点数为偶数时,说明有一个度为1的节点,如上图情况。 对于一个非空二叉树,有以下等式成立 n0=n2+1举例说明: 设一棵完全二叉树共有699个节点,则在该... -
第2关:计算二叉树的深度和节点个数
2021-07-13 22:08:49// 右子树指针 BiTreeNode(){ // 树节点初始化 left=NULL; right=NULL; } BiTreeNode(char item){ // 用元素初始化树节点 data=item; left=NULL; right=NULL; } ~BiTreeNode(){ // 释放树节点内存 left=NULL; right... -
计算二叉树的高度、节点数、叶子节点数
2017-11-08 09:38:20#include #include typedef char dataType; struct TreeNode{ dataType data;...最后输入AB##C#D###即可求得二叉树的高度为:3 二叉树的总结点数为:4 二叉树的叶子节点数:2 二叉树的最大值为:D -
二叉树的基本内容(创建,遍历,节点个数,深度计算)
2022-03-21 08:24:08//该函数不需要返回值,因为节点数都放在了数组里面 _preorderTraversal(root,a,&i); //返回值 *returnSize=size; return a; } tips:对于上述这种 oj 题,输出型参数需要开辟空间,然后赋值返回的,各位小伙伴们在... -
二叉树的建立,遍历及计算叶子节点,深度计算
2010-11-29 20:27:23建立 先序遍历 中序遍历 后续遍历 计算深度 叶子节点数