자료구조 :: 트리(3) 쓰레드 이진트리

# 쓰레드 이진트리

ThreadTree.cpp

NULL 링크를 낭비하지 않고 순환호출 없이도 트리의 노드들을 순회 할 수 있도록 중위 순회시에
선행노드인 중위 선행자나 중위 순회시 후속 노드인 중위 후속자를 저장시켜 놓은 트리이다.

중위 후속자만 저장되어 있는 쓰레드 이진트리

#include <stdio.h> 
#defineTRUE1
#defineFALSE0

typedefstruct TreeNode { 
int data; 
struct TreeNode *left, *right; 
int is_thread;     
} TreeNode; 


//             G
//         C         F
//    A       B   D     E
TreeNode n1={'A',  NULL, NULL, 1}; 
TreeNode n2={'B',  NULL,  NULL, 1}; 
TreeNode n3={'C',  &n1,  &n2, 0}; 
TreeNode n4={'D', NULL, NULL, 1}; 
TreeNode n5={'E', NULL, NULL, 0}; 
TreeNode n6={'F', &n4,  &n5, 0}; 
TreeNode n7={'G', &n3,  &n6, 0}; 
TreeNode *exp= &n7; 

//
TreeNode *find_thread_successor(TreeNode *p) 
{ 
    TreeNode *q = p->right; 
if( q==NULL || p->is_thread == TRUE) 
return q; 
while( q->left != NULL ) q = q->left; 
return q; 
} 
void thread_inorder(TreeNode *t) 
{ 
    TreeNode *q; 
    q=t; 
while (q->left) q = q->left; 
do
    { 
        printf("%c ", q->data); 
        q = find_thread_successor(q); 
    } while(q); 
} 
int main() 
{ 
    n1.right= &n3; 
    n2.right= &n7; 
    n4.right= &n6; 
    thread_inorder(exp); 
}