首页 文章

三元搜索树 - 迭代遍历

提问于
浏览 1277
0

我试图迭代地遍历 ternary search tree . 我试图使用与二进制搜索树相同的技术遍历它,保持一个堆栈, push 一个节点, pop 它和 push 它的子节点 .

这样,访问了所有节点,但我不知道如何跟踪树包含的字符串 .

我有一个遍历的递归代码:

public void traverse(TernaryTreeNode r, String str)
    {
        if (r != null)
        {
            traverse(r.left, str);

            str = str + r.data;
            if (r.isEnd)
                al.add(str);

            traverse(r.middle, str);
            str = str.substring(0, str.length() - 1);

            traverse(r.right, str);
        }
    }

我希望重写一个迭代实现 . 这是当前的代码:

public void iterativePreorder(TernaryTreeNode node) {

        // Base Case
        if (node == null) {
            return;
        }

        // Create an empty stack and push root to it
        Stack<TernaryTreeNode> nodeStack = new Stack<TernaryTreeNode>();
        nodeStack.push(root);
        String str = "";

        while (nodeStack.empty() == false) {

            // Pop the top item from stack and print it
            TernaryTreeNode mynode = nodeStack.peek();
            nodeStack.pop();
            str+= mynode.data;
            if(mynode.isEnd){
                al.add(str); //al is an ArrayList of strings
            }

            // Push right and left children of the popped node to stack
            if (mynode.right != null) {
                nodeStack.push(mynode.right);
            }

            if (mynode.middle != null) {
                nodeStack.push(mynode.middle);
            }
            else{
                str = "";
            }

            if (mynode.left != null) {
                nodeStack.push(mynode.left);
            }


        }

    }

基于 isEnd 属性,我能够知道当前节点是否表示字符串结束,因此我将 str 添加到arraylist . (isEnd可能是也可能不是叶子节点) . 但我无法使用 str 定义获取所有字符串的逻辑 .

这是TernaryTreeNode类:

public class TernaryTreeNode {

    char data;
    boolean isEnd;
    TernaryTreeNode left, middle, right;

    public TernaryTreeNode(char data){
        this.data = data;
        this.isEnd = false;
        this.left = this.middle = this.right = null;
    }
}

这是一个直观的例子:http://igoro.com/archive/efficient-auto-complete-with-a-ternary-search-tree/

1 回答

  • 1

    您可以考虑保留另一个 Stack 以跟踪父项中的字符串,或者使用与配对类相同的 Stack .

    class TernaryPair {
      TernaryTreeNode node;
      String fromParent;
    }
    

    根元素用空字符串放入堆栈 . 每当您将字符串推入堆栈时,您也会从父项中推送字符串 .

    TernaryPair mypair = nodeStack.pop();
    str+= mypair.fromParent + mypair.node.data;
    if(mypair.node.isEnd){
      al.add(str); //al is an ArrayList of strings
    }
    

    当推到堆栈时

    if (mypair.node.right != null) {
      TernaryPair newPair = new TernaryPair();
      newPair.node = mypair.node.right;
      newPair.fromParent = str;
      nodeStack.push(newPair);
    }
    

    PS: Stack pop() 方法将 remove and return 你在堆栈顶部的元素 . 一个电话就足够了 .

    TernaryTreeNode mynode = nodeStack.peek();
    nodeStack.pop();
    
    TernaryTreeNode mynode = nodeStack.pop();
    

相关问题