그래프 이론 (이진트리의 구현과 순회방식)

이진트리는 데이터의 탐색속도 증진을 위해 사용하는 구종비니다.

이때 루트에서 자식노드로 접근하는 방법은 포인터를 이용하는 방식과 DFS를 이용하는 방식이 있습니다.

 

만약 완전이진트리가 아닌 자식노드가 하나씩 없는 이진트리라면 배열로 표현하기 어렵고, 탐색할 때도 불필요한 메모리가 사용됩니다.

 

 

이진 트리를 순회하는 방법은 크게 세가지 방법이 있다.

-전위순회 : 루트 → left → right

-중위순회 : left → 루트 → right

-후위순회 : left → right → 루트

 

포인터를 이용해서 완전이진트리가 아닌 구조에서도 안정적으로 작동할 수 있다.

JS에서는 클래스를 이용해야한다.

const preOrder=[];
const inOrder=[];
const postOrde=[];

//부모 자식 초기화
const node=function(num){
	this.num=num;
    this.left=null;
    this.right=null;
}
//루트 노드 초기화
const treeB =function(){
	this.root=null
}

//이진트리 값 생성
treeB.prototype.makeTree = function (left,num,right){
	const newT = new node(num)
    newT.left=left;
    newT.right=right;
    this.root=newT
}


//전위순회
treeB.prototype.preOrderFunc = function (Troot){
	if(Troot !=null){
    	prOrder.push(Troot.num);
       	this.preOrderFunc(Troot.left);
        this.preOrderFunc(Troot.right);
    }
}
//중위순회
treeB.prototype.inOrderFunc = function (tree){
	if(Troot !=null){
    	this.inOrderFunc(Troot.left);
    	inOrder.push(Troot.num);
        this.inOrderFunc(Troot.right);
    }
}
//후위순회
treeB.prototype.PostOrderFunc = function (tree){
	if(Troot !=null){
    	
       	this.postOrderFunc(Troot.left);
        this.postOrderFunc(Troot.right);
        postOrder.push(Troot.num);
    }
}


Function main(){
	//트리생성
	const tree=new treeB();
    const n7=tree.makeTree(null,"d",null);
    const n6=tree.makeTree(null,"c",null);
    const n5=tree.makeTree(null,"b",null);
    const n4=tree.makeTree(null,"a",null);
    const n3=tree.makeTree(n6,"/",n7);
    const n2=tree.makeTree(n4,"*",n5);
    const n1=tree.makeTree(n2,"-",n3);
    
    
    tree.preOrderFunc(n1);
    console.log(preOrder);
    tree.inOrderFunc(n1);
    console.log(inOrder);
    tree.postOrderFunc(n1);
    console.log(postOrder);
    
 }

 

 

DFS를 이용해서 이진트리를 탐색할 수 있다.

 

전위순회

let res = '';
 
function DFS(n) {
  if (n >= 8) return;
  res += n + '';
  DFS(n * 2);
  DFS(n * 2 + 1);
}
 
DFS(1);
console.log(res);

 

중위순회

let res = '';
 
function DFS(n) {
  if (n >= 8) return;
  DFS(n * 2);
  res += n + '';
  DFS(n * 2 + 1);
}
 
DFS(1);
console.log(res);

 

후위순회

let res = '';
 
function DFS(n) {
  if (n >= 8) return;
  DFS(n * 2);
  DFS(n * 2 + 1);
  res += n + '';
}
 
DFS(1);
console.log(res);

출처

https://blog.naver.com/ndb796/221233560789

19. 이진 트리의 구현과 순회(Traversal) 방식