- 浏览: 601430 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
import java.util.*; public class BinaryTree { protected Node root; public BinaryTree(Node root) { this.root = root; } public Node getRoot() { return root; } /** 构造树 */ public static Node init() { Node a = new Node('A'); Node b = new Node('B', null, a); Node c = new Node('C'); Node d = new Node('D', b, c); Node i = new Node('I'); Node e = new Node('E',i,null); Node f = new Node('F', e, null); Node g = new Node('G', null, f); Node h = new Node('H', d, g); return h;// root } /** 访问节点 */ public static void visit(Node p) { System.out.print(p.getKey() + " "); } // 求二叉树的高度 static int height(Node tree) { if (tree == null) return 0; else { int leftTreeHeight = height(tree.getLeft()); int rightTreeHeight = height(tree.getRight());; return leftTreeHeight > rightTreeHeight ? leftTreeHeight + 1: rightTreeHeight + 1; } } // 求二叉树的结点总数 static int nodes(Node tree) { if (tree == null) return 0; else { int left = nodes(tree.getLeft()); int right = nodes(tree.getRight()); return left + right + 1; } } // 求二叉树叶子节点的总数 static int leaf(Node tree) { if (tree == null) return 0; else { int left = leaf(tree.getLeft()); int right = leaf(tree.getRight()); if (tree.getLeft() == null && tree.getRight() == null) return left + right + 1; else return left + right; } } //将二叉树所有结点的左右子树交换 static void swapTree(Node root){ if(root != null) { Node tmp = root.getLeft(); root.setLeft(root.getRight()); root.setRight(tmp); swapTree(root.getLeft()); swapTree(root.getRight()); } } /** * getLeafNodes: 递归求解给定二叉树的所有叶子结点 * @param root 给定二叉树的根结点 * @param leaflist 给定二叉树的所有叶子结点 */ static void getLeafNodes(Node root, List<Node> leaflist) { if (root != null) { if (root.getLeft() == null && root.getRight() == null) { leaflist.add(root); return ; } getLeafNodes(root.getLeft(), leaflist); getLeafNodes(root.getRight(), leaflist); } } /** * longestPath: 递归求解给定二叉树的一条最长路径 如果有多条,输出其中一条 * @param root 给定二叉树的根结点 * @param longestPath 存放二叉树的最长路径上的结点 */ static void longestPath(Node root, List<Node> longestPath) { if (root != null) { longestPath.add(root); if (root.getLeft() == null && root.getRight() == null) { // 左右子树均空 return ; } List<Node> leftLongestPath = new ArrayList<Node>(); List<Node> rightLongestPath = new ArrayList<Node>(); longestPath(root.getLeft(), leftLongestPath); longestPath(root.getRight(), rightLongestPath); if (leftLongestPath.size() >= rightLongestPath.size()) { longestPath.addAll(leftLongestPath); } else if (leftLongestPath.size() < rightLongestPath.size()) { longestPath.addAll(rightLongestPath); } } } /** * @param args */ public static void main(String[] args) { BinaryTree tree = new BinaryTree(init()); System.out.println("叶子结点数"); System.out.println(leaf(tree.getRoot())); System.out.println("总结点数"); System.out.println(nodes(tree.getRoot())); System.out.println("树的高度"); System.out.println(height(tree.getRoot())); System.out.println(); System.out.println("一条最长路径"); List<Node> l=new ArrayList<Node>(); longestPath(tree.getRoot(),l); for(int i=0;i<l.size();i++) System.out.println(l.get(i).getKey()); } } public class Node { private char key; private Node left, right; public Node(char key) { this(key, null, null); } public Node(char key, Node left, Node right) { this.key = key; this.left = left; this.right = right; } public char getKey() { return key; } public void setKey(char key) { this.key = key; } public Node getLeft() { return left; } public void setLeft(Node left) { this.left = left; } public Node getRight() { return right; } public void setRight(Node right) { this.right = right; } }
下载源码
- 45688424g.rar (1.5 KB)
- 下载次数: 2
发表评论
-
求二叉树上任意两个节点的最近公共父节点
2013-01-09 10:24 2394北大百练题2756: 如上图所示,由正整数1, 2 ... -
JAVA判断二叉树是否是二叉平衡树
2013-01-07 18:59 1986import java.util.*; ... -
大顶堆应用:POJ2010
2012-12-23 20:59 1897POJ2010题意: 奶牛学校招生,c头奶牛报名,要选 ... -
二维树状数组学习之二:练习POJ 1195
2012-12-12 21:40 1397接前文:二维树状数组学习之一:彻底理解http://128kj ... -
二维树状数组学习之一:彻底理解
2012-12-12 20:54 2468当要频繁的对数组元素进行修改,同时又要频繁的查询数组内 ... -
图的深搜+树状数组练习 POJ 3321(JAVA)
2012-12-11 11:13 1824关于树状数组:参看:http://128kj.iteye.co ... -
树状数组练习:POJ 3067
2012-12-09 17:10 1816关于树状数组,参看:http://128kj.iteye.co ... -
树状数组练习:POJ 2481(JAVA)
2012-12-08 18:11 1818关于树状数组,请参考:http://128kj.iteye.c ... -
初步了解树状数组
2012-12-07 14:18 1773一、树状数组是干什么的? 平常我们会遇到一些对数组进 ... -
线段树求逆序数(离散化)POJ 2299
2012-12-06 08:25 2100POJ2299题意: 给出长度为n的序列,每次只能交换 ... -
利用线段树求逆序数(JAVA)
2012-12-04 22:46 2576设A[1…n]是一个包含n个不同数的数组。如果在i< ... -
线段树入门学习(三)懒操作(兼解POJ1823) JAVA
2012-12-02 15:37 2120继续上文"线段树入门学习(二)" ht ... -
线段树入门学习(二)(兼解POJ3468) JAVA
2012-11-30 16:55 2544继续上文http://128kj.iteye. ... -
线段树入门学习(兼解HDU1754)
2012-11-30 11:24 2702先看网上的介绍: 线段树也叫区间树,顾名思义,线段树是 ... -
AVL树及JAVA实现
2012-11-26 16:34 2293一棵AVL树是其每个节点的左子树和右子树的高度最多差1的二 ... -
图解平衡二叉树
2012-11-26 11:34 2061形态匀称的二叉树 ... -
深度优先遍历字典树(统计单词出现的个数)
2012-11-23 22:18 2851例:给出一个字符文本,每行一个字符串,统计不同的字符串出现的百 ... -
学习使用字典树(JAVA)
2012-11-22 09:25 2134字典树 又称单词 ... -
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
2012-11-17 21:50 18707堆有最大堆和最小堆之分,最大堆就是每个节点的值都>= ... -
并查集入门精讲,实例2个(JAVA)
2012-10-30 14:47 4045一、什么是并查集 ...
相关推荐
这个问题可以通过动态规划或者深度优先搜索(DFS)来解决,对于非负权重的二叉树,可以采用两次深度优先搜索,一次求最大路径,一次求最小路径,两者相减即为最长路径。 在C++实现中,`bitree.cpp`很可能是包含上述...
选取其中较长的一条,更新该节点的最长路径长度。 4. **更新全局最长路径**:在BFS过程中,每次遇到非叶子节点时,将当前节点的最长路径与全局最长路径进行比较,如果当前路径更长,则更新全局最长路径。 5. **...
二叉树的直径指的是该二叉树上任意两个节点路径长度中最长的一条,其长度为这两个节点之间经过的边数。 可以使用深度优先搜索(DFS)来求解二叉树的直径。具体做法如下: 定义一个私有变量 diameter,用于存储当前...
这是因为每个非叶节点都会贡献两条边,而叶节点贡献一条边,但总边数比节点数少一个。 #### 结论 通过以上分析,我们不仅理解了如何求解二叉树中节点的最大距离这一问题,而且也看到了动态规划和深度优先搜索在...
在计算机科学中,二叉树是一种非常重要的数据结构,而求二叉树节点的最大距离是二叉树中一个经典的问题。问题的定义是这样的:在二叉树中,计算任意两个节点之间的最大路径长度,路径长度是指路径上的边数。解决这个...
在二叉树中,如果我们沿着一条路径从根节点到某个叶节点,将这条路径上所有节点的标签(也就是节点值)连接成一个字符串,如果这个字符串是回文,那么我们称这条路径为回文路径。 然而,“伪回文路径”不是严格的...
首先,我们要理解问题的背景:给定一棵二叉树,每个节点的值都是一个整数,我们需要找出这棵树中能形成最长连续序列的一条路径。这里的“连续序列”是指节点值构成的序列是连续的,比如1、2、3或5、6、7。我们的目标...
关键路径(Critical Path)是项目管理中一个重要的概念,它是指项目中从头到尾最长的一条路径,决定了项目的最短完成时间。在图中,关键路径可以视为任务之间的依赖关系,其中任何任务的延迟都会导致整个项目的延期...
7. **计算二叉树深度**:从根节点出发,沿着最长的路径到达最远的叶子节点,这条路径的长度就是二叉树的深度。可以通过递归算法实现,每次进入子树时增加深度,返回时减去1。 这些基本操作是理解和操作链式存储...
最长路径则是所有这些路径中最长的一条,这对于理解二叉树的结构和性质非常有用。 二叉树的表示法输出也是一项重要任务。括号表示法(或称前缀表示法)使用圆括号来表示子树,如`(A(B(C)(D))(E(F(G)(H)))`。凹入...
红黑树则是一种弱平衡的二叉查找树,它允许节点不平衡,但通过颜色属性(红色或黑色)来保证任何节点到每个叶子节点的最长路径不超过最短路径的两倍,同样保持高效的查找性能。 在Windows编程中实现平衡二叉树的...
- 求二叉树的直径:找到最长的路径,这条路径经过两个节点,但不经过根节点。 综上所述,二叉树是数据结构的重要组成部分,其丰富的性质和操作使其在多种场景下得到广泛应用。理解并熟练掌握二叉树的原理和算法,...
3. **路径查找**:能够准确地找到所有从叶子节点到根节点的路径,并输出其中最长的一条路径。 4. **二叉树表示**:使用括号表示法和凹入表示法正确地输出了二叉树的结构。 5. **资源管理**:实验最后能够释放分配给...
二叉树的直径是指树中任意两个节点之间最长路径的长度,这条路径可能经过也可能不经过根节点root。两节点之间路径的长度由它们之间边数表示。 在解决这道题时,我们需要注意到二叉树的直径有两种可能:一是左子树的...
题目要求计算一棵二叉树的直径,即树中任意两个节点之间的最长路径。这条路径可以经过根节点,也可以不经过。给定的输入格式包括一个整数n,表示树的节点数,以及n-1对整数x和y,表示x是y的父亲节点。在二叉树中,x...
数据结构二叉树实验报告 二叉树是一种常用的数据结构,在计算机科学和信息技术领域中广泛应用。...* 实验 7.3:输出所有的叶子节点、输出所有从叶子节点到根节点的路径、输出(2)中的第一条最长的路径。
树的深度是所有节点的路径中最长的一条,而高度则是根节点到最远叶子节点的距离: ```cpp int treeDepth(TreeNode* root) { if (!root) return 0; queue*> q; q.push(root); int depth = 0; while (!q.empty()...
题目描述输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。