java - 将二叉树转换为没有重复的堆栈

Question

我有一个对象类型 InfoTree 的二叉树对象有 2 个属性 - 数字和字符，但有些字符可以重复。我的最终目标是找到具有最大数字的字符的对象并返回它的字符.为此，我有一个函数可以找到最大数并递归返回，但我仍然需要将数字与二叉树中的字符进行匹配，所以我想将树转换为仅包含字符但没有重复项的堆栈，这就是我的位置的问题。我的不同字符是:k、e、c、d，但我所做的是将堆栈更改为 [k、d、c] - 没有 e 并且基本上不起作用。

//input : The function gets a stack and a character
//output : The function returns true if the character given is in the stack
public static boolean isInStack(Stack<Character> s,char ch){
    while(!s.isEmpty()){
        if(s.pop()==ch)
            return true;
    }
    return false;
}

 //The function puts all different characters in a stack
public static void stack(BinTreeNode<InfoTree> t,Stack<Character> s){
    s.push(t.getValue().getTav());
    if(t!=null){
        if(t.getLeft()!=null&&t.getRight()!=null){
            if(!isInStack(s,t.getValue().getTav())){
                s.push(t.getValue().getTav());
            }
            stack(t.getLeft(),s);
            stack(t.getRight(),s);
        }
        else if(t.getLeft()!=null)
        {
            if(!isInStack(s,t.getValue().getTav())){
                s.push(t.getValue().getTav());
            }
            stack(t.getLeft(),s);
        }
        else if(t.getRight()!=null)
        {
            if(!isInStack(s,t.getValue().getTav())){
                s.push(t.getValue().getTav());
            }
            stack(t.getRight(),s);
        }
    }
}

树是:

//input : none
//output : The function builds  and returns a tree
public static BinTreeNode<InfoTree> buildtree(){
    BinTreeNode<InfoTree> t1=new BinTreeNode<InfoTree>(new BinTreeNode<InfoTree>(new InfoTree('k',1)),new InfoTree('k',3),new BinTreeNode<InfoTree>(new InfoTree('k',0)));
    t1.getLeft().setLeft(new BinTreeNode<InfoTree>(new InfoTree('k',0)));
    t1.getLeft().setRight(new BinTreeNode<InfoTree>(new InfoTree('k',0)));
    t1.getLeft().getRight().setLeft(new BinTreeNode<InfoTree>(new InfoTree('e',0)));
    t1.getLeft().getRight().getLeft().setRight(new BinTreeNode<InfoTree>(new InfoTree('d',0)));

    t1.getRight().setLeft(new BinTreeNode<InfoTree>(new InfoTree('c',1)));  
    t1.getRight().getLeft().setRight(new BinTreeNode<InfoTree>(new InfoTree('c',0)));
    return t1;
}

非常感谢您的帮助!

Answer 1

堆栈是一种收集集合的可怕数据结构。假设您有一个包含元素 A、B、C 的堆栈，其中 A 是堆栈的顶部，而在您的代码中您有另一个 C。您的代码将在弹出所有元素并返回 true 后停止元素在那里，但你的堆栈现在将有零个元素。那是结果树的最后一个节点吗？运行后你拥有 4 个元素中的 3 个是分享运气。

正确的数据结构应该是一个集合:

Set<Character> setA = new HashSet<Character>();
setA.add('a');
setA.add('a');
setA.add('b');
setA.add('b');
setA.contains('a'); // ==> true
Character[] result = setA.toArray(new Character[setA.size()]);

基本上你不需要检查你之前是否添加过它，因为它会处理它。最后，您将拥有独特的字符。