마지막 레벨 전까지 노드가 가득 채워져 있고, 마지막 레벨은 왼쪽부터 순차적으로 채워져 있는 트리
배열을 사용해 효율적인 표현이 가능
노드의 개수 : n < 2(h제곱) - 1
정 이진 트리 (Full binary tree)
모든 노드가 0개 또는 2개의 자식 노드만 갖는 트리
proper 또는 plane 이진 트리라고도 불림
노드의 개수 : n <= 2(h제곱) - 1
편향 이진 트리 (Skewed binary tree)
왼쪽 혹은 오른쪽으로 펴향되게 치우쳐 있는 트리
각각의 높이에 하나의 노드만 존재
노드의 개수 : h
균형 이진 트리 (Balance binary tree)
삽입/삭제가 이루어 질 때, 왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차를 1 이하로 맞추는 이진 타맥 트리
서브 트리 높이 차이가 항상 1 이하로 유지
균형 트리 종류 : AVL 트리, Red-Black 트리, B 트리, B+ 트리, B* 트리
3. 이진 트리 순회 (Binary Tree Traversal)
각각의 노드가 최대 두개의 자식 노드를 가지는 트리 자료 구조를 순회하는 방법
노드 추가 : BinaryTree._insertNode(), BinaryTree.insert()
전위 순회 : BinaryTree._preOrderTraverseNode(), BinaryTree.preOrderTraverse()
중위 순회 : BinaryTree._inOrderTraverseNode(), BinaryTree.inOrderTraverse()
후위 순회 : BinaryTree._postOrderTraverseNode(), BinaryTree.postOrderTraverseNode()
층별 순회 : BinaryTree.levelOrderTraverse()
_붙인 애들은 내부적으로 private 으로 쓰인다는 의미 (타언어에서 자주 사용되지만 js 는 해당 안된다) > 다른 메소드에서 호출되는 메소드
4. 이진 트리 구현하기
생성자, _insertNode(), insert()
// Node() : value와 left, right node 저장을 위한 생성자
function Node(value) {
this.value = value
this.left = null
this.right = null
}
// BinaryTree() : 시작 노드인 root 를 저장하기 위한 생성자
function BinaryTree() {
this.root = null
}
// _insertNode() : 재귀로 트리를 순회하며 노드 추가 (내부 사용)
BinaryTree.prototype._insertNode = function(node, value){
// 현재값과 비교
// 작으면 왼쪽, 크면 오른쪽
// 왼쪽, 오른쪽에 left, right pointer 비어있다면 추가할 노드를 연결
// 비어있지 않다면 하위 노드에서 다시 비교하도록 넘겨준다
if (node === null){
node = new Node(value)
} else if (value < node.value){
//🤔 재귀는 어려워...
node.left = this._insertNode(node.left, value)
} else if (value > node.value){
//🤔
node.right = this._insertNode(node.right, value)
}
return node
}
// insert() : 노드 추가
BinaryTree.prototype.insert = function(value){
this.root = this._insertNode(this.root, value)
}
let tree = new BinaryTree()
tree.insert("F")
tree.insert("B")
tree.insert("A")
tree.insert("D")
tree.insert("C")
tree.insert("E")
tree.insert("G")
tree.insert("I")
tree.insert("H")
console.log(tree)
// BinaryTree {
// root: Node {
// value: 'F',
// left: Node { value: 'B', left: [Node], right: [Node] },
// right: Node { value: 'G', left: null, right: [Node] }
// }
// }
전위 순회 구현
// _preOrderTraverse() : 재귀로 트리를 순회하며 전위 순회 (내부 사용)
BinaryTree.prototype._preOrderTraverse = function(node, callback){
if (node === null){
return
}
callback(node)
this._preOrderTraverse(node.left, callback)
this._preOrderTraverse(node.right, callback)
}
// preOrderTraverse() : 전위 순회하며 노드 출력
BinaryTree.prototype.preOrderTraverse = function(callback){
this._preOrderTraverse(this.root, callback)
}
let tree = new BinaryTree()
tree.insert("F")
tree.insert("B")
tree.insert("A")
tree.insert("D")
tree.insert("C")
tree.insert("E")
tree.insert("G")
tree.insert("I")
tree.insert("H")
// callback
function printNode(node){
process.stdout.write(`${node.value} -> `)
}
tree.preOrderTraverse(printNode)
console.log("end")
//F -> B -> A -> D -> C -> E -> G -> I -> H -> end
중위, 후위 순회 구현
// _inOrderTraverse() : 재귀로 트리를 순회하며 중위 순회 (내부 사용)
BinaryTree.prototype._inOrderTraverse = function(node, callback){
if (node === null){
return
}
this._inOrderTraverse(node.left, callback)
callback(node)
this._inOrderTraverse(node.right, callback)
}
// inOrderTraverse() : 중위 순회하며 노드 출력
BinaryTree.prototype.inOrderTraverse = function(callback){
this._inOrderTraverse(this.root, callback)
}
// _postOrderTraverse() : 재귀로 트리를 순회하며 후위 순회 (내부 사용)
BinaryTree.prototype._postOrderTraverse = function(node, callback){
if (node === null){
return
}
this._postOrderTraverse(node.left, callback)
this._postOrderTraverse(node.right, callback)
callback(node)
}
// postOrderTraverse() : 후위 순회하며 노드 출력
BinaryTree.prototype.postOrderTraverse = function(callback){
this._postOrderTraverse(this.root, callback)
}
let tree = new BinaryTree()
tree.insert("F")
tree.insert("B")
tree.insert("A")
tree.insert("D")
tree.insert("C")
tree.insert("E")
tree.insert("G")
tree.insert("I")
tree.insert("H")
// callback
function printNode(node){
process.stdout.write(`${node.value} -> `)
}
console.log("---------전위---------")
tree.preOrderTraverse(printNode)
console.log("end")
//F -> B -> A -> D -> C -> E -> G -> I -> H -> end
console.log("---------중위---------")
tree.inOrderTraverse(printNode)
console.log("end")
console.log("---------후위---------")
tree.postOrderTraverse(printNode)
console.log("end")
// ---------전위---------
// F -> B -> A -> D -> C -> E -> G -> I -> H -> end
// ---------중위---------
// A -> B -> C -> D -> E -> F -> G -> H -> I -> end
// ---------후위---------
// A -> C -> E -> D -> B -> H -> I -> G -> F -> end
층별 순회 구현하기
// Queue 객체 추가
function Queue(array) {
this.array = array ? array : [];
}
Queue.prototype.isEmpty = function () {
return this.array.length == 0;
};
Queue.prototype.enqueue = function (element) {
return this.array.push(element);
};
Queue.prototype.dequeue = function () {
return this.array.shift();
};
// levelOrderTraverse() : 층별 순회하며 노드 출력
BinaryTree.prototype.levelOrderTraverse = function (callback) {
let q = new Queue();
let node;
q.enqueue(this.root);
while (!q.isEmpty()) {
node = q.dequeue();
callback(node);
if (node.left !== null) q.enqueue(node.left);
if (node.right !== null) q.enqueue(node.right);
}
};
let tree = new BinaryTree();
tree.insert("F");
tree.insert("B");
tree.insert("A");
tree.insert("D");
tree.insert("C");
tree.insert("E");
tree.insert("G");
tree.insert("I");
tree.insert("H");
// callback
function printNode(node) {
process.stdout.write(`${node.value} -> `);
}
console.log("---------레벨---------");
tree.levelOrderTraverse(printNode);
console.log("end");
//---------레벨---------
//F -> B -> G -> A -> D -> I -> C -> E -> H -> end
