Учитывая Двоичное дерево поиска и два узла, n1 и n2, напишите функцию, которая находит расстояние между двумя узлами - PullRequest
Новая
       11

Учитывая Двоичное дерево поиска и два узла, n1 и n2, напишите функцию, которая находит расстояние между двумя узлами

0 голосов
/ 17 ноября 2018

Учитывая дерево бинарного поиска, мне нужно написать функцию, которая находит расстояние между 2 узлами.Я думаю, что я близок с этим, но он, кажется, не работает должным образом.Если я хочу искать расстояние между узлами, которые находятся на одной стороне дерева.Не уверен, как это исправить.Любые советы будут с благодарностью.Ниже приведен код, который у меня есть.Мой код в Javascript. 

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

function BinarySearchTree(value) { 
 this.root = null;
};

BinarySearchTree.prototype.push = function(val){
   var root = this.root;

   if(!root){
      this.root = new Node(val);
      return;
   }

   var currentNode = root;
   var newNode = new Node(val); 

   while(currentNode){
      if(val < currentNode.value){
          if(!currentNode.left){
             currentNode.left = newNode;
             break;
          }
          else{
             currentNode = currentNode.left;
        }
     }
     else{
         if(!currentNode.right){
            currentNode.right = newNode;
            break;
         }
         else{
            currentNode = currentNode.right;
         }
     }
  }

}

BinarySearchTree.prototype.levelOfNode = 
    function(root, key, level){
      if(root === null){
        return -1;
      }else if(root.value === key){
        return level;
      }
  let l = this.levelOfNode(root.left, key, level+1)
    if (l!== -1){
      return l;
    }
    return this.levelOfNode(root.right, key, level +1)
  }

BinarySearchTree.prototype.lca = function(root, n1, n2){
   if(!root) return;
   var val = root.value;
   if(n1<val && n2<val){
     return lca(root.left, n1, n2);
   }
   if(n1>val && n2>val){
     return lca(root.right, n1, n2);
  }
  return this.root;
}

BinarySearchTree.prototype.findDistance = function(root, n1, n2){
  let lcaValue = this.lca(root, n1, n2);

  let l1 = this.levelOfNode(lcaValue, n1, 0);
  let l2 = this.levelOfNode(lcaValue, n2, 0);

  return l1 + l2;

}

let tree = new BinarySearchTree();

tree.push(4);
tree.push(8);
tree.push(9);
tree.push(11);
tree.push(3);

tree.findDistance(4,8,11);

1 Ответ

0 голосов
/ 17 ноября 2018

Пока у вас есть дерево, которое выглядит как 

   4
3     8
         9
           11

Вы можете получить путь от root для каждой цели и 

[4, 8]
[4, 8, 9, 11]

устранить все общие узлы.Затем проверьте, является ли один массив путей пустым, и возьмите длину другого.

Если у вас есть два непустых массива, вы можете добавить длину обоих, например 

[4, 3]
[4, 8, 9]

после устранения общих узлов 

[3]
[8, 9]

Затем добавьте обе длины 

1 + 2 = 3
...