廊坊企业建站模板,曾舜晞网站是哪个公司做的,软件项目过程,合肥哪里有做网页的地方二叉树详解 一:什么是树1:概念2:树的特点##3:树的一些重要概念 二:二叉树1:二叉树的概念2:二叉树的特点3:特殊的二叉树: 三:二叉树的性质四:二叉树的存储 一:什么是树
1:概念
树是一种非线性的数据结构,它是由n个节点组成的一个具有层次关系的集合,把它叫做树的原因是因为它看… 二叉树详解 一:什么是树1:概念2:树的特点##3:树的一些重要概念 二:二叉树1:二叉树的概念2:二叉树的特点3:特殊的二叉树: 三:二叉树的性质四:二叉树的存储 一:什么是树
1:概念
树是一种非线性的数据结构,它是由n个节点组成的一个具有层次关系的集合,把它叫做树的原因是因为它看起来像一棵倒挂着得树,根朝上,叶子朝下:如图所示: 注意: 树形结构中子树之间不能有交集,否则就不是树形结构
2:树的特点##
1:子树是不能相交的; 2:除了根节点以外,每个节点有且仅有一个父节点; 3:一个N个节点的树有N-1条边;
3:树的一些重要概念 结点的度:一个结点含有子树的个数称为结点的度.如上图,A结点的度为3,B结点的度为2; 树的度:一棵树中,所有结点度的最大值称为树的度 叶子节点:度为0的结点称为叶子结点 结点的层次:从根结点开始,根为第一层,根的子结点为第二层,以此类推 树的高度:树中结点的最大层次,上图树的高度就是3
二:二叉树
1:二叉树的概念
一棵二叉树是由根结点,左子树,右子树组成的,而左子树又是由根结点,左子树,右子树组成的,右子树也是由根结点,左子树,右子树组成的. 所以二叉树是递归定义的 2:二叉树的特点
1:二叉树不存在度大于2的结点; 2:二叉树的子树有左右之分,次序不能颠倒;
3:特殊的二叉树:
1:满二叉树:每一层结点个数都是2^(n-1)个结点(n表示二叉树的层数,从1开始) 如下图:
2:完全二叉树: 二叉树的结点是从上到下,从左到右,依次存放的. 如下图:
三:二叉树的性质
1:若规定根结点的层数为1,则一棵非空二叉树的第i层最多放2^(N-1)个结点. 2:若规定根节点的二叉树的深度为1,则深度为k的二叉树的最大结点数是2^k-1; 3:假设:叶子结点个数有n0个,度为2的结点个数有n2个,则n0n21; 4:共奇数个结点的完全二叉树,没有度为1的结点;共偶数个节点的完全二叉树,只有一个度为1的结点 5:具有n个结点的完全二叉树的深度为log(n1)向上取整,(log(n)1向下取整) 6:假设给完全二叉树编号,(从0开始),则编号为i的结点,父节点为(i-1)/2; 左孩子编号为:2i1,如果2i1n,则没有左孩子 右孩子编号为2i2,如果2i2n,则没有右孩子
四:二叉树的存储
二叉树的存储结构分为:链式存储和顺序存储 在这里主要介绍链式存储 /*** 孩子表示法*/static class TreeNode {int val;//数值域TreeNode left;//左孩子的引用,TreeNode right;//右孩子的引用}/*** 孩子双亲表示法*/static class TreeNode{int val;//数值域TreeNode left;//左孩子的引用TreeNode right;//右孩子的引用TreeNode parent;//当前结点父结点的引用}
