劳务网站有做吗,wordpress点击图片不显示,网站书店建设背景,制作网站软件叫什么个人主页 #x1f339;#xff1a;喜欢做梦 二叉树中有一个树#xff0c;我们可以猜到他和树有关#xff0c;那我们先了解一下什么是树#xff0c;在来了解一下二叉树
一#x1f35d;、树型结构
1#x1f368;.什么是树型结构#xff1f;
树是一种非线性的数据结构喜欢做梦 二叉树中有一个树我们可以猜到他和树有关那我们先了解一下什么是树在来了解一下二叉树
一、树型结构
1.什么是树型结构
树是一种非线性的数据结构它是由nn0个有限节点结点和边组成的层次结构的集合。有一个特定的节点为根节点其余节点通过边连接形成的分支每个节点可以有零个或多个子节点。把它叫做树是因为它看起来像一颗倒挂的树也就是说它是根朝上而叶朝下的。 什么是线性结构什么是非线性结构 线性结构数据元素呈现一对一的线性关系除第一个和最后一个元素外每个元素都有且仅有一个直接前驱和一个直接后继 非线性结构数据元素之间的关系不是简单的一对一一个元素可能有多个前驱或后继或者两者都有。 树的定义是递归的除根节点外的每一个结点都能引出一颗子树树型结构中子树之间不能有交集否则就不是树型结构 除了跟节点之外每个节点有且只有一个父节点一个N个节点的树有N-1条边因为根节点的上方没有边
2.什么是非树型结构
非树节点间的连通性复杂可能存在多个路径连接统一对节点也肯存在孤立节点即与其他节点无连接。 3.树型结构的基本性质 结点的度一个结点含有子树的个数称为该结点的度如上图A的度为3C的度为2树的度一颗树中所有结点度的最大值称为结点的度如上图树的度为4叶子结点或终端结点度为0的节点称为叶结点如上图E、F、G、P等结点为叶节点孩子结点或子结点一个结点含有子树的根结点称为该结点的子结点即只有根节点的结点才是子节点如上图B是A的孩子结点双亲结点或父亲结点若一个结点含有子结点则这个树称为该结点的父结点如图上A是B的父节点根结点一个树没有双亲的结点如上图A结点的层次从根开始定义根为第一层根的子结点为第二层一次类推树的高度或深度树中结点的最大层次如上图树的高度为4以下只需了解的概念非终端结点或分支结点除根结点外度不为0的结点如上图B、C、D、H为分支节点兄弟结点具有相同父结点的结点互称为兄弟结点如上图B、C是兄弟结点堂兄弟结点不具有同一个父结点但双亲在同一层的结点互为堂兄弟如上图G和H结点的祖先从根到该结点所经分支的所有结点如上图A就是所有结点的祖先子孙以某结点为根的子树中的任一节点都称为该结点的子孙。如上图所有结点都是A的子孙森林有mm0课互不相交的树组成的集合称为森林
4.树的表现形式了解
树的表现形式有很多种如双亲表示法孩子表示法、孩子双亲表示法、孩子兄弟表示法等等。这里简单了解一下其中最常见的方法就是孩子兄弟表示法
class Node{public int value;//数据public Node firstChild;//第一个孩子public Node nextBrother;//下一个兄弟
} 二、二叉树
1.什么是二叉树
二叉树二叉树是每个结点最多有两科子树的树的结构其两个子树通常称为左子树和右子树。 二叉树的递归定义 或者是一颗空树或者是一颗由一根结点和两课互不相交的分别称为左子树和右子树所组成的非空数左子树和右子树又同样是二叉树 特点
度的限制结点的度最大为2有序性左右子树由顺序即使某节点只有一颗子树也要区分左右子树
性质
若规定的根节点层数为1这一棵非空二叉树的第i层上最多有i.0个节点若规定只有根节点的二叉树的深度为1则深度为k的二叉树的最大节点数是k0;对于任何一棵二叉树如果其叶节点个数为n0度为2的非叶节点个数为n2则有n0n21对于一颗有n个节点的m个二叉树m表示树的度其最小深度计算公式nm-11 2.二叉树的类型
1.满二叉树 满二叉树每一层的结点树都达到最大除最后一层外每个节点都有两个节点。 特点
节点度数除最后一层的叶子节点外其他层的每一个的节点都有两个节点即度都为2叶子节点所有的叶子节点都在同一层且叶子节点的数量为k为数的高度节点总数 节点总数是 2.完全二叉树 完全二叉树除最后一层外其余层节点数都达到最大最后一层节点从左到右依次按顺序排列可通过数组的高效和访问完全二叉树是满二叉树的一种。 特点
节点度数除了底层的叶子节点外其余所有节点都有两个子节点即度数均为2叶子节点分布所有叶子节点都在同一层这使得树的结构呈现出完美的形态具有n个节点的完全二叉树的深度k为(n1)上取整进1 总节点个数与叶子节点个数的关系 如果总节点个数为偶数那么叶子节点为总节点个数的一半也就是n2n0如果总节点个数为奇数那么叶子节点为总节点个数的一半再减一也就是n2n0-1 节点数量对于具有n个节点的完全二叉树如果按照从上至下从左至右的顺序对所有节点从0开始编号这对于序号为i的节点有 若i0,双亲序号i-1/2;i0,i为根节点的编号无双亲节点若2i1n,左孩子序号:2i1,否则无左孩子若2i1n,右孩子序号2i2否则无右孩子 3.二叉树的创建 public class BinaryTree {public static class TreeNode{public char val;//数据public TreeNode left;//左孩子public TreeNode right;//右孩子public TreeNode(char val) {this.val val;}}public TreeNode createTree(){//创建节点TreeNode Anew TreeNode(A);TreeNode Bnew TreeNode(B);TreeNode Cnew TreeNode(C);TreeNode Dnew TreeNode(D);TreeNode Enew TreeNode(E);TreeNode Fnew TreeNode(F);TreeNode Gnew TreeNode(G);//连接节点A.leftB;A.rightC;B.leftD;B.rightE;C.leftF;C.rightG;return A;}
}
4.二叉树的遍历
二叉树的遍历是指按照一定的顺序访问二叉树中的每个节点且每个节点仅被访问一次。
二叉树的遍历方式主要有前序遍历、中序遍历、后序遍历
前序遍历
前序遍历遍历顺序是先访问根的的节点—左子树—右子树也就是根、左、右 前序遍历代码
// 前序遍历public void preOrder(TreeNode root){//判断是否有节点,没有返回if(root null){return;}System.out.print(root.val );//遍历左子树preOrder(root.left);//遍历右子树preOrder(root.right);} 顺序根节点--左子树--右子树根结点的打印位置第一个 中序遍历
中序遍历遍历顺序是先访问左子树—根的的节点—右子树也就是左、根、右 中序遍历代码 // 中序遍历public void inOrder(TreeNode root){//判断是否有节点,没有返回if(root null){return;}//遍历左子树preOrder(root.left);System.out.print(root.val );//遍历右子树preOrder(root.right);} 顺序左子树--根节点--右子树根结点的打印位置中间 后序遍历 后序遍历遍历顺序是先访问左子树—右子树—根的的节点也就是左、根、右 // 后序遍历public void postOrder(TreeNode root){//判断是否有节点,没有返回if(root null){return;}//遍历左子树preOrder(root.left);//遍历右子树preOrder(root.right);System.out.print(root.val );}
}
后序遍历的过程与前面的也是同理就不画图过多解释了。
顺序左子树--右子树--根节点根结点的打印位置最后一个
三者之间的区别 前序遍历中序遍历后序遍历访问顺序根、左、右左、根、右左、右、根根节点访问位置第一个中间最后一个应用场景二叉树结构、将表达式树转换为前缀表达式用于输出有序序列还能辅助将表达式树转换为中缀表达式二叉树的高度、节点数以及释放二叉树内存 层序遍历
层序遍历从上至下从左至右逐层访问就是层序遍历。 层序遍历的代码我后期补上或者下篇在写这篇就到这里啦~ 我的博客即将同步至腾讯云开发者社区邀请大家一同入驻https://cloud.tencent.com/developer/support-plan?invite_code3k88uddoizs48
