柚子快报邀请码778899分享：b树 学习二叉树(java版)
树概念二叉树概念(重点)两种特殊的二叉树二叉树的性质
二叉树三种遍历二叉树的基本操作获取树中节点个数获取叶子节点个数获取第k层节点的个数获取二叉树的高度检测为value的元素是否存在判断一棵树是不是完全二叉树
树概念
树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
1: 有一个特殊的结点，称为根结点，根结点没有前驱结点. 2: 除根结点外，其余结点被分成M(M > 0)个互不相交的集合T1、T2、…、Tm，其中每一个集合 Ti (1 <= i<= m) 又是一棵与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继. 3: 树是递归定义的。
大概就是这种:
一些重要的概念:
结点的度: 一个结点含有子树的个数称为该结点的度； 如上图：A的度为6 树的度： 一棵树中，所有结点度的最大值称为树的度； 如上图：树的度为6 叶子结点或终端结点： 度为0的结点称为叶结点； 如上图：B、C、H、I…等节点为叶结点 双亲结点或父结点： 若一个结点含有子结点，则这个结点称为其子结点的父结点； 如上图：A是B的父结点 孩子结点或子结点： 一个结点含有的子树的根结点称为该结点的子结点； 如上图：B是A的孩子结点 根结点： 一棵树中，没有双亲结点的结点；如上图：A 结点的层次： 从根开始定义起，根为第1层，根的子结点为第2层，以此类推 树的高度或深度： 树中结点的最大层次； 如上图：树的高度为4 树的以下概念只需了解，在看书时只要知道是什么意思即可： 非终端结点或分支结点： 度不为0的结点； 如上图：D、E、F、G…等节点为分支结点 兄弟结点： 具有相同父结点的结点互称为兄弟结点； 如上图：B、C是兄弟结点 堂兄弟结点： 双亲在同一层的结点互为堂兄弟；如上图：H、I互为兄弟结点 结点的祖先： 从根到该结点所经分支上的所有结点；如上图：A是所有结点的祖先 子孙： 以某结点为根的子树中任一结点都称为该结点的子孙。如上图：所有结点都是A的子孙 森林： 由m（m>=0）棵互不相交的树组成的集合称为森林
二叉树概念(重点)
一棵二叉树是结点的一个有限集合，该集合：
或者为空或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。
从上图可以看出： 3. 二叉树不存在度大于2的结点 4. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树
注意： 对于任意的二叉树都是由以下几种情况复合而成的：
两种特殊的二叉树
1. 满二叉树: 一棵二叉树，如果每层的结点数都达到最大值，则这棵二叉树就是满二叉树。也就是说，如果一棵二叉树的层数为K，且结点总数是 ，则它就是满二叉树。 2. 完全二叉树: 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
二叉树的性质
若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有 (i>0)个结点若规定只有根结点的二叉树的深度为1，则深度为K的二叉树的最大结点数是 (k>=0)对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0＝n2＋1具有n个结点的完全二叉树的深度k为 上取整对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i 的结点有： 若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点 若2i+1 二叉树三种遍历 这三种遍历是最基本的,必须掌握! 先给一颗二叉树 流程基本就是这样 二叉树的基本操作 这里才是本博客的重点,搞懂代码才算搞懂二叉树: 这是我们要模拟实现的二叉树的功能,这些搞懂了,二叉树就差不多入门了 // 获取树中节点的个数 int size(Node root); // 获取叶子节点的个数 int getLeafNodeCount(Node root); // 子问题思路-求叶子结点个数 // 获取第K层节点的个数 int getKLevelNodeCount(Node root); // 获取二叉树的高度 int getHeight(Node root); // 检测值为value的元素是否存在 Node find(Node root, int val); // 判断一棵树是不是完全二叉树 boolean isCompleteTree(Node root); 我们这里用的是枚举法创建二叉树,并不是正确的创建方法,但是为了方便我们理解,先这样用一下. class TreeNode { //定义节点 public char val; //节点值 public TreeNode left;//左孩子的引用 public TreeNode right;//右孩子的引用 public TreeNode(char val) { //构造方法 this.val = val; } } public class BinaryTree { //public BTNode root;//二叉树的根节点 /** * 这种方式 是穷举的方式创建的 * 但是 这样写不行 太low了。 * * @return */ public TreeNode createTree() { 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'); TreeNode H = new TreeNode('H'); A.left = B; A.right = C; B.left = D; B.right = E; C.left = F; C.right = G; E.right = H; return A; } } 接下来我们模拟实现一下三种遍历: 前序遍历: 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; } 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 class TestDemo { public static void main(String[] args) { BinaryTree binaryTree = new BinaryTree(); TreeNode root = binaryTree.createTree(); System.out.print("前序遍历: "); binaryTree.preOrder(root); System.out.println(); System.out.print("中序遍历: "); binaryTree.inOrder(root); System.out.println(); System.out.print("后序遍历: "); binaryTree.postOrder(root); System.out.println(); } } 有了刚刚的遍历思维,我们现在再来实现一些二叉树的基本功能: 获取树中节点个数 //获取树中节点个数 int count = 0; //记录根节点个数 public int size(TreeNode root){ if(root == null){ return 0; } count++; //借用前序遍历思想,遇到根节点就加一 size(root.left); //递归左子树 size(root.right);//递归右子树 return count; //返回根节点 } public class TestDemo { public static void main(String[] args) { BinaryTree binaryTree = new BinaryTree(); TreeNode root = binaryTree.createTree(); System.out.print("前序遍历: "); binaryTree.preOrder(root); System.out.println(); System.out.print("中序遍历: "); binaryTree.inOrder(root); System.out.println(); System.out.print("后序遍历: "); binaryTree.postOrder(root); System.out.println(); int ret = binaryTree.size(root); System.out.println("树中节点个数为: "+ret); } } 我们这里还有一种思维方式,子问题思路:想到所有节点个数就是 根节点 + 左子树节点 + 右子树节点. /** * 子问题思路 * @param root * @return */ public int size1(TreeNode root) { if(root == null) { return 0; } return size(root.left) + size(root.right) + 1; //递归左子树节点 + 右子树节点 + 根节点 } 获取叶子节点个数 /** * 获取叶子节点的个数 * 遍历思路： */ int leafCount = 0; //记录叶子节点个数 public int getLeafNodeCount(TreeNode root) { if(root == null) { return 0; } if(root.left == null && root.right == null) { //知道叶子节点左子树和右子树都为空 leafCount ++; } getLeafNodeCount(root.left); //递归左子树 getLeafNodeCount(root.right); //递归右子树 return leafCount; } public class TestDemo { public static void main(String[] args) { BinaryTree binaryTree = new BinaryTree(); TreeNode root = binaryTree.createTree(); System.out.print("前序遍历: "); binaryTree.preOrder(root); System.out.println(); System.out.print("中序遍历: "); binaryTree.inOrder(root); System.out.println(); System.out.print("后序遍历: "); binaryTree.postOrder(root); System.out.println(); int ret = binaryTree.size(root); System.out.println("树中节点个数为: "+ret); System.out.println(binaryTree.size1(root)); int ret2 = binaryTree.getLeafNodeCount(root); System.out.println("叶子节点个数为: "+ret2); } } 一样的,我们这里也用子问题思维 /** * 获取叶子节点的个数 * 子问题思路 * @param root * @return */ public int getLeafNodeCount2(TreeNode root) { if(root == null) { return 0; } if(root.left == null && root.right == null) { //当前的root是叶子节点 return 1; } return getLeafNodeCount2(root.left) + getLeafNodeCount2(root.right); } 获取第k层节点的个数 /** * 获取第K层节点的个数 * 子问题思路： * */ public int getKLevelNodeCount(TreeNode root,int k) { //获取第k层节点 if(root == null || k <= 0) { return 0; } if(k == 1) { //处于当层节点 return 1; } return getKLevelNodeCount(root.left,k-1) + getKLevelNodeCount(root.right,k-1); //左子树当层节点 + 右子树当层节点 } public static void main(String[] args) { BinaryTree binaryTree = new BinaryTree(); TreeNode root = binaryTree.createTree(); System.out.print("前序遍历: "); binaryTree.preOrder(root); System.out.println(); System.out.print("中序遍历: "); binaryTree.inOrder(root); System.out.println(); System.out.print("后序遍历: "); binaryTree.postOrder(root); System.out.println(); int ret = binaryTree.size(root); System.out.println("树中节点个数为: "+ret); System.out.println(binaryTree.size1(root)); int ret2 = binaryTree.getLeafNodeCount(root); System.out.println("叶子节点个数为: "+ret2); int ret3 = binaryTree.getLeafNodeCount2(root); System.out.println(ret3); int ret4 = binaryTree.getKLevelNodeCount(root,3); System.out.println("第三层节点个数为: "+ret4); } } 获取二叉树的高度 /** * 获取二叉树的高度 * 时间复杂度：O(n) * 空间复杂度：O() */ public int getHeight(TreeNode root) { if(root == null) return 0; int leftHeight = getHeight(root.left); int rightHeight = getHeight(root.right); return leftHeight > rightHeight ? leftHeight+1 : rightHeight+1; //精髓就是后面的加一,每次递归满足条件就加一,最后返回的就是高的那颗子树 } public class TestDemo { public static void main(String[] args) { BinaryTree binaryTree = new BinaryTree(); TreeNode root = binaryTree.createTree(); System.out.print("前序遍历: "); binaryTree.preOrder(root); System.out.println(); System.out.print("中序遍历: "); binaryTree.inOrder(root); System.out.println(); System.out.print("后序遍历: "); binaryTree.postOrder(root); System.out.println(); int ret = binaryTree.size(root); System.out.println("树中节点个数为: "+ret); System.out.println(binaryTree.size1(root)); int ret2 = binaryTree.getLeafNodeCount(root); System.out.println("叶子节点个数为: "+ret2); int ret3 = binaryTree.getLeafNodeCount2(root); System.out.println(ret3); int ret4 = binaryTree.getKLevelNodeCount(root,3); System.out.println("第三层节点个数为: "+ret4); int ret5 = binaryTree.getHeight(root); System.out.println("二叉树的高度为: "+ret5); } } 子问题思维我感觉相对简单些 public int getHeight2(TreeNode root){ if(root == null){ return 0; } return Math.max(getHeight2(root.left),getHeight(root.right)) + 1; //精髓还是在那个加一,每次取较大值后加一,最后返回的就是树的高度 } 检测为value的元素是否存在 /** * 检测值为value的元素是否存在 */ public TreeNode find(TreeNode root, char value) { if(root == null) return null; if(root.val == value) return root; //检测根节点是不是指定的元素 TreeNode ret = find(root.left,value); //遍历左子树检测 if(ret != null) { return ret; } ret = find(root.right,value); //遍历右子树检测 if(ret != null) { return ret; } return null; //没有 } public class TestDemo { public static void main(String[] args) { BinaryTree binaryTree = new BinaryTree(); TreeNode root = binaryTree.createTree(); System.out.print("前序遍历: "); binaryTree.preOrder(root); System.out.println(); System.out.print("中序遍历: "); binaryTree.inOrder(root); System.out.println(); System.out.print("后序遍历: "); binaryTree.postOrder(root); System.out.println(); int ret = binaryTree.size(root); System.out.println("树中节点个数为: "+ret); System.out.println(binaryTree.size1(root)); int ret2 = binaryTree.getLeafNodeCount(root); System.out.println("叶子节点个数为: "+ret2); int ret3 = binaryTree.getLeafNodeCount2(root); System.out.println(ret3); int ret4 = binaryTree.getKLevelNodeCount(root,3); System.out.println("第三层节点个数为: "+ret4); int ret5 = binaryTree.getHeight(root); System.out.println("二叉树的高度为: "+ret5); int ret6 = binaryTree.getHeight2(root); System.out.println(ret6); System.out.print("判断H值是否存在,存在,返回其引用"); System.out.println(binaryTree.find(root,'H')); try { System.out.println(binaryTree.find(root, 'H').val); }catch(NullPointerException e){ e.printStackTrace(); System.out.println("指定元素不存在,空指针异常了!"); } } } 判断一棵树是不是完全二叉树 这个题用队列做就简单一些了 /** * 是不是完全二叉树 * @param root * @return */ boolean isCompleteTree(TreeNode root) { if(root == null) return true;//空树也是完全二叉树 Queue queue.offer(root); //先入根节点 while (!queue.isEmpty()) { TreeNode cur = queue.poll(); //出队 if(cur != null) { //不为null,就将对应的左右子树入队 queue.offer(cur.left); queue.offer(cur.right); }else { //出队元素为null break; } } while (!queue.isEmpty()) { //开始判断二叉树是否为完全二叉树 TreeNode top = queue.peek(); if(top != null) { //如果此队列里还有不为null的节点,说明这颗二叉树不是完全二叉树 return false; } queue.poll(); } return true; //走到了这里,说明他是一颗完全二叉树 } 这是我们创建的二叉树 此时他不是一颗完全二叉树 public class TestDemo { public static void main(String[] args) { BinaryTree binaryTree = new BinaryTree(); TreeNode root = binaryTree.createTree(); System.out.print("前序遍历: "); binaryTree.preOrder(root); System.out.println(); System.out.print("中序遍历: "); binaryTree.inOrder(root); System.out.println(); System.out.print("后序遍历: "); binaryTree.postOrder(root); System.out.println(); int ret = binaryTree.size(root); System.out.println("树中节点个数为: "+ret); System.out.println(binaryTree.size1(root)); int ret2 = binaryTree.getLeafNodeCount(root); System.out.println("叶子节点个数为: "+ret2); int ret3 = binaryTree.getLeafNodeCount2(root); System.out.println(ret3); int ret4 = binaryTree.getKLevelNodeCount(root,3); System.out.println("第三层节点个数为: "+ret4); int ret5 = binaryTree.getHeight(root); System.out.println("二叉树的高度为: "+ret5); int ret6 = binaryTree.getHeight2(root); System.out.println(ret6); System.out.print("判断H值是否存在,存在,返回其引用"); System.out.println(binaryTree.find(root,'H')); try { System.out.println(binaryTree.find(root, 'H').val); }catch(NullPointerException e){ e.printStackTrace(); System.out.println("指定元素不存在,空指针异常了!"); } boolean flag = binaryTree.isCompleteTree(root); System.out.println(flag); } } 这时我们屏蔽掉H 就可以判断他是一颗完全二叉树了. 各位,代码可以保存复习备用!! 柚子快报邀请码778899分享：b树 学习二叉树(java版)
发表评论