---

1. successor 를 이용해서 recursive traversal 을 사용하지 않고도 트리의 모든 노드들을 탐색할 수 있게 하는 이진 탐색 트리! large scale tree 에서는 recursive call 이 시간이 많이 걸릴 수 있으므로, 이를 사용하는 것이 좋음(근데 왜..? 시간이 많이 걸리는..? → 아마 트리의 높이가 높으면, a 찾고 다시 처음부터 c 찾고 b 찾고 해야 하는데 시간 많이 걸리는데, successor 즉 그 다음에 올 애를 link 에 걸어두면 recursive 하게 안해도 바로 찾을 수 있으니까..? 그래서 효율적이라는 것 같음.)
2. 그래서 여기 예시에 보면 leaf node 그니까 맨 끝단의 노드의 경우 rlink 가 원래는 null 인데 null 대신 각각의 successor 를 저장해 둠. 단, E 즉 leaf node 중에서도 맨 마지막으로 탐색당해서 그 다음 방문할 노드가 없는 노드의 경우에는 successor 를 저장하지 않음. 근데 C,G,F 의 경우에는 successor 를 저장하고 싶어도, rlink 에 이미 값이 있어서 저장을 못 함. 그래서 on the fly 즉 재귀적으로 그때마다 구해야 함.(맞아..?)

1. threaded binary tree 에는 특별한 값이 하나 있음. 바로 is_thread. 노드 중에 leaf node 의 경우 rlink 에 successor 가 있는데, 이렇게 successor 를 저장하는 노드를 thread 라고 함. 그래서 thread 이면 true 를 저장하고, GCF 처럼 그냥 rlink child 를 저장하는 노드라면 is_thread 에 false 를 저장함. 그리고 모든 각각의 노드가 isThread 값을 가지고 있어야 하므로, 이는 노드 하나하나를 만드는 구조체에 data, right, left 와 함께 저장되어야 함. 그래서 나중에 트리 노드를 만들 때, 맨 마지막에 thread node 가 맞으면 1 을, 아니면 0을 넣어야 함. TreeNode n1 = {’A’(data), NULL(llink 주소), &n3(rlink 주소), 1(is_thread)};

1. 함수 중에 새롭게 추가되는 애 중에 find_successor 라는 게 있음. inorder 하게 탐색하는 과정에서 해당 노드의 successor 를 찾는 것임. 그래서 successor 를 찾고 싶은 트리 노드의 주소를 인자로 받은 다음, 인자로 받은 트리노드의 successor 에 해당하는 노드의 주소를 반환하는 함수를 짜면 됨.
2. 이때, 함수 내부에서 트리 노드 주소 저장하는 트리노드 포인터 q 선언하고, 그 값으로 p 즉 인자로 받은 트리노드 포인터의 right 를 저장함. 즉 오른쪽 자식을 저장함.
3. 그리고 나서 그 오른쪽 자식이 쓰레드이거나, 더 이상 successor 가 없는 leaf node 라면, successor 로 재귀 탐색 안하고 바로 그 오른쪽 자식 주소를 (q) 리턴하면 됨.
4. 근데 만약 leaf node 가 아니라면, 재귀 탐색을 통해서 successor 를 찾아줘야 함 (그니까 threaded binary. tree 가 재귀를 아예 안쓰는 게 아니라 leaf node 한해서 안써서 효율 좀 높여주는 거임.) 그래서 while 문 써서 현재 q 에는 인자로 받은 노드의 오른쪽 자식 트리노드의 주소가 저장되어 있고, inorder 에서successor 는 오른쪽 서브트리의 맨 왼쪽 자식이니까, q(인자의 오른쪽 자식)의 왼쪽 자식이 null 이 아닐 때까지만 while 문을 돌고, while 문 안에는 q에 q의 왼쪽 자식의 주소를 넣어주면 됨. 그리고 나서 while 문 다 끝나면 즉 q→left 가 null 인 상태가 되면, q를 반환해 주면 됨.

1. thread binary tree 를 inorder 한 방식으로 iterative 하게 traversal 하는 함수도 있음. in order traversal 은 왼쪽 자식부터 방문해야 하므로, leftmost 노드를 제일 먼저 찾아야 함. 그리고 나서 leftmost 노드의 값 출력한 뒤에는 find_successor 함수 이용해서, successor 의 값을 다음 탐색에 이용하면 됨.
2. 이를 위해, 우선 인자로는 트리노드의 루트 노드의 주소를 받아와야 함. 그 뒤에 맨 왼쪽으로 이동해야 하므로,트리노드 포인터 q 를 선언하고, 인자로 받은 뿌리 노드의 주소를 일단 넣음.
3. 그 뒤에 while 문에 q→left 가 널이 아닐때까지 도는 조건을 넣고(사실 q→left 만 넣어도 됨) q 에는 q의 left 를 저장하는 것을 반복함. 그래서 leftmostnode 에 도달함.
4. 그리고 나면, 다시 새로운 반복문을 돌아야 하는데, 돌기 전에 무조건 leftmostnode 를 프린트 해야 하니까, do wihle 로 쓰고 조건은 q가 널이 아닐때까지! 그 다음 printf 로 q의 데이터를 출력하고, q 에는 find_successor(leafnode 든 아니든 successor 찾아주게 아까 만들었음) 를 이용해서 찾은 successor 값을 저장해 줌.

1. 여기서 의문인게, 이미 TreeNode 만들면서 n1, n2, n4 dml right 에 successor 의 주소를 저장해 주었는데, main 에서 또 저장하는이유를 모르겟음. 저거 삭제해도 코드 잘 돌아가려나..?

1. Binary Search Tree 이진 탐색 트리는 search 하는 동작을 좀 더 쉽게 효율적으로 할 수 잇게 도와주는 자료구조임. 이게 어케 가능하냐면, 트리를 만들 적에 모든 왼쪽 서브트리의 키값은 root node 의 키값보다 작거나 같고, 모든 오른쪽 서브트리의 키값은 루트 노드의 키값보다 크거나 같게 만들면 됨. 이때 중요한 건 모든과 서브트리.! 즉 왼쪽 ≤ 중앙 ≤ 오른쪽이 모든 트리 노드에 대해서 보장되어 있다는 거!!