- 浏览: 583771 次
- 来自: ...
文章分类
最新评论
-
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 2326北大百练题2756: 如上图所示,由正整数1, 2 ... -
JAVA判断二叉树是否是二叉平衡树
2013-01-07 18:59 1945import java.util.*; ... -
大顶堆应用:POJ2010
2012-12-23 20:59 1829POJ2010题意: 奶牛学校招生,c头奶牛报名,要选 ... -
二维树状数组学习之二:练习POJ 1195
2012-12-12 21:40 1353接前文:二维树状数组学习之一:彻底理解http://128kj ... -
二维树状数组学习之一:彻底理解
2012-12-12 20:54 2417当要频繁的对数组元素进行修改,同时又要频繁的查询数组内 ... -
图的深搜+树状数组练习 POJ 3321(JAVA)
2012-12-11 11:13 1765关于树状数组:参看:http://128kj.iteye.co ... -
树状数组练习:POJ 3067
2012-12-09 17:10 1672关于树状数组,参看:http://128kj.iteye.co ... -
树状数组练习:POJ 2481(JAVA)
2012-12-08 18:11 1746关于树状数组,请参考:http://128kj.iteye.c ... -
初步了解树状数组
2012-12-07 14:18 1699一、树状数组是干什么的? 平常我们会遇到一些对数组进 ... -
线段树求逆序数(离散化)POJ 2299
2012-12-06 08:25 2021POJ2299题意: 给出长度为n的序列,每次只能交换 ... -
利用线段树求逆序数(JAVA)
2012-12-04 22:46 2477设A[1…n]是一个包含n个不同数的数组。如果在i< ... -
线段树入门学习(三)懒操作(兼解POJ1823) JAVA
2012-12-02 15:37 2031继续上文"线段树入门学习(二)" ht ... -
线段树入门学习(二)(兼解POJ3468) JAVA
2012-11-30 16:55 2497继续上文http://128kj.iteye. ... -
线段树入门学习(兼解HDU1754)
2012-11-30 11:24 2600先看网上的介绍: 线段树也叫区间树,顾名思义,线段树是 ... -
AVL树及JAVA实现
2012-11-26 16:34 2215一棵AVL树是其每个节点的左子树和右子树的高度最多差1的二 ... -
图解平衡二叉树
2012-11-26 11:34 2009形态匀称的二叉树 ... -
深度优先遍历字典树(统计单词出现的个数)
2012-11-23 22:18 2784例:给出一个字符文本,每行一个字符串,统计不同的字符串出现的百 ... -
学习使用字典树(JAVA)
2012-11-22 09:25 2060字典树 又称单词 ... -
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
2012-11-17 21:50 18568堆有最大堆和最小堆之分,最大堆就是每个节点的值都>= ... -
并查集入门精讲,实例2个(JAVA)
2012-10-30 14:47 3985一、什么是并查集 ...
相关推荐
二叉树的前,中,后递归,非递归遍历,层次遍历,最长路径,采用C++实现,用了sTL的容器,附带测试样例,采用tree.exe 测试
二叉树的直径指的是该二叉树上任意两个节点路径长度中最长的一条,其长度为这两个节点之间经过的边数。 可以使用深度优先搜索(DFS)来求解二叉树的直径。具体做法如下: 定义一个私有变量 diameter,用于存储当前...
题目描述输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。
55.1 二叉树的深度题目描述从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。解题思路public int TreeD
编写一个C++程序,它能根据读入的某二叉树的中序序列和后序序列(两个英文字母串,每个串长不大于80,各占一行),构造该二叉树,并输出该二叉树的前序序列、叶的个数、二度结点个数及其从根节点开始的最长路径上...
从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。 解题思路一: ①如果一棵树只有一个节点,它的深度为1 ②如果根节点只有左子树而没有右子树,那么树的深度是左子树的...
从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。递归的时候无需判断左右子树是否存在,因为如果该节点为叶节点,它的左右子
从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。递归的时候无需判断左右子树是否存在,因为如果该节点为叶节点,它的左右子
30、 已知有向图G=,E>,试设计一算法以判断对于任意两点u和v,是否存在一条从u到v的路径,并分析其复杂度。 31、 对于给定的一个二叉树T(如下图) a) 设计一个算法,统计二叉树中结点总数; b) 设计一个算法,求...
从根节点到叶节点依次经过的节点(含根、叶节点)形成树的一条路径,最长路径的长度为树的深度。 例如: 给定二叉树 [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回它的最大深度 3 。 思路:递归 ...
向vector插入一条数据 Easy 观察规律 Hard 输出第一个不见的正整数 Medium 矩阵旋转90° Easy 最大子序列和 Medium 判断能否跳到最后 Easy vector East 爬楼梯 Easy 单链表节点删除 Easy 合并数组 Medium 二叉树中序...
4、用邻接矩阵或邻接图实现一个有向图的存储,并实现单源最短路径算法的实现(这个类的一个成员函数),并能输出该图的关键路径。 注:1、要用面向对象的方法设计代码; 2、一个图是一个类的实例; 3、类...
62条独特的路径中 64最小路径和中 66加一轻松 67添加二进制简单 70爬楼梯容易 72编辑距离困难 74搜索二维矩阵媒体 75种颜色中号 78个子集中 79字搜索媒体 81在旋转排序数组中搜索 II介质 88合并排序数组简单 96棵...
62条独特的路径 55 跳跃游戏 91种解码方式 63条独特的道路II 674 最长连续递增子序列 64 最小路径和 338 计数位 198 强盗 第213话 121个买卖股票的最佳时机 122 买卖股票的最佳时机 II 123 买卖股票的最佳时机 III ...
条推文计数51 N-Queens 572 另一棵树的子树98 验证二叉搜索树1048 最长的字符串链101 对称树第151话第177话218 天际线问题242 有效字谜378 排序矩阵中的第 K 个最小元素第489章 扫地机器人406按高度重构队列592 分数...
1.2.5. 在二元树中找出和为某一值的所有路径 .............................................. 22 1.2.6. Top K 算法详细解析---百度面试 ......................................................... 29 1.2.7. ...