【数据结构与算法之树结构】案例 女爷i 2024-03-25 14:12 59阅读 0赞 #### 【数据结构与算法之树结构】案例 #### #### 文章目录 #### * * * 【数据结构与算法之树结构】案例 * * * 1 计算二叉树的深度 * 2 计算二叉树中叶子节点的数量 * 3 二叉排序树的最低公共祖先问题 ###### 1 计算二叉树的深度 ###### 编写一个程序,计算二叉树的深度。 Java代码实现: public int getBinaryTreeDepth(BinaryTreeNode root) { int leftHeight, rightHeight, maxHeight; if (root != null) { leftHeight = getBinaryTreeDepth(root.leftChild); rightHeight = getBinaryTreeDepth(root.rightChild); maxHeight = leftHeight > rightHeight ? leftHeight : rightHeight; return maxHeight + 1; } else { return 0; } } 测试 ![在这里插入图片描述][92761e17e5034feba59e4204c4b59b87.png_pic_center] public static void main(String[] args) { BinaryTree binaryTree = new BinaryTree(); LinkedList<Integer> nodes = new LinkedList<>(Arrays.asList(new Integer[]{ 2, 3, 5, null, null, 0, null, null, 6, 7, null, null, null})); binaryTree.CreateBinaryTree(nodes); System.out.println(binaryTree.getBinaryTreeDepth(binaryTree.root)); } 运行结果 ![在这里插入图片描述][c2b2bd677a964c1d9bfd172844ae47a5.png_pic_center] 没问题。 ###### 2 计算二叉树中叶子节点的数量 ###### 编写一个算法,计算二叉树中叶子节点的数量。 ① 利用二叉树本身的递归特性,计算二叉树的叶子节点数其实就是计算二叉树根节点左子树和右子树的叶子节点的数量之和。 Java实现: public int getBinaryTreeLeavesNumber() { return getBinaryTreeLeavesNumber(root); } public int getBinaryTreeLeavesNumber(BinaryTreeNode root) { if (root == null) { return 0; } else if (root.leftChild == null && root.rightChild == null) { return 1; } else { return getBinaryTreeLeavesNumber(root.leftChild) + getBinaryTreeLeavesNumber(root.rightChild); } } 还有一种方法,通过遍历,在遍历二叉树时可以访问到二叉树中的每一个节点,所以可以通过判断 + 累加,得出叶子节点数量。 Java实现: private int count = 0; public int countBinaryTreeLeavesNumberByTraversing() { countBinaryTreeLeavesNumberByTraversing(root); return count; } public void countBinaryTreeLeavesNumberByTraversing(BinaryTreeNode root) { if (root != null && root.leftChild == null && root.rightChild == null) { count = count + 1; } if (root != null) { countBinaryTreeLeavesNumberByTraversing(root.leftChild); countBinaryTreeLeavesNumberByTraversing(root.rightChild); } } 测试 ![在这里插入图片描述][b1a01139442b4c5488983c544f89b533.png_pic_center] public static void main(String[] args) { BinaryTree binaryTree = new BinaryTree(); LinkedList<Integer> nodes = new LinkedList<>(Arrays.asList(new Integer[]{ 2, 3, 5, null, null, 0, null, null, 6, 7, null, null, null})); binaryTree.CreateBinaryTree(nodes); System.out.println(binaryTree.getBinaryTreeLeavesNumber()); System.out.println(binaryTree.countBinaryTreeLeavesNumberByTraversing()); } 运行结果 ![在这里插入图片描述][88ce74ef489942b5b51f4ed063128b6b.png_pic_center] 没问题。 ###### 3 二叉排序树的最低公共祖先问题 ###### 在一棵二叉排序树中找到节点值value1和节点值value2 的最低公共祖先。 其实在二叉排序树中,如果两个节点分别位于根节点的左子树和右子树,那么根节点必然是它们的最低公共祖先。 当然如果给定的两个节点本身就存在祖先和子孙关系,就不能像上面那样找了, 假定给定的两个节点分别为a和b,并且a是b的祖先,那么节点a和b的最低公共祖先就是a的父节点,另外如果value1或value2的其中一个是根节点,那么不存在最低公共祖先。【除非题目允许a或b作为最低公共祖先】 Java实现: public int findLowestCommonAncestor(int value1, int value2) { return findLowestCommonAncestor(root, value1, value2); } public int findLowestCommonAncestor(BinaryTreeNode root, int value1, int value2) { BinaryTreeNode curNode = root; if (root.data == value1 || root.data == value2) { return -1; // 不存在公共祖先 } while (curNode != null) { if (curNode.data > value1 && curNode.data > value2 && curNode.leftChild.data != value1 && curNode.leftChild.data != value2) { curNode = curNode.leftChild; } else if (curNode.data < value1 && curNode.data < value2 && curNode.rightChild.data != value1 && curNode.rightChild.data != value2) { curNode = curNode.rightChild; } else { return curNode.data; } } return -1; } 测试 ![在这里插入图片描述][e025ef8453ba4612bd4700f6b0816093.png_pic_center] public static void main(String[] args) { BinaryTree binaryTree = new BinaryTree(); LinkedList<Integer> nodes = new LinkedList<>(Arrays.asList(new Integer[]{ 10, 8, 3, 1, null, null, 5, null, null, 9, null, null, 12, 11, null, null, 20, null, null})); binaryTree.CreateBinaryTree(nodes); System.out.println(binaryTree.findLowestCommonAncestor(1, 9)); System.out.println(binaryTree.findLowestCommonAncestor(11, 12)); System.out.println(binaryTree.findLowestCommonAncestor(8, 10)); } 运行结果 ![在这里插入图片描述][0e4363bfd5114c35adcfd72ddf1702d9.png_pic_center] [92761e17e5034feba59e4204c4b59b87.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/05695bf9e19e44a8a7240884a43527eb.png [c2b2bd677a964c1d9bfd172844ae47a5.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/ab8e9365a02345ba886eaf726d76b29b.png [b1a01139442b4c5488983c544f89b533.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/c8eb7782bc28405983fa0304bad1462b.png [88ce74ef489942b5b51f4ed063128b6b.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/5c8cedf757f44377a9fb324834cd3dc5.png [e025ef8453ba4612bd4700f6b0816093.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/10c14944d0af4fdc8ec6bf3e618a1c4b.png [0e4363bfd5114c35adcfd72ddf1702d9.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/fb81604985d34e9785f1ae65771c3fe2.png
相关 【数据结构与算法之回溯法】案例 【数据结构与算法之回溯法】案例 文章目录 【数据结构与算法之回溯法】案例 1 四皇后问题 àì夳堔傛蜴生んèń/ 2024年03月25日 20:19/ 0 赞/ 53 阅读
相关 【数据结构与算法之动态规划】案例 【数据结构与算法之动态规划】案例 文章目录 【数据结构与算法之动态规划】案例 1 机器人的不同路径 谁借莪1个温暖的怀抱¢/ 2024年03月25日 19:16/ 0 赞/ 16 阅读
相关 【数据结构与算法之贪心算法】案例 【数据结构与算法之贪心算法】案例 文章目录 【数据结构与算法之贪心算法】案例 1 分薄饼问题 ゝ一纸荒年。/ 2024年03月25日 19:16/ 0 赞/ 54 阅读
相关 【数据结构与算法之递归算法】案例 【数据结构与算法之递归算法】案例 文章目录 【数据结构与算法之递归算法】案例 1 数组的全排列 秒速五厘米/ 2024年03月25日 19:16/ 0 赞/ 46 阅读
相关 【数据结构与算法之排序与查找】案例 【数据结构与算法之排序与查找】案例 文章目录 【数据结构与算法之排序与查找】案例 1 荷兰国旗问题 清疚/ 2024年03月25日 16:39/ 0 赞/ 42 阅读
相关 【数据结构与算法之图结构】案例 【数据结构与算法之图结构】案例 文章目录 【数据结构与算法之图结构】案例 1 迷宫问题 1 迷宫问题 如 超、凢脫俗/ 2024年03月25日 16:38/ 0 赞/ 51 阅读
相关 【数据结构与算法之树结构】案例 【数据结构与算法之树结构】案例 文章目录 【数据结构与算法之树结构】案例 1 计算二叉树的深度 女爷i/ 2024年03月25日 14:12/ 0 赞/ 60 阅读
相关 【数据结构与算法之树结构】创建二叉树 【数据结构与算法之树结构】创建二叉树 文章目录 【数据结构与算法之树结构】创建二叉树 利用二叉树遍历的思想,在遍历过程中生成二叉树的节点,进而建 柔情只为你懂/ 2024年03月25日 14:12/ 0 赞/ 47 阅读
相关 【数据结构与算法之树结构】二叉树 【数据结构与算法之树结构】二叉树 文章目录 【数据结构与算法之树结构】二叉树 1 二叉树的定义 小鱼儿/ 2024年03月25日 12:36/ 0 赞/ 50 阅读
相关 【数据结构与算法之树结构】树的基本概念 【数据结构与算法之树结构】树的基本概念 文章目录 【数据结构与算法之树结构】树的基本概念 1 树的定义 傷城~/ 2024年03月25日 12:36/ 0 赞/ 46 阅读
还没有评论,来说两句吧...