0

我的问题是如何将此函数对转换为单个非递归调用？据我了解，任何递归调用都可能变成产生相同结果的迭代算法。

public void insert(Key key, Value value){
       root = insert(root, key, value);
       root.color = BLACK;
}
private Node insert(Node h, Key key, Value value) {

       /*1*/ if (h == null)      return new Node(key, value);

       /*2*/ if (isRed(h.left) && isRed(h.right)) colorFlip(h);

       /*3*/ int cmp = key.compareTo(h.key);
       /*4*/ if (cmp == 0) h.val = value;
       /*5*/ else if (cmp < 0) h.left = insert(h.left, key, value); 
       /*6*/ else              h.right = insert(h.right, key, value);

       /*7*/ if (isRed(h.right) && !isRed(h.left))     h = rotateLeft(h);
       /*8*/ if (isRed(h.left)  && isRed(h.left.left)) h = rotateRight(h);
             return h; 
  }

我看到第 2 行在将节点推入堆栈时对其进行评估。我还注意到在第 5 行和第 6 行中，一个节点被推送到用户定义的堆栈上。当我开始思考第 7 行和第 8 行将出现的位置以及如何弹出节点并将它们正确链接到左侧或正确的指针。

4

1 回答 1

0

我的直觉是，这样做“应该”会产生一些像这样的混乱......

public void insert(Key key, Value value) {

Stack<Node> nodeStack = new Stack<>();
Stack<Key> keyStack = new Stack<>();
Stack<Value> valStack = new Stack<>();

nodeStack.push(root);
keyStack.push(key);
valStack.push(value);

boolean done = false;

while(!done) {
   //here you cut-past the 3-parameter insert method...
   //BUT...
   //replace all uses have h, key, and value with stack.peek() calls
   //push new items to each stack everytime you call insert(Node n, Key k, Value v) (and do a continue)
   //pop items from each stack each time you leave insert
   //set done to true when the recurssion should end

         //you also MAY need some a Node var to hold the last returned value
}

 root.color = BLACK;
}

故事的寓意是……您需要用自己的一些堆栈替换软件堆栈。上面的大纲可能并不完美，但它是一个开始。

出于好奇，你问什么？

于 2013-03-27T21:53:55.003 回答