java计算二叉树的高度以及叶节点个数
java计算二叉树的高度以及叶节点个数
java实现二叉树的相关操作
package 二叉树有关;
import java.util.ArrayD
import java.util.Q
public class CreateTree {
* @param args
public static void main(String[] args) {
// TODO Auto-generated method stub
Node root = new Node();
root.data = 9;
Node temp01 = new Node();
temp01.data = 1;
root.left = temp01;
Node temp02 = new Node();
temp02.data = 3;
root.right = temp02;
Node temp03 = new Node();
temp03.data = 2;
root.left.left = temp03;
Node temp04 = new Node();
temp04.data = 4;
root.left.right = temp04;
Node temp05 = new Node();
temp05.data = 8;
root.right.left = temp05;
Node temp06 = new Node();
temp06.data = 6;
root.left.left.left = temp06;
Node temp07 = new Node();
temp07.data = 7;
root.left.left.right = temp07;
System.out.println(&--------先序遍历----------&);
SelectTree1(root);
System.out.println();
System.out.println(&---------中序遍历---------&);
SelectTree(root);
System.out.println();
System.out.println(&---------后序遍历---------&);
SelectTree2(root);
System.out.println();
System.out.println(&----------叶节点个数-----------&);
int i = leafNum(root);
System.out.println(i);
System.out.println(&----------层次遍历二叉树-----------------&);
levelOrder(root);
System.out.println();
int j = deep(root);
System.out.println(&---------高度---------&);
System.out.println(j);
// 中序遍历
public static void SelectTree(Node root) {
if (root == null)
SelectTree(root.left);
System.out.print(root.data + & &);
SelectTree(root.right);
// 先序遍历
public static void SelectTree1(Node root) {
if (root == null)
System.out.print(root.data + & &);
SelectTree1(root.left);
SelectTree1(root.right);
// 后序遍历
public static void SelectTree2(Node root) {
if (root == null)
SelectTree2(root.left);
SelectTree2(root.right);
System.out.print(root.data + & &);
public static int leafNum(Node node) {
if (node != null) {
if (node.left == null && node.right == null) {
return leafNum(node.left) + leafNum(node.right);
// 求二叉树的深度
public static int deep(Node node) {
int h1, h2;
if (node == null) {
h1 = deep(node.left);
h2 = deep(node.right);
return (h1 & h2) ? h2 + 1 : h1 + 1;
// 层次遍历
public static void levelOrder(Node node) {
if (node == null)
Queue&Node& queue = new ArrayDeque&Node&();
queue.add(node);
while (!queue.isEmpty()) {
Node temp = queue.poll();
System.out.print(temp.data);
if (temp.left != null)
queue.add(temp.left);
if (temp.right != null)
queue.add(temp.right);
class Node {
boolean visited =
int data = 0;
Node left =
Node right =
我的热门文章
即使是一小步也想与你分享昨天做了个二叉树的笔试题 大概十几分钟就做完了 但是有些疑惑 想到了一个新题 不知道有没有人能解 - V2EX
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
已注册用户请 &
昨天做了个二叉树的笔试题 大概十几分钟就做完了 但是有些疑惑 想到了一个新题 不知道有没有人能解
22:13:39 +08:00 · 3832 次点击
下面是笔试题目:
根据用户的输入的字母, 构建一个满二叉树, 然后打印出它的所有从根到叶子的路径.
(假设用户的输入字母的个数恰好满足构建一个满二叉树)
a b c d e f g后构建成下面的树
就是这样的一个满二叉树
然后输出 abc，abd，ace，acf
要求:
使用任意一种你熟悉的语言即可。
然后菜鸟我是这样做的
* Created by tangtang on 15/6/15.
*/
public class Tree {
public static void main(String[] args)
byte[] byteArray={'D','B','A','C','F','E','G'};
Node root=new Node();
for (byte b: byteArray)
root.insert(b);
root.traverseBiTree(&&);
class Node{
private byte value=-1;
private Node leftC
private Node rightC
public Node getLeftChild()
return leftC
public Node getRightChild()
return rightC
public byte getValue()
public void setLeftChild(Node leftChild)
this.leftChild=leftC
public void setRightChild(Node rightChild)
this.rightChild=rightC
public void setValue(byte value)
this.value=
* 遍历加打印
思路 让上一层都产生一个string
public void traverseBiTree(String str)
str+=(char)
if (leftChild==null&&rightChild==null) {
System.out.println(str);
if (leftChild!=null)
leftChild.traverseBiTree(str);
if (rightChild!=null)
rightChild.traverseBiTree(str);
public void insert(byte c)
if (value==-1) {
if (c&value)
if (rightChild==null)
rightChild=new Node();
rightChild.insert(c);
if (leftChild==null)
leftChild=new Node();
leftChild.insert(c);
用java写的 有点长
不过去掉set get方法也非常简洁了
在做的过程产生了这样一个问题
如果 试题问的 就是输入a b c d e f g 生成上边的那个满二叉树 要求下一层的孩子都大于上一层的孩子 并且 右孩子都大于左孩子
如何生成该 上面的那个满二叉树？
好好想想 这个问题还是很困难的
要求只能一个一个的插入 不可以先排序再生成二叉树
56 回复 &| &直到
22:16:33 +08:00
& & 22:33:02 +08:00 via Android
听说过平衡二叉树或者红黑树么？它们在插入过程当中通过自旋就能满足你说的要求。
& & 22:37:36 +08:00
@ 这位兄台 你实现一个看看 平衡二叉树 并不能满足需求
不信你做做看
& & 22:44:16 +08:00 via Android
& & 22:57:02 +08:00
@ 1.如果v是u的左孩子，则key[v] & key[u].
2.如果v是u的右孩子，则key[v] & key[u].
3.如果v是u的孩子，则priority[u] & priority[u].
这是树堆的特点 好像并不满足
& & 23:01:36 +08:00
@ 恩，果然不行。
树的底层使用数组表示，插入算法使用普通的数组插入，可以保证最后的树为符合条件的完全树。
不过整体算法复杂度为O(n^2)。
你有更好复杂度的算法没？
& & 23:03:49 +08:00 via Android
@ priority=key
& & 23:04:27 +08:00
@ 嗯 我并没有解出来 想的不错 但是一写发现还是有问题
& & 23:05:00 +08:00
#!/usr/bin/python
#如果你会用数组表示二叉树，就会知道这个问题有多简单
l = 'abcdefg'
for i in range(len(l)/2+1, len(l)+1):
__result = []
__while i:
____result.append(l[i-1])
____i /= 2
__result.reverse()
__print ''.join(result)
& & 23:09:18 +08:00
@ 你这个并不对 如果打乱abcdefg的顺序呢 比如插入 t c b d a f k呢
& & 23:10:22 +08:00
@ 你只要求是满二叉树啊，又没规定是怎么插入的
& & 23:11:21 +08:00
看看最后那段话
问题在最后
& & 23:17:26 +08:00
@ 谁去看最后啊，那不就是个小根堆啊
& & 23:19:25 +08:00
英雄所见略同：）
顺序插入的话，直接把元素放到末尾就好。
不过考虑如果数据为随机插入的话，整个算法就退化为有序数组的插入算法了。
整个过程还是O(log n^2)
& & 23:22:40 +08:00
不是堆，堆的性质只能保证parent的value比child小。
& & 23:23:43 +08:00 via Android
@ +1 不就是个小根堆嘛
& & 23:24:42 +08:00
@ 既然对于小根堆来说，左右孩子大小关系没有影响，你交换一下不就好了。。。
& & 23:25:58 +08:00 via Android
@ 二叉堆为什么有退化的问题。。不是严格O(nlogn)的吗。。
& & 23:29:09 +08:00
我觉得这个题目限制不严，比如说不能先排序，那如果之后的算法内比较再交换允许吗？一般的算法题，限制时间复杂度和空间复杂度，都是很明确的。
提供个思路：用一维数组表示满二叉树，你可以顺序把元素全填进去，然后快排调整
& & 23:29:17 +08:00 via Android
无法避免a的兄弟节点的孩子比a大的状况
& & 23:30:12 +08:00 via Android
不是，我的方案是使用有序数组。
& & 23:33:43 +08:00
再者，基于比较的排序算法已经证明了时间复杂度下界是O(nlogn）。你要的结果里面所有元素已经有序了，所以如果你的算法基于比较，也不可能超过这个下界。
& & 23:36:12 +08:00
@ 并不违反 「下一层的孩子都大于上一层的孩子 并且 右孩子都大于左孩子」吧，那有什么关系？
& & 23:37:08 +08:00
只交换是不行的，但再加上向下调整就行了
& & 23:40:46 +08:00
@ 为什么不行？首先小根堆保证了左右两个元素比父元素大，交换了依然满足这个条件啊。
& & 23:45:26 +08:00 via Android
说反了，应该是 无法避免a的兄弟节点的孩子比a小的状况
z
c d
c和d是b的孩子，但是比z小。
& & 23:46:28 +08:00
@ 就说一个简单的小根堆 1,5,2,6,7,3,4 （数组表示）
交换中间层元素5,2之后，会变成 1,2,5,6,7,3,4，不符合小根堆性质了
结论：已经调整完毕的小根堆，不可随意交换某两个孩子的位置。
& & 23:48:50 +08:00 via Android
有序的完全二叉树为一有序序列，在插入过程中插入位置之后的节点都需要向后移动，所以这个题目等同于求一个有序数组的插入算法…
这样应该没问题了。
& & 23:51:12 +08:00
@ 其实说不能先排序 是考虑到性能的问题 每次都要排序 会浪费极大的性能 其实这也不是真实中需要的算法了 只不过是在做题的过程中产生的思考罢了 看了楼上的 觉得还没有满意的答案 为什么没有人动手实现一下呢
想的永远回比做起来简单
& & 23:54:52 +08:00
其实这么做 把先排序换成了后排序 我在想有没有更好的办法
& & 00:03:31 +08:00 via Android
后排序会导致插入过程中树无法保持有序的条件，这个题目就退化为给一个数组排序了。
底层如果使用二叉树的话，需要维护每一个元素的“前驱”和“后继”，前驱和后继指value的前一个和后一个。
这样插入时需要遍历插入位置之后的元素，复杂度和数组的相同。
& & 00:05:35 +08:00
难道 「下一层的孩子都大于上一层的孩子」 这句话的意思是，大于上一层的所有节点？
& & 00:07:31 +08:00
@ 洗澡的时候想了想 这并没有什么卵用 排完序之后 还需要重新组织二叉树
还是违背题的
& & 00:08:58 +08:00 via Android
我是这样理解的。就是一颗有序的完全二叉树。
& & 00:09:35 +08:00
@ 亲 你觉得可行 可以写出来让大家学习学习
& & 00:09:54 +08:00 via Android
所以底层用数组就行了
& & 00:39:02 +08:00
1、如果这么理解，这个题目是有问题的。
既然第 n 层 全部大于 第 n-1 层，「右孩子都大于左孩子」没有任何意义，在同一层之间交换元素，没有任何影响和副作用。那么这个 「右孩子都大于左孩子」的要求，随便交换一下元素就可以了。
2、其次，这个问题不是完全排序的。
只要使用快速划分，让数组左边一半小于右边一半，然后对左边继续前面的过程。再加上1所诉的的交换元素，就可以建立起符合要求的树了。复杂度只有 O(n)
& & 08:41:56 +08:00
楼上的诸位说这么多只不过是纸上谈兵罢了 没有一个肯做出来用事实说话
& & 08:45:08 +08:00 via Android
n层大于n-1层（a）与右孩子大于左孩子（b）是两个独立的条件，写两个例子。
a成立b不成立：
a
c b
b成立a不成立：
b
a c
这两个条件共同约束下只能是有序序列。
& & 08:48:00 +08:00 via Android
对了，你说的2的“调整”如果满足a和b，就是一个快速排序。
& & 09:03:12 +08:00
@ 事实？你自己问题都说不清楚，让人家找事实？你写得出测试用例吗？
@ 不是的
a
b c
d e f g
成立
a
b c
e g d f
也成立
同层之间，只要 2n 和 2n+1 做个交换就能满足条件 b
& & 09:14:03 +08:00 via Android
@ 恩，不错，是这样
& & 09:17:43 +08:00
@ 所以只要层间排序，不需要层内排序。
如果一次解决就是做一半快速划分，如果插入就是层内做大根堆。
都是 O(n) 的
& & 09:38:18 +08:00 via Android
@ 堆的那个恐怕不行吧。怎么处理插入一个比该层元素都小的值？
& & 10:07:12 +08:00
@ 大根堆顶往下推，不然为什么是大根堆呢
& & 10:17:43 +08:00 via Android
这个题目根据描述很可能有歧义，我觉得楼主你在叫人写代码之前应该给出几个测试用例，这样别人才好着手去写
& & 12:03:59 +08:00
@ 哈哈 没有其他的意思 就是讨论学习
我并没有测试用例 确实有人理解的不太正确 嗯等晚上下班在写吧
& & 12:05:12 +08:00
我出题的意思是
感谢回复者
3 小时 0 分钟前
@ 事实？你自己问题都说不清楚，让人家找事实？你写得出测试用例吗？
这个不成立 右边的都要大于左边的 可能是我描述的不清楚
实在不好意思哈
& & 12:33:48 +08:00
@ 如果右边的都要大于左边，这棵树可以被证明是完全排序的，这个题目就更没意义了。
& & 14:43:42 +08:00
你要求的所谓树用数组来表示那就是有序数组嘛，要求可以快速随机访问插入那就是块状链表了，效率是sqrt(n)
& & 14:46:57 +08:00
@ 其实更像是杨辉三角 但是要求动态插入 而不是排好序再排列
& & 14:52:26 +08:00
Oops, 似乎弄错了，我把条件加强了。。
& & 15:02:59 +08:00
这样做如何：每一层对应一个大根堆，插入时二分查找到需要插入的层，O(lg lg n)，将其根剔除并插入元素，将其根插入下一层，每次执行O(lg n)，最多执行lg n次，效率O(lg^2 n)；总效率O(lg lg n + lg n * lg n) = O(lg^2 n)。如果用数组来存储堆，并且将所有数组头尾相接起来，可以以大数组来解释二叉树。
这样的话，总效率O(n lg^2 n)，缺点是插入时会破坏所有原有的父子关系。
& & 15:05:52 +08:00
Oops，又漏了。用大数组来解释时，会出现左儿子大于右儿子的情况，访问时交换它们修正就可以了
& & 15:07:48 +08:00
发现@ 已经给出正解了…默默匿了…
& & 15:10:45 +08:00
好吧，按@ 47楼的解释，那我的解答就是49楼提到的块状链表了……
洗洗睡了……
& & 22:16:33 +08:00
& · & 1514 人在线 & 最高记录 2430 & · &
创意工作者们的社区
World is powered by solitude
VERSION: 3.9.7.5 · 66ms · UTC 13:58 · PVG 21:58 · LAX 05:58 · JFK 08:58? Do have faith in what you're doing.java 二叉树的实现 - 若是人间 - ITeye技术网站
博客分类：
BinaryTree类：
package com.javaeye.
* @author nishiting
public class BinaryTree {
* 内部类实现结点类，可提高安全性
* @author nishiting
private static class Node {
Node(int newData) {
data = newD
* 创建一个空的二叉树
public BinaryTree() {
* 递归的插入数值
* @param data 要插入的数值
public void insert(int data) {
root = insert(root, data);
* 将数值插入到二叉树中，比当前结点小或等于当前结点的插在当前结点的左侧，比当前结点大的数插在当前结点的右侧，每次从根结点开始递归比较
* @param node 当前的结点，就是根结点，只是每次根结点的左右子孙更新
* @param data 要插入的数值
* @return 新排好的二叉树
private Node insert(Node node, int data) {
if (node == null) {
node = new Node(data);
if (data &= node.data) {
node.left = insert(node.left, data);
node.right = insert(node.right, data);
return (node);
* 将数值输入构建二叉树
* @param data 要输入的数值
public void buildTree(int[] data) {
for (int i = 0; i & data. i++) {
insert(data[i]);
* 递归打印出二叉树
public void printTree() {
printTree(root);
System.out.println();
* 从根结点开始遍历，从树的最高层叶子结点开始输出，从左至右
* @param node 当前的结点
private void printTree(Node node) {
if (node == null)
// left, node itself, right
printTree(node.left);
System.out.print(node.data + "
printTree(node.right);
package com.javaeye.
import junit.framework.TestC
public class BinaryTreeTest extends TestCase {
public void testBinaryTreeTest() {
BinaryTree biTree = new BinaryTree();
int[] data = { 2, 8, 7, 4 ,9,3,1,6,7,5};
biTree.buildTree(data);
biTree.printTree();
浏览 17355
浏览: 64310 次
来自: 上海
遍历顺序错了，应该是
if(node==null){
现在是int，如果是字符呢，比如：Comparable[] s ...
马克下，学习之
很棒[size=x-large][/size]