java - 三元搜索树 - 迭代遍历

Question

我正在尝试迭代地遍历三元搜索树。我正在尝试使用与二叉搜索树相同的技术遍历它，保留一个堆栈，push 一个节点，pop 它，然后 push它的 child 。

这样，所有节点都被访问了，但我不确定如何跟踪树包含的字符串。

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

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 添加到数组列表中。 (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/

Answer 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() 方法将移除并返回您堆栈顶部的元素。一个电话就够了。

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

-->

TernaryTreeNode mynode = nodeStack.pop();