Computer >> 컴퓨터 >  >> 프로그램 작성 >> JavaScript

JavaScript에서 이진 트리 반전

<시간/>

다음과 같이 표현되는 이진 트리가 있다고 가정합니다. -

      4
   /    \
  2      7
 / \    / \
1 3     6  9

이 바이너리 트리의 루트를 가져와 반전시키는 JavaScript 함수를 작성해야 합니다.

위의 이진 트리의 반전된 버전은 다음과 같습니다. -

      4
      / \
    7    2
   / \ / \
   9 6 3 1

예시

이에 대한 코드는 -

// class for a single tree node
class Node{
   constructor(val){
      this.val = val;
      this.left = null;
      this.right = null;
   };
};
// class for binary tree
class BinaryTree{
   constructor(){
      // root of the binary tree
      this.root = null;
   };
   insert = (data) => {
      // creating a new node with data
      const newNode = new Node(data);
      // if root is null, then this node will be the root
      if(this.root === null){
         this.root = newNode;
      }else{
         // otherwise we find the correct position to insert this node
         this.insertData(this.root, newNode);
      };
   };
   insertData = (node, newNode) => {
      if(newNode.val < node.val){
         if(node.left === null){
            node.left = newNode;
         }else{
            this.insertData(node.left, newNode);
         }
      }else{
         if(node.right === null){
            node.right = newNode;
         }else{
            this.insertData(node.right, newNode);
         }
      }
   };
   // function to invert the binary tree
   invert = (node) => {
      if(node === null){
         return;
      };
      [node.left, node.right] = [node.right, node.left];
      this.invert(node.right);
      this.invert(node.left);
   }
   traverse = (node) => {
      if(node === null){
         return;
      };
      this.traverse(node.right);
      console.log(node.val);
      this.traverse(node.left);
   };
};
const Tree = new BinaryTree();
Tree.insert(2);
Tree.insert(7);
Tree.insert(4);
Tree.insert(1);
Tree.insert(9);
Tree.insert(3);
Tree.insert(6);
// original right to left traversal
Tree.traverse(Tree.root);
Tree.invert(Tree.root);
console.log('after inversion');
// traversal right to left after inversion
Tree.traverse(Tree.root);
뒤에 왼쪽

출력

콘솔의 출력은 -

9
7
6
4
3
2
1
after inversion
1
2
3
4
6
7
9