想做苗木生意网站怎么怎么做,一家专门做打折的网站,怎么做公众号,有什么网站可以做浏览单找往期文章包括但不限于本期文章中不懂的知识点#xff1a; 个人主页#xff1a;我要学编程(ಥ_ಥ)-CSDN博客 所属专栏#xff1a;数据结构#xff08;Java版#xff09; 二叉树的前置知识#xff08;概念、性质、、遍历#xff09;
通过上篇文章的学习#xff0c;我们…找往期文章包括但不限于本期文章中不懂的知识点 个人主页我要学编程(ಥ_ಥ)-CSDN博客 所属专栏数据结构Java版 二叉树的前置知识概念、性质、、遍历
通过上篇文章的学习我们已经知道什么是二叉树以及其性质和遍历的方式了。接下来主要是实现代码。
目录
伪创建二叉树
遍历二叉树
获取二叉树中节点的个数
获取二叉树中叶子节点的个数
获取二叉树中第K层节点的个数
获取二叉树的高度
在二叉树中找寻元素 伪创建二叉树
为啥叫伪创建二叉树呢因为我们现在才刚开始学习二叉树而创建二叉树是一个非常复杂的过程树的递归定义的。因此我们就先手动的来创建二叉树。树是有一个一个的结点组成因此得先把结点创建出来。树的结点我们采用的是简单的孩子表示法 // 树的结点static class TreeNode {public char val; // 数据域public TreeNode left; // 左子树public TreeNode right; // 右子树public TreeNode(char val) {this.val val;}}
创建的二叉树图形如下 public TreeNode createBinaryTree() {TreeNode A new TreeNode(A);TreeNode B new TreeNode(B);TreeNode C new TreeNode(C);TreeNode D new TreeNode(D);TreeNode E new TreeNode(E);TreeNode F new TreeNode(F);TreeNode G new TreeNode(G);// 根据图形关系把结点之间相连A.left B;A.right C;B.left D;B.right E;C.left F;C.right G;// 返回根结点return A;}
遍历二叉树
二叉树创建完成后我们就可以遍历打印二叉树看看是否符合我们的预期结果。遍历的四种方式我们前面也学习了。
前序遍历 // 前序遍历public void preOrder(TreeNode root) {if (root null) {return;}// 打印根结点的值System.out.print(root.val );// 递归遍历根的左子树preOrder(root.left);// 递归遍历根的右子树preOrder(root.right);}
递归的限制条件当递归到 root 为 null 时就开始回退。随着递归的深入root 不断的接近 null。
中序遍历 // 中序遍历public void inOrder(TreeNode root) {// 中序遍历左子树-根-右子树if (root null) {return;}// 递归遍历根的左子树inOrder(root.left);// 打印根结点的值System.out.print(root.val );// 递归遍历根的右子树inOrder(root.right);}
后序遍历 // 后序遍历public void postOrder(TreeNode root) {// 后序遍历左子树-右子树-根if (root null) {return;}// 递归遍历根的左子树postOrder(root.left);// 递归遍历根的右子树postOrder(root.right);// 打印根结点的值System.out.print(root.val );}
由于层序遍历还是比较复杂因此我们后面再学习。
获取二叉树中节点的个数
思路一这个同样是遍历二叉树遇到不为空的结点就最后统计的就是树的节点个数。 // 记录节点个数public int treeNodeSize; public void size(TreeNode root) {if (root null) {return;}// 根结点treeNodeSize;// 左子树size2(root.left);// 右子树size2(root.right);}
思路二整棵树的节点个数等于 根结点左子树的节点个数右子树的节点个数 // 获取树中节点的个数public int size(TreeNode root) {if (root null) {return 0;}// 左子树的节点个数右子树的节点个数根结点return size(root.left)size(root.right)1;}
思路一采用的是遍历的方式思路二采用的是化为子问题的方式。思路二也是更加接近递归的方式。
获取二叉树中叶子节点的个数
思路首先我们得知道什么是叶子节点。叶子结点的特点是其左孩子和右孩子都是null。同样这也是采用遍历的方式。
法一采用子问题思路 // 获取叶子节点的个数public int getLeafNodeCount(TreeNode root) {if (root null) {return 0;}// 遇到叶子结点就返回1if (root.left null root.right null) {return 1;}// 返回左子树的叶子节点个数右子树的叶子节点个数return getLeafNodeCount(root.left) getLeafNodeCount(root.right);}
法二采用遍历思路 public int leafSize;public void getLeafNodeCount(TreeNode root) {if (root null) {return;}if (root.left null root.right null) {leafSize;}// 遍历左子谁getLeafNodeCount2(root.left);// 遍历右子树getLeafNodeCount2(root.right);}
获取二叉树中第K层节点的个数 上面是对于第K层的介绍根结点是作为第一层。
思路当K为1时就可以直接返回这一层的节点个数即可。因此我们就是要递归到K不断的接近1.
法一 采用子问题思路 // 获取第K层节点的个数public int getKLevelNodeCount(TreeNode root, int k) {// 假定不存在K无效的情况if (root null) {return 0;}if (k 1) {return 1;}// 左子树的第k-1层的节点个数右子树的第k-1层的节点个数return getKLevelNodeCount(root.left, k-1) getKLevelNodeCount(root.right, k-1);}
法二 采用遍历思路 public int getLevelNodeSize;public void getKLevelNodeCount(TreeNode root, int k) {// 假定不存在K无效的情况if (root null) {return;}if (k 1) {getLevelNodeSize;}// 遍历左子树的第k-1层getKLevelNodeCount2(root.left, k-1);// 遍历右子树的第k-1层getKLevelNodeCount2(root.right, k-1);}
获取二叉树的高度
思路获取二叉树的高度和求第K层节点的个数类似。同样根结点算高度为1。接着就是分别递归计算左子树和右子树的高度的最大值。
采用子问题思路 // 获取二叉树的高度public int getHeight(TreeNode root) {if (root null) {return 0;}// 左子树与右子树的最大高度根结点return Math.max(getHeight(root.left), getHeight(root.right)) 1;}
这个如果不采用子问题思路而是用遍历思路的话只能用层序遍历来写又因为层序遍历过于复杂因此我们暂时先不写这个代码。
在二叉树中找寻元素 思路这个比较简单就是遍历去比较即可。 // 检测值为value的元素是否存在public TreeNode find(TreeNode root, int val) {if (root null) {return null;}// 采用前序遍历的方式根-左子树-右子树// 根if (root.val val) {return root;}// 在左子树中寻找肯定有一个结果TreeNode findLeft find(root.left, val);// 如果不为null则说明找到了if (findLeft ! null) {return findLeft;}// 在右子树中寻找肯定有一个结果不管结果如何直接返回即可return find(root.right, val);}
注意这里在寻找二叉树中的节点时采用前序遍历的方式是最有效率的。因为前序遍历是首先比较根结点而我们就是需要比较根结点。
对于二叉树的基本操作我们就已经学习完了。基于上述基本操作就可以进行一些简单的刷题了后续也会在刷题中继续完善二叉树的相关操作。
好啦本期 数据结构之初始二叉树2的学习之旅就到此结束啦我们下一期再一起学习吧
