JS의 이진 트리 탐색에 대한 자세한 설명

이진 트리는 루트 노드, 왼쪽 하위 트리, 오른쪽 하위 트리로 구성됩니다. 왼쪽 하위 트리와 프렌드 하위 트리는 각각 이진 트리입니다.
이 글은 주로 JS에서 이진 트리 순회를 구현합니다.

이진 트리의 예

var tree = {
 value: 1,
 left: {
  value: 2,
  left: {
   value: 4
  }
 },
 right: {
  value: 3,
  left: {
   value: 5,
   left: {
    value: 7
   },
   right: {
    value: 8
   }
  },
  right: {
   value: 6
  }
 }
}

너비 우선 순회

폭 우선 순회는 이진 트리의 첫 번째 수준(루트 노드)에서 시작하여 동일한 수준에서 위에서 아래로 수준별로 순회하며 노드는 왼쪽에서 오른쪽으로 하나씩 방문됩니다.

구현:

배열을 사용하여 대기열을 시뮬레이션합니다. 먼저 루트 노드를 대기열에 넣습니다. 큐가 비어 있지 않으면 루프를 실행합니다. 큐에서 노드를 꺼내고 노드의 왼쪽 하위 트리가 비어 있지 않으면 노드의 오른쪽 하위 트리가 비어 있으면 노드의 왼쪽 하위 트리를 큐에 넣습니다. 비어 있지 않으면 노드의 오른쪽 하위 트리를 대기열에 넣습니다.
(설명이 좀 불분명합니다. 코드만 보시면 됩니다.)

var levelOrderTraversal = function(node) { 
 if(!node) {  
  throw new Error('Empty Tree')
 } 
 var que = []
 que.push(node) 
 while(que.length !== 0) {
  node = que.shift()  
  console.log(node.value)  
  if(node.left) que.push(node.left)  
  if(node.right) que.push(node.right)
 }
}

재귀 순회

느낌이 듭니다. 이러한 문자를 사용하여 재귀 순회를 표현하는 세 가지 좋은 방법이 있습니다.
D: 루트 노드 방문, L: 루트 노드의 왼쪽 하위 트리 순회, R: 루트 노드의 오른쪽 하위 트리 순회.
선주문 순회: DLR
순순 순회: LDR
후순 순회: LRD
문자의 의미에 따라, 순회입니다^ ^

이 세 가지 유형의 순회는 모두 재귀 순회 또는 깊이 우선 검색(DFS)입니다. 왜냐하면 항상
더 깊은 곳에 먼저 액세스하기 때문입니다.

선순 순회를 위한 재귀 알고리즘:

var preOrder = function (node) { 
 if (node) {  
  console.log(node.value);
  preOrder(node.left);
  preOrder(node.right);
 }
}

순순 순회를 위한 재귀 알고리즘:

var inOrder = function (node) { 
 if (node) {
  inOrder(node.left);  
  console.log(node.value);
  inOrder(node.right);
 }
}

후순 순회를 위한 재귀 알고리즘:

var postOrder = function (node) { 
 if (node) {
  postOrder(node.left);
  postOrder(node.right);  
  console.log(node.value);
 }
}

비재귀적 깊이 우선 순회

사실 이 개념이 누구의 것인지 잘 모르겠습니다. 일부 책에서는 이진 트리 순회에 대한 위의 세 가지 재귀 순회에 대해서만 설명합니다. 일부는 너비 우선 순회와 깊이 우선 순회라는 두 가지 유형으로 나뉘며, 재귀 순회는 깊이 순회로 구분되며, 일부는 재귀 순회와 비재귀 순회라는 두 가지 유형으로 구분됩니다. 그리고 다음 순회. 개인적으로 방법과 사용법만 익히면 어떻게 나누든 문제가 되지 않는다고 생각합니다. :)

방금 너비 우선 순회에서 사용한 것은 이에 상응하여 이 비-우선 탐색에서 대기열입니다. 재귀적 깊이 우선 순회에서는 스택을 사용합니다. JS에서 시뮬레이션하려면 여전히 배열을 사용하세요.
여기에서는 선주문에 대해서만 이야기합니다.
음, 이 알고리즘을 설명하려고 했지만 명확하지 않았습니다. 코드를 따라가면 이해하실 수 있습니다.

var preOrderUnRecur = function(node) { 
 if(!node) {  
  throw new Error('Empty Tree')
 } 
 var stack = []
 stack.push(node) 
 while(stack.length !== 0) {
  node = stack.pop()  
  console.log(node.value)  
  if(node.right) stack.push(node.right)  
  if(node.left) stack.push(node.left)
 }
}

이 글을 읽다가 비재귀적 후순 알고리즘을 찾았으니 여기서는 비재귀적 순회 방법을 완성하겠습니다.

비재귀적 순서

먼저 숫자의 왼쪽 노드를 스택에 밀어넣었다가 꺼낸 다음 오른쪽 노드를 밀어넣습니다.

var inOrderUnRecur = function(node) { 
 if(!node) {  
  throw new Error('Empty Tree')
 } 
 var stack = [] 
 while(stack.length !== 0 || node) {  
  if(node) {
   stack.push(node)
   node = node.left
  } else {
   node = stack.pop()   
   console.log(node.value)
   node = node.right
  }
 }
}

비재귀적 후순(스택 사용)

여기서 임시 변수를 사용하여 마지막 푸시를 기록합니다/ 팝 노드. 아이디어는 먼저 루트 노드와 왼쪽 트리를 스택에 푸시한 다음 왼쪽 트리를 꺼낸 다음 오른쪽 트리로 푸시하고 제거하고 마지막으로 다음 노드를 가져오는 것입니다.

var posOrderUnRecur = function(node) { 
 if(!node) {  
  throw new Error('Empty Tree')
 } 
 var stack = []
 stack.push(node) 
 var tmp = null
 while(stack.length !== 0) {
  tmp = stack[stack.length - 1]  
  if(tmp.left && node !== tmp.left && node !== tmp.right) {
   stack.push(tmp.left)
  } else if(tmp.right && node !== tmp.right) {
   stack.push(tmp.right)
  } else {   
   console.log(stack.pop().value)
   node = tmp
  }
 }
}

비재귀적 사후 순서(두 개의 스택 사용)

이 알고리즘의 아이디어는 다음과 유사합니다. 위의 s1은 임시 변수와 약간 비슷합니다.

var posOrderUnRecur = function(node) { 
 if(node) {  
  var s1 = []  
  var s2 = []
  s1.push(node)  
  while(s1.length !== 0) {
   node = s1.pop()
   s2.push(node)   
   if(node.left) {
    s1.push(node.left)
   }   
   if(node.right) {
    s1.push(node.right)
   }
  }  
  while(s2.length !== 0) {   
   console.log(s2.pop().value);
  }
 }
}

Morris 순회

이 방법은 재귀나 스택 없이 세 가지 깊이 순회를 구현하며 공간 복잡도는 O(1)( 이 개념은 잘 모르겠습니다.)
(이 세 가지 알고리즘은 따로 시간이 나면 따로 공부하겠습니다.)

Morris order:

var morrisPre = function(head) { 
 if(!head) {  
  return
 } 
 var cur1 = head,
   cur2 = null
 while(cur1) {
  cur2 = cur1.left  
  if(cur2) {   
   while(cur2.right && cur2.right != cur1) {
    cur2 = cur2.right
   }   
   if(!cur2.right) {
    cur2.right = cur1    
    console.log(cur1.value)
    cur1 = cur1.left    
    continue
   } else {
    cur2.right = null
   }
  } else {   
    console.log(cur1.value)
  }
  cur1 = cur1.right
 }
}

모리스 중주문 :

var morrisIn = function(head) { 
 if(!head) {  
  return
 } 
 var cur1 = head,
   cur2 = null
 while(cur1) {
  cur2 = cur1.left  
  if(cur2) {   
   while(cur2.right && cur2.right !== cur1) {
    cur2 = cur2.right
   }   
   if(!cur2.right) {
    cur2.right = cur1
    cur1 = cur1.left    
    continue
   } else {
    cur2.right = null
   }
  }  
  console.log(cur1.value)
  cur1 = cur1.right
 }
}

모리스 후주문 :

var morrisPost = function(head) { 
 if(!head) {  
  return
 } 
 var cur1 = head,
   cur2 = null
 while(cur1) {
  cur2 = cur1.left  
  if(cur2) {   
   while(cur2.right && cur2.right !== cur1) {
    cur2 = cur2.right
   }   
   if(!cur2.right) {
    cur2.right = cur1
    cur1 = cur1.left    
    continue
   } else {
    cur2.right = null
    printEdge(cur1.left)
   }
  }
  cur1 = cur1.right
 }
 printEdge(head)
}
var printEdge = function(head) {

그렇습니다 이 기사의 전체 내용이 모든 사람의 학습에 도움이 되기를 바랍니다. 더 많은 관련 튜토리얼을 보려면 JavaScript 비디오 튜토리얼을 방문하세요!