sweetdev

스택 없이 트리를 traverse 하는 방법이 있다고 한다. 각 노드에 parent field를 추가하면 된다는데...? 이렇게 하면 한 노드에서 루트 노드로 올라가고 다시 밑으로 내려올 수 있다고 한다. 또 다른 해결책은 이진트리를 쓰레드 이진 트리로 표현하면 된다고 한다. ???

이것도 이산수학에서 배운 내용이긴 한데, 기억이 가물가물하고 그때는 벼락치기 했으니까 다시 정리해볼게요!! Preorder Traversal Inorder Traversal Postorder Traversal 그리고 Levelorder Traversal 이케 세가지를 배울거라고 합니다 Preorder: 이름처럼, 자기 자신(root)-left-right Inorder: left-root-right Postorder: left-right-root 이렇게 생긴 바이너리 트리가 있다고 해 봅시다! 얘를 preorder, inorder, postorder로 traverse 해보아용 preorder: A-B-D-H-E-C-F-I-G-J-L-K inorder: D-H-B-E-A-I-F-C-L-J-G-K postor..

Array로 표현하기 이렇게 생긴 트리를 Array로 표현하려고 하면, 요런식으로 표현해서 넣는다고 한다! 왜 0번에는 아무것도 안넣었을까?? 나중에 쓰나!? 궁금하지만 역시 아직 모르니까 pass... Array[i]번째에 있는 Node는, 걔의 left child는 Array[2*i]에, right child는 Array[2*i + 1]에, Parent는 Array[(i/2)의 내림] 에 있다고 한다 i에 6을 넣어서 확인해보면, 6번째 칸에는 F가 있고 걔의 left child는 I, right child는 없음, parent는 C인데 과연 맞을까?! 12번째 칸 = I 13번째 칸 = 없음 3번째 칸 = C 다 맞다 ㅎㅎ Node로 표현하기 아까 그 그래프를 Node로 표현하면, Node 구조를 ..

안녕하세요 SweetDev입니다. 저는 지금 컴공 2학년 수업인 자료구조에서 트리를 배우는 중이라고 해서(사실 수업 잘 안가서 모름) 시험공부도 미리 할 겸 트리를 정리해보려고 합니다! 1. 정의 트리 : hierarchy구조의 데이터를 표현하기 위한 자료 구조 2. 트리를 표현하기 위해서 쓰는 단어들 Node Root Node Child Node , Children degree, fan out Sibling Ancestor Descendant Leaf node, Leaves, Non-Leaf Node Subtree Forest Path from node x to node y Level 0, 1, 2, ~ h-1 1, 2, 3, ~ h Height : max, level 이런 단어들을 배울 예정이라고 하..

[정의] forest는 n개의 disjoint tree의 집합이다 나무가 모이면 숲이 되듯, tree가 여러개 모이면 forest라고 부른다. forest는 tree의 개념과 매우 유사한데, 이는 '트리에서 루트를 제거하면 포리스트가 되기 때문'이라고 한다??? ㅇㅎㅇㅎ...원래 이렇게 생긴 거였구나... 다음 단원에서 'disjoint set'을 표현하기 위해서 forest를 사용할것이라고 한다. [forest를 binary tree로 변환하기] 1. forest에 있는 각 트리를 이진트리로 변환한다. 2. 변환된 모든 binary tree를 root node의 rightChild 필드를 통해 연결한다. 그러면... 요렇게 된다.(아직 그림 안넣음) 이 변환은 이렇게 정의할 수 있다고 한다. Tree1..