昨天做了个二叉树的笔试题 大概十几分钟就做完了 但是有些疑惑 想到了一个新题 不知道有没有人能解

[woai110120130]

下面是笔试题目: 根据用户的输入的字母, 构建一个满二叉树, 然后打印出它的所有从根到叶子的路径. (假设用户的输入字母的个数恰好满足构建一个满二叉树)
例如: 输入 a b c d e f g后构建成下面的树
a
b c
c d e f 就是这样的一个满二叉树

然后输出 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("");
}


static class Node{

private byte value=-1;

private Node leftChild;
private Node rightChild;

public Node getLeftChild()
{
return leftChild;
}

public Node getRightChild()
{
return rightChild;
}


public byte getValue()
{
return value;
}

public void setLeftChild(Node leftChild)
{
this.leftChild=leftChild;
}

public void setRightChild(Node rightChild)
{
this.rightChild=rightChild;
}

public void setValue(byte value)
{
this.value=value;
}


/**
* 遍历加打印 遍历路径
* 思路 让上一层都产生一个string
* @return
*/
public void traverseBiTree(String str)
{
str+=(char)value;
if (leftChild==null&&rightChild==null) {
System.out.println(str);
return;
}

if (leftChild!=null)
{
leftChild.traverseBiTree(str);
}

if (rightChild!=null)
{
rightChild.traverseBiTree(str);
}
}




public void insert(byte c)
{
if (value==-1) {
value = c;
return;
}

if (c>value)
{
if (rightChild==null)
rightChild=new Node();
rightChild.insert(c);
}else {
if (leftChild==null)
leftChild=new Node();
leftChild.insert(c);
}

}

}
}

用java写的 有点长 不过去掉set get方法也非常简洁了


在做的过程产生了这样一个问题
如果 试题问的 就是输入a b c d e f g 生成上边的那个满二叉树 要求下一层的孩子都大于上一层的孩子 并且 右孩子都大于左孩子 如何生成该 上面的那个满二叉树？ 好好想想 这个问题还是很困难的
要求只能一个一个的插入 不可以先排序再生成二叉树

[Heartwork]

听说过平衡二叉树或者红黑树么？它们在插入过程当中通过自旋就能满足你说的要求。

[woai110120130]

@Heartwork 这位兄台 你实现一个看看 平衡二叉树 并不能满足需求 不信你做做看

[yangff]

treap

[woai110120130]

@yangff 1.如果v是u的左孩子，则key[v] < key[u].
2.如果v是u的右孩子，则key[v] > key[u].
3.如果v是u的孩子，则priority[u] > priority[u]. 这是树堆的特点 好像并不满足

[Heartwork]

@Heartwork 恩，果然不行。

树的底层使用数组表示，插入算法使用普通的数组插入，可以保证最后的树为符合条件的完全树。

不过整体算法复杂度为O(n^2)。

你有更好复杂度的算法没？

[yangff]

@woai110120130 priority=key

[woai110120130]

@Heartwork 嗯 我并没有解出来 想的不错 但是一写发现还是有问题

[binux]

#!/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)

[woai110120130]

@binux 你这个并不对 如果打乱abcdefg的顺序呢 比如插入 t c b d a f k呢

[binux]

@woai110120130 你只要求是满二叉树啊，又没规定是怎么插入的

[woai110120130]

看看最后那段话 问题在最后

[binux]

@woai110120130 谁去看最后啊，那不就是个小根堆啊

[Heartwork]

@binux

英雄所见略同：）

顺序插入的话，直接把元素放到末尾就好。

不过考虑如果数据为随机插入的话，整个算法就退化为有序数组的插入算法了。

整个过程还是O(log n^2)

[Heartwork]

@binux

不是堆，堆的性质只能保证parent的value比child小。

[wodesuck]

@binux +1 不就是个小根堆嘛

[binux]

@Heartwork 既然对于小根堆来说，左右孩子大小关系没有影响，你交换一下不就好了。。。

[wodesuck]

@Heartwork 二叉堆为什么有退化的问题。。不是严格O(nlogn)的吗。。

[zwzmzd]

我觉得这个题目限制不严，比如说不能先排序，那如果之后的算法内比较再交换允许吗？一般的算法题，限制时间复杂度和空间复杂度，都是很明确的。

提供个思路：用一维数组表示满二叉树，你可以顺序把元素全填进去，然后快排调整

[Heartwork]

@binux
无法避免a的兄弟节点的孩子比a大的状况

[Heartwork]

@wodesuck
不是，我的方案是使用有序数组。