丽水房产网站建设,企业logo标志设计公司,最新网站网址永久发布,网上做问卷调查赚钱哪些网站好文章目录 二叉树一、树的概念1.树形结构1.1. 树的特点#xff1a;1.2 概念#xff1a;1.3 树的表示形式 2.树的应用 二、二叉树1.二叉数的概念2.满二叉树3.完全二叉树4.二叉树的性质练习#xff1a; 二叉树 一、树的概念
1.树形结构
1.1. 树的特点#xff1a; 1.根节点没… 文章目录 二叉树一、树的概念1.树形结构1.1. 树的特点1.2 概念1.3 树的表示形式 2.树的应用 二、二叉树1.二叉数的概念2.满二叉树3.完全二叉树4.二叉树的性质练习 二叉树 一、树的概念
1.树形结构
1.1. 树的特点 1.根节点没有前驱节点 2.除根节点外其余结点分成了M个互不相交的集合 3.子树的根节点有且只有一个前驱 4.树是递归定义的 树形结构中子树不能相交除了根节点外每个结点有且只有一个父结点一颗N个结点的树有N-1条边
1.2 概念 1.结点的度一个结点含子树的个数 如上图A的度为32.树的度树中结点的度最大值 数的度为3 3.叶子结点/终端结点度为0的结点没有子结点如J、F、K、L、H、I4.父结点/双亲节点含有子节点的结点. 如A是C的父结点5.子结点/孩子结点如B是A的子结点6.根结点一棵树中没有父结点的结点 A7.结点的层次从根结点开始根为第1层根的子结点为第2层…8.树的高度/深度:树中结点的最大层次。 上图中树的高度为49.分支结点/非终端结点度不为0的结点E,G…10.兄弟结点具有相同的父结点E、F11.堂兄弟结点其父结点都在同一层F、G12.森林:多棵互不相交的的数的结合
1.3 树的表示形式
孩子兄弟表示法
class Node{int val;//存储的数据Node firstChild;//第一个孩子引用Node nextBrother;//下一个兄弟引用
}一个结点中val存储数据 firstChild存该结点的第一个子结点 nextBrother存该结点下一个兄弟结点 没有孩子兄弟的时候为null 孩子双亲表示法
2.树的应用
文件夹结构
二、二叉树 1.二叉数的概念
一个根节点加上它的左子树和右子树二叉树不存在度大于2的结点一个结点只能有两个子节点二叉树是有序树子树的左右不能颠倒
2.满二叉树 1.每一层的结点都是满的除了最后一层每个结点都有两个子结点 2.每层的结点数都达到最大值 3.如果二叉树的层数为K,结点总数为2^k-1,则为满二叉树 4.结点为n,层数 log2(n1),向上取整 3.完全二叉树 1.从0开始依次从左往右按顺序一一对应 2.满二叉树是一种特殊的完全二叉树 4.二叉树的性质
1.根结点的层数为1则一棵非空二叉树的第i层上最多有 2^(i-1) 个结点2.根结点的二叉树的深度为1深度为K的二叉树的最大结点数是 2^K-13.具有n个结点的完全二叉树的深度klog2(n1) ,向上取整4.对于具有n个结点的完全二叉树如果按照从上至下从左至右的顺序对所有节点从0开始编号则对于序号为i的结点有 父结点下标为 i : 左孩子的下标2i1 ; 右孩子的下标 2i2; 子结点下标为 i : 父结点下标i - 1/ 2 5.对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0n21 也就是说度为0的结点比度为2的结点多一个有两个子节点的结点数叶子结点数-1 n0n21 练习 A.n 完全二叉树结点的个数分奇数和偶数两种情况 奇数个结点度为1的结点数为1 偶数个结点度为1的结点数为0 联立总结点数之和的式子和 n0-1n2 点击移步博客主页欢迎光临~
