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(), я получаю объект с Вэл 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);