Javascript：將二進制搜索樹轉換爲雙向鏈接列表的算法

Question

我正在嘗試編寫將BST轉換爲雙向鏈接列表的算法。這是我迄今爲止所擁有的。下面是代碼：

function TreeNode(val) { 
 
    this.val = val; 
 
    this.left = this.right = null; 
 
} 
 

 
function BinaryTree() { 
 
    this.root = null; 
 
} 
 
    
 
BinaryTree.prototype.push = function(val) { 
 
    var root = this.root; 
 
    
 
    if(!root) { 
 
     this.root = new TreeNode(val); 
 
     return; 
 
    } 
 
    
 
    var currentNode = root; 
 
    var newNode = new TreeNode(val); 
 
    
 
    while(currentNode) { 
 
     if (val < currentNode.val) { 
 
     \t if(!currentNode.left) { 
 
      currentNode.left = newNode; 
 
      break; 
 
      } else { 
 
       currentNode = currentNode.left; 
 
      } 
 
     } else if(val > currentNode.val) { 
 
     \t if(!currentNode.right) { 
 
      currentNode.right = newNode; 
 
      break; 
 
      } else { 
 
       currentNode = currentNode.right; 
 
      } 
 
     } 
 
    } 
 
} 
 
var bt = new BinaryTree(); 
 
bt.push(4); 
 
bt.push(2); 
 
bt.push(5); 
 
bt.push(1); 
 
bt.push(3); 
 
//console.log(bt); 
 
//var node = bt.root; 
 
function Node(node) { 
 
    //this.data = value; 
 
    //this.previous = this.next = null; 
 
    var head = null; 
 
    var tail = null; 
 
    var prev = null; 
 
    console.log(bstToLL(node, head, prev, tail)); 
 
} 
 

 

 
//function DoublyLinkedList() { 
 
// this.head = null; 
 
// this.prev = null; 
 
// this.tail = null; 
 
//} 
 

 
function bstToLL(node, head, prev, tail) { 
 
\t if (node === null) { 
 
    \t return; 
 
    } 
 
    
 
    bstToLL(node.left, head, prev, tail); 
 
    if (head === null) { 
 
    \t head = node; 
 
    //console.log(head) 
 
    } 
 
    if (prev === null) { 
 
    \t prev = node; 
 
    //console.log(prev) 
 
    } else { 
 
    \t //console.log(node); 
 
    //console.log(prev); 
 
    node.left = prev; 
 
    prev.right = node; 
 
    } 
 
    prev = node 
 
    bstToLL(node.right, head, prev, tail); 
 
    if(node.right === null) { 
 
    \t tail = node; 
 
    } 
 
    return head; 
 
} 
 

 
Node(bt.root);

代碼工作，但我不認爲這是獲得正確的結果。二進制樹看起來喜歡 -

4 
/\ 
    2 5 
/\ 
1 3 

當我從bstToLL（）方法返回的頭，我與VAL 4指向一個目標是右孩子5和左子2等等等等。

如果您運行代碼，並檢查調試器，您將看到頭對象。

有人可以請指導我，如果我這樣做是正確的方式，以及如何解決結果？

Answer 1

這是一些將二叉樹轉換爲LinkedList的代碼。它將記錄1，2，3，4和5，依次是：

function TreeNode(left, value, right) { 
    this.left = left; 
    this.value = value; 
    this.right = right; 
} 

function ListNode(prev, value, next) { 
    this.prev = prev; 
    this.value = value; 
    this.next = next; 
} 

function LinkedList(head, tail) { 
    if (tail === undefined) tail = head; 
    this.head = head; 
    this.tail = tail; 
} 
LinkedList.prototype.addToStart = function(list) { 
    this.head.prev = list.tail; 
    list.tail.next = this.head; 
    this.head = list.head; 
} 
LinkedList.prototype.addToEnd = function(list) { 
    this.tail.next = list.head; 
    list.head.prev = this.tail; 
    this.tail = list.tail; 
}; 

function bstToLL(tree) { 
    var centerNode = new ListNode(null, tree.value, null); 
    var list = new LinkedList(centerNode); 
    if (tree.left) list.addToStart(bstToLL(tree.left)); 
    if (tree.right) list.addToEnd(bstToLL(tree.right)); 
    return list; 
} 

var tree = new TreeNode(
    new TreeNode(
    new TreeNode(null, 1, null), 
    2, 
    new TreeNode(null, 3, null) 
), 
    4, 
    new TreeNode(null, 5, null) 
); 
var linkedList = bstToLL(tree); 
for (var node = linkedList.head; node; node = node.next) console.log(node.value);