QA 업무 중 자료 구조? ( level - 트리 순회 )

QA업무 중 TC(일명 : TestCase) 에 대한 구조를 짜는 도중

오랜만에 자료구조에 대해 고민하게 되었습니당... ㅎㅎ(사실 이런 고민거리 너무 좋은.. ㅎㅎ)

QA 업무 중 자료구조 ? 1탄

https://ipex.tistory.com/entry/QA-%EC%97%85%EB%AC%B4-%EC%A4%91-%EC%9E%90%EB%A3%8C-%EA%B5%AC%EC%A1%B0?category=666717

여기에 있는 TestCase 를 전체 순회 하는 작업을 하게 되었는데

일을 하다보니 정말 시간이 안나서 저녁먹고 7시쯤 됐나 이슈를 연구소에 다 전달하고 하니

시간이 붕 떠버렸습니다. 그래서 퇴근을 하려고했지만 해당 순회에대한 작업이 안되서 계속 신경이 쓰여버리는 바람에

시간을 내서 한번 level-순회에 대해서 조사를 해보고 실행해 보았습니다.

일단 구조는 전체 포스팅했지만 대강 이런 구조입니다.

장점이라 함은

특정위젯에 특정 카테고리에 있는 케이스를 가져올때 너무 편합니다.

예를들어

widget 에 setFocus API를 가져와야 한다.

obj.widget.api.setFocus

obj["widget"]["api"]["setFocus"]  두 방식다 사용할수 있기 때문이죠 되도록이면 

"전자"(obj.widget.api.setFocus) 의 방법을 사용하는게 좋다고 하네요!

하지만 문제 되는점은 특정 위치에서 전체 케이스를 가져올 때 입니다.

widget 에 api 를 전부 가져와야 한다!

모든 tc를 가져와야 한다.

결국은 특정 "Root"를 기준으로 Leaf Node 를 가져올수 있어야 한다는 의미가 됩니다.

다음 설명은 그림을 지나서 슈슉

자 이제 여기서 LeafNode(마지막 노드) 를 가져와야합니다. 마지막 노드! 여기서는 테스트케이스 겠네요

level - 순회 트리에서 중요한거는

(preOrder, postOrder, inOrder)전위순회,후위순회,중위순회 와는 다르게 "레벨" 별로 순회를 해야한다는 점입니다.

그렇기 때문에 등장하는 개념이 바로 큐(Queue) 입니다.

레벨 트리 순회는 위의 그림처럼 레벨별로 순회를 하여야 합니다.

A 레벨 순회 -> B레벨 순회 -> C레벨 순회 -> D레벨 순회

재귀형태로 도는 기본 순회랑은 조금 다르다고 볼수있습니다.

각 레벨별로 큐(Queue)를 두어서 해당 큐(Queue)에서 레벨을 관리 할수 있도록 하는 방법입니다.

그렇기 때문에 시나리오를 그려본다면

순회를 할 함수 ! 

리프노드인지 체크하는 함수 !

2개 정도가 필요할것 같구

순회 하는 함수에서는 처음으로 Root 노드를 파라미터로 받아 Child(자식) 값이 있을 경우 해당 내용을 큐에 넣고

큐는 다시 앞에서 부터 꺼내서 Child(자식)이 있으면 다시 그 자식들을  큐(Queue) 에 넣고 없다면 leafNode라는 배열에 

추가 해주는 방식을 사용하였습니다.

말로만 백날해봐야 백문의 불여일견이죠

코드로 보자면

1번 리프노드 체크

function isLeaf(node){

var leafKey = Object.keys(node);

var isLeaf = true;

var length = leafKey.length;

for(let i=0;i<length;i++){

if(typeof node[leafKey[i]]==='object'){

isLeaf = false;

}

}

return isLeaf;

}

생각보다 단순하죠  해당 노드의 내부 Value 들이(js Object는 key : value 로 구성됩니다.) 전부 object가 아니면 되는

케이스입니다. 사실 리프노드의 체크 유무는 원하는 상태에 따라 다를수 있기 때문에 저는 이번에 이런식으로

체크했다고 아시면 될 것 같습니다.

2번 루트 노드 순회 

function levelTree(obj){

var Queue=[];

var leafNode = [];

Queue.push(obj);

while(!__isEmpty(Queue)){

// dequeue

var root = Queue.shift();

console.log(root);

// 리프 노드가 맞다면

if(isLeaf(root)){

leafNode.push(root);

}

// 리프 노드가 아니라면 해당 자식들을 전부 큐에 추가

else{

let keyArr = Object.keys(root);

let length = keyArr.length;

for(let i=0;i<length;i++){

Queue.push(root[keyArr[i]]);

}

}

}

return leafNode;

}

사실 루트 노드 순회도 너무 별게 없다보니 이걸.. 적어야 하나 말아야 하나 고민했습니다.

순회 하기전에 Queue를 하나 만듭니다.

Q : [] 겠네요

그리고 바로 obj 를 추가합니다. 

만약 var obj = {

 "test":{},
"testb":{} 

}

이라면

Q : [obj] 가 되겠죵

그리고 while문을 돌리게 되는데 __isEmpty는 제가 따로 구현한 형태입니다. 비어있는지 아닌지만 판별해서 return 

while -> 간단하게 설명하면 Queue가 비어있으면 나가는 게 조건입니다. 

Queue생성후 push 를 해주었기 때문에 비어있지 않아 while 문으로 들어가게 됩니다.

그리고 Queue이기 때문에 js에서는 pop이 아닌 shift를 빼옵니다. 그래야 Queue의 FIFO 구조가 성립이 되기때문이죠

var obj = {

"widget":{

"api":{

"setFocus":{

"contents:":"setFocus쥬",

"tc":"WIDGET_API_SETFOCUS",

"result":"fail"

}

},

"event":{},

}

,

"widget2":{

"attr":{},

"event":{},

}

}

해당의 obj가 들어온다고 가정하고 그림을 그리면 Queue는 Q , Root는 현재 방문중인 노드로 R이라고하겠습니다.

while문 전에

Q [ obj ]

R  undefined

Q.shift 후

Q []   

R obj ("widget","widget2") 키값 2개 리프노드가 아님

Q에 추가

Q [ "widget", "widget2"]

R  -

Q.shift()

Q ["widget2"]

R  "widget"     ("api","event") 2개 있음  역시 리프노드가 아니기 때문에 push

Q에 추가 

Q ["widget2","api","event"]

R   - 

Q.shift()

Q ["api","event"]

R "widget2"   "attr","event" 2개를 가지고있으며 역시 리프노드가 아님 push

Q에 추가

Q ["api","event","attr","event"]

R

Q.shift()

Q ["event","attr",event"]

R "api"      "setFocus"를 가지고있음 리프노드가 아님

Q에 추가

Q ["event","attr","event","setFocus"]  

> 이후에 전부 하위 자식들을 추가하다가 setFocus를 만났을때

Q ["setFocus", .....] 에서 Q.shift()

Q [......] 

R "setFocus" 리프노드를 확인하면 내부값이 전부 string으로만되어있어 리프노드 true가 나타나게됨

leafNode.push(root);

체크가확인되면 리프노드에 추가

위의 방식으로 계속 순환후 함수에서는 leafNode를 return

** 실행 결과

테스트용이였지만 단순하게 {}로만 되어있는것들도 리프노드로 가져왔네요 문제 될건 아니지만 이런 경우도 나중에 다시

수정해야 할 부분이겠죠!

트리순회는 이만 마치도록 하겠습니당

전체 코드 (테스트용 코드이며 업무시에는 모듈 형태로 변환하여야 합니다.)

function __isEmpty(array){

return array.length===0 ? true : false;

}

function getShow(){

var leafArray = levelTree(obj);

console.warn(leafArray);

}

function levelTree(obj){

var Queue=[];

var leafNode = [];

Queue.push(obj);

while(!__isEmpty(Queue)){

var root = Queue.shift();

console.log(root);

if(isLeaf(root)){

leafNode.push(root);

}

else{

let keyArr = Object.keys(root);

let length = keyArr.length;

for(let i=0;i<length;i++){

Queue.push(root[keyArr[i]]);

}

}

}

return leafNode;

}

function isLeaf(node){

var isLeaf = true;

var leafKey = Object.keys(node);

var length = leafKey.length;

for(let i=0;i<length;i++){

if(typeof node[leafKey[i]]==='object'){

isLeaf = false;

}

}

return isLeaf;

}