이진 트리

 

트리

 

 

노드 - 트리에서 각 위치, 차수 - 자식 노드의 개수, 리프 - 차수가 0인 노드

 

이진 트리는 모든 노드가 자식이 2개 이하로 구성되어 있다. 노드는 이중 연결 리스트 구조로 만들 수 있다.

 

 

끝 번호의 노드는 비어 있어야 한다

 

 

이진 탐색 트리

 

typedef struct{
	char word[20];
    char mean[200];
}element;

typedef struct treeNode{
	element key;
    struct treeNode* left;
    struct treeNode* right;
}treeNode;

treeNode* searchDic(treeNode* root, element key){
	treeNode* p;
    int compare;
    p = root;
    
    while(p != NULL){
        compare = strcmp(key.word, p->key.word);
        if(compare<0) p = p->left;
        else if(compare>0) p = p->right;
        else printf("%s",p->key.word); return p;
    }
    return p;
}

 

이진 트리 순회

 

# 전위 순회
def preorder(node):
    if node == None:
        return
    print(node.data, end = '->')
    preorder(node.left)
    preorder(node.right)
# 중위 순회    
def inorder(node):
    if node == None:
        return
    inorder(node.left)
    print(node.data, end = '->')
    inorder(node.right)
# 후위 순회    
def postorder(node):
    if node == None:
        return
    postorder(node.left)
    postorder(node.right)
    print(node.data, end = '->')