二叉樹とその基本操作

39166 ワード

データ構造

スタックの基本的な操作については、「データ構造のスタックの基本的な操作」「キューに関する基本的な操作」を参照してください.
概念
一本の二叉の木は、結点の限定的な集合であり、集合または空であり、または一本のノードに二つの木を加えて、左の子樹と右の子樹と呼ばれる二叉の木からなる.
二叉樹の特徴:

各結点には最大2つのサブツリーがあります.すなわち、二叉樹の存在度が2より大きい結点

は存在しません.

二叉樹の子木には左右の区別があり、その子樹の順序は逆にしてはいけない.
満二叉木:一本の二叉樹において、すべての分岐点が左の子樹と右の子樹にあり、すべての葉ノードが同じ層において完全に二叉の木を有している場合:N個の結点を有する二叉樹の構造は、満二叉樹の前のN個の結点の構造と同じであり、完全二叉樹と呼ばれている.
性質

ルートノードの層数が1であると規定されている場合、1本の非空二叉樹のi番目の層には最大2^(i-1)(i>0)個の結点

がある.

ルートノードのみの二叉樹の深さが1であると規定されると、Kの深さの二叉樹の最大の接合点数は2^k-1(k>=0)

である.

は、任意の二叉樹に対して、葉の結点個数がn 0である場合、度が2の非葉結点個数がn 2である場合、n 0＝n 2＋1

がある.

n個の結点を有する完全な二叉樹の深さkは、log(n＋1)上の整数

である.

は、n個の結点を有する完全な二叉樹について、すべてのノードが上から下までの順に0から始まると、シーケンス番号iの結点について有する.

若i>0、両親番号:(i-1)/2;i=0,iはルートノード番号で、無双親ノード

もし2 i＋1＜nなら、左の子供番号:2 i＋1、さもなければ左の子供がいない

もし2 i+2

保存
二叉樹は主に順序記憶とチェーン記憶構造の順記憶構造があります.完全な二叉樹のすべての結点については、順に一番下にあり、同じ層が左から右に順番に番号を付けると、一つのノードの順番配列の利点が得られます.完全な二叉樹を記憶し、簡単な省間欠点:一般的な二叉樹、特にシングルツリーを保存し、記憶空間の利用が高くないです.
基本操作

二叉樹のエルゴード(先序、中序、後序、順)

は、先に巡回した結果に基づいて、二叉樹を作成します.

は、二叉樹を破壊する

クローン二叉樹

本の木の結点の個数を求めます.

本の木の葉の結点の個数を求めます.

本の木の第K層の結点の個数の

を求めます.

二叉樹の高さを求める

は、結点が一本の二叉樹の中にあるかどうかを判断する

結点の左の子供の結点

を取得します.

結点の右子供の結点

を取得します.

結点の両親を獲得して

を結びます.

非再帰的に二叉樹を巡回した(先序、中序、後序)

二叉樹の鏡像を求めます.

は、一本の二叉の木が完全な二叉の木であるかどうかを判断します.
①bin_tree.h

#pragma once

#include 
#include 
#include 

typedef char TreeNodeType;

typedef struct TreeNode{
    TreeNodeType data;
    struct TreeNode* lchild;
    struct TreeNode* rchild;
}TreeNode;

void TreeInit(TreeNode** root);

void PreOrder(TreeNode* root);      //    

void InOrder(TreeNode* root);       //    

void PostOrder(TreeNode* root);     //    

void LevelOrder(TreeNode* root);    //    

TreeNode* TreeCreate(TreeNodeType array[], size_t size, TreeNodeType null_node);     //             

void TreeDestroy(TreeNode** root);  //     

TreeNode* TreeClone(TreeNode* root);    //     

size_t TreeSize(TreeNode* root);    //      

size_t TreeLeafSize(TreeNode* root);    //        

size_t TreeKLevelSize(TreeNode* root, int K);   //    K    

size_t TreeHeight(TreeNode* root);        //    

TreeNode* TreeFind(TreeNode* root, TreeNodeType to_find);     //    

TreeNode* LChild(TreeNode* node);       //     

TreeNode* RChild(TreeNode* node);       //     

TreeNode* Parent(TreeNode* root, TreeNode* node);       //    

void PreOrderByLoop(TreeNode* root);     //          

void InOrderByLoop(TreeNode* root);      //           

void PostOrderByLoop(TreeNode* root);    //          

void TreeMirror(TreeNode* root);         //      

int isCompleteTree(TreeNode* root);      //

②bin_tree.

#include "bin_tree.h"

#include 

#include "seqqueue.h"
#include "seqstack.h"

TreeNode* CreateTreeNode(TreeNodeType value){
    TreeNode* new_node = (TreeNode*)malloc(sizeof(TreeNode));
    new_node->data = value;
    new_node->lchild = NULL;
    new_node->rchild = NULL;
    return new_node;
}

void DestroyTreeNode(TreeNode* ptr){
    free(ptr);
}

void TreeInit(TreeNode** root){
    if(root == NULL){
        return;
    }
    *root = NULL;
}

void PreOrder(TreeNode* root){
    if(root == NULL){
        return;
    }
    printf("%c ",root->data);
    PreOrder(root->lchild);
    PreOrder(root->rchild);
}

void InOrder(TreeNode* root){
    if(root == NULL){
        return;
    }
    InOrder(root->lchild);
    printf("%c ",root->data);
    InOrder(root->rchild);
}

void PostOrder(TreeNode* root){ 
    if(root == NULL){
        return;
    }
    PostOrder(root->lchild);
    PostOrder(root->rchild);
    printf("%c ",root->data);
}

void LevelOrder(TreeNode* root){
    if(root == NULL){
        //  
        return;
    }
    SeqQueue q;
    SeqQueueInit(&q);
    //1.          
    SeqQueuePush(&q, root);
    //2.       
    TreeNode* cur = NULL;
    while(SeqQueueFront(&q, &cur)){
         //3.          
         printf("%c ", cur->data);
         SeqQueuePop(&q);
         //4.               
         if(cur->lchild != NULL){
             SeqQueuePush(&q, cur->lchild);
         }
         if(cur->rchild != NULL){
             SeqQueuePush(&q, cur->rchild);
         }
         //5.       ，      
    }
}

TreeNode* _TreeCreate(TreeNodeType array[], size_t size, size_t* index, TreeNodeType null_node){
    if(index == NULL){
        return NULL;    //    
    }
    if(*index >= size){
        //     
        return NULL;
    }
    if(array[*index] == null_node){
        return NULL;
    }
    TreeNode* new_node = CreateTreeNode(array[*index]);
    ++(*index);
    new_node->lchild = _TreeCreate(array,size,index,null_node);
    ++(*index);
    new_node->rchild = _TreeCreate(array,size,index,null_node);
    return new_node;
}

TreeNode* TreeCreate(TreeNodeType array[], size_t size, TreeNodeType null_node){
    //             
    size_t index = 0;
    return _TreeCreate(array, size, &index, null_node);
}

void TreeDestroy(TreeNode** root){
    if(root == NULL){
        return;    //    
    }
    if(*root == NULL){
        return;
    }
    TreeNode* to_delete = *root;
    TreeNode* to_delete_lchild = to_delete->lchild;
    TreeNode* to_delete_rchild = to_delete->rchild;
    DestroyTreeNode(to_delete);
    TreeDestroy(&to_delete_lchild);
    TreeDestroy(&to_delete_rchild);
    *root = NULL;
}

TreeNode* TreeClone(TreeNode* root){
    if(root == NULL){
        return NULL;
    }
    TreeNode* new_root = CreateTreeNode(root->data);
    new_root->lchild = TreeClone(root->lchild);
    new_root->rchild = TreeClone(root->rchild);
    return new_root;
}

//size_t TreeSize(TreeNode* root){
//    if(root == NULL){
//        return 0;
//    }
//    return 1 + TreeSize(root->lchild) + TreeSize(root->rchild);
//}
//
void _TreeSize(TreeNode* root,size_t* size){
    if(root == NULL || size == NULL){
        return;    //    
    }
    //      ，        size++
    ++(*size);
    _TreeSize(root->lchild,size);
    _TreeSize(root->rchild,size);
}

size_t TreeSize(TreeNode* root){
    size_t size = 0;
    _TreeSize(root,&size);
    return size;
}

size_t TreeLeafSize(TreeNode* root){
    if(root == NULL){
        return 0;
    }
    if(root->lchild == NULL && root->rchild == NULL){
        return 1;
    }
    return TreeLeafSize(root->lchild) + TreeLeafSize(root->rchild);
}

size_t TreeKLevelSize(TreeNode* root, int K){
    if(root == NULL || K < 1){
        return 0;
    }
    if(K == 1){
        return 1;
    }
    return TreeKLevelSize(root->lchild, K - 1) + TreeKLevelSize(root->rchild, K - 1);
}

size_t TreeHeight(TreeNode* root){
    if(root == NULL){
        return 0;
    }
    size_t lheight = TreeHeight(root->lchild);
    size_t rheight = TreeHeight(root->rchild);
    return lheight > rheight ? lheight + 1 : rheight + 1;
}

TreeNode* TreeFind(TreeNode* root, TreeNodeType to_find){
    if(root == NULL){
        return NULL;
    }
    if(root->data == to_find){
        return root;
    }
    TreeNode* lresult = TreeFind(root->lchild, to_find);
    TreeNode* rresult = TreeFind(root->rchild, to_find);
    return lresult != NULL ? lresult : rresult;
}

TreeNode* LChild(TreeNode* node){
    if(node == NULL){
        return NULL;
    }
    return node->lchild;
}

TreeNode* RChild(TreeNode* node){
    if(node == NULL){
        return NULL;
    }
    return node->rchild;
}

TreeNode* Parent(TreeNode* root, TreeNode* node){
    if(root == NULL || node == NULL){
        return NULL;
    }
    if(root->lchild == node || root->rchild == node){
        return root;
    }
    TreeNode* lresult = Parent(root->lchild, node);
    TreeNode* rresult = Parent(root->rchild, node);
    return lresult != NULL ? lresult : rresult;
}

void PreOrderByLoop(TreeNode* root){
    if(root == NULL){
        return;
    }
    SeqStack stack;
    SeqStackInit(&stack);
    SeqStackPush(&stack, root);
    while(1){
        TreeNode* top = NULL;
        SeqStackTop(&stack, &top);
        if(top == NULL){
            //   
            break;
        }
        //        
        printf("%c ", top->data);
        //       
        SeqStackPop(&stack);

        //                
        if(top->rchild != NULL){
            SeqStackPush(&stack, top->rchild);
        }
        if(top->lchild != NULL){
            SeqStackPush(&stack, top->lchild);
        }
    }
    printf("
");
}

void InOrderByLoop(TreeNode* root){
    if(root == NULL){
        return;
    }
    SeqStack stack;
    SeqStackInit(&stack);
    TreeNode* cur = root;
    while(1){
        //1.      ，              
        //          ，        
        while(cur != NULL){
            SeqStackPush(&stack, cur);
            cur = cur->lchild;
        }
        //2.     ，  ，       
        TreeNode* top = NULL;
        SeqStackTop(&stack, &top);
        if(top == NULL){
            //    
            break;
        }
        printf("%c ", top->data);
        SeqStackPop(&stack);
        //3.          ，      ，           
        cur = top->rchild;
    }
    printf("
");
    return;
}

void PostOrderByLoop(TreeNode* root){
    if(root == NULL){
        return;
    }
    SeqStack stack;
    SeqStackInit(&stack);
    TreeNode* cur = root;
    TreeNode* pre = NULL;
    while(1){
        while(cur != NULL){
            SeqStackPush(&stack, cur);
            cur = cur->lchild;
        }
        TreeNode* top = NULL;
        SeqStackTop(&stack, &top);
        if(top == NULL){
            break;
        }
        //       ，          ，    top
        //1.top       
        //2.top         
        //        top     
        if(top->rchild == NULL || top->rchild == pre){
            printf("%c ", top->data);
            SeqStackPop(&stack);
            pre = top;
        }
        else{
            cur = top->rchild;
        }
    }
    printf("
");
}

void TreeMirror(TreeNode* root){
    if(root == NULL){
        return;
    }
    TreeNode* tmp = root->lchild;
    root->lchild = root->rchild;
    root->rchild = tmp;
    TreeMirror(root->lchild);
    TreeMirror(root->rchild);
}

int isCompleteTree(TreeNode* root){
    if(root == NULL){
        return -1;
    }
    SeqQueue queue;
    SeqQueueInit(&queue);
    SeqQueuePush(&queue, root);
    int flag = 0;      //                       
    while(1){
        TreeNode* top = NULL;
        SeqQueueFront(&queue, &top);
        if(top == NULL){
            //    
            break;
        }
        //      
        if(flag == 0){
            if(top->lchild != NULL && top->rchild != NULL){
                SeqQueuePush(&queue, top->lchild);
                SeqQueuePush(&queue, top->rchild);
            }
            else if(top->lchild == NULL && top->rchild != NULL){
                return 0;
            }
            else if(top->lchild != NULL && top->rchild == NULL){
                SeqQueuePush(&queue, top->lchild);
                flag = 1;
            }
            else if(top->lchild == NULL && top->rchild == NULL){
                flag = 1;
            }
        }
        else{
            if(top->lchild == NULL && top->rchild == NULL){
                //                  
            }
            else{
                return 0;
            }
        }
        SeqQueuePop(&queue);
    }
    return 1;
}

③test.

#include "bin_tree.h"
#include 
#include 
#include 

#define TEST_HEADER printf("
========================%s====================
",__FUNCTION__)

void TestInit(){
    TEST_HEADER;
    TreeNode* root;
    TreeInit(&root);
    printf("root expect NULL, actual %p
",root);
}

void TestPreOrder(){
    TEST_HEADER;
    TreeNode* root;
    TreeInit(&root);
    TreeNode* a = CreateTreeNode('a');
    TreeNode* b = CreateTreeNode('b');
    TreeNode* c = CreateTreeNode('c');
    TreeNode* d = CreateTreeNode('d');
    TreeNode* e = CreateTreeNode('e');
    TreeNode* f = CreateTreeNode('f');
    TreeNode* g = CreateTreeNode('g');
    a->lchild = b;
    a->rchild = c;
    b->lchild = d;
    b->rchild = e;
    e->lchild = g;
    c->rchild = f;
    root = a;

    printf("[      ]：");
    PreOrder(root);
    printf("
");
}

void TestInOrder(){
    TEST_HEADER;
    TreeNode* root;
    TreeInit(&root);
    TreeNode* a = CreateTreeNode('a');
    TreeNode* b = CreateTreeNode('b');
    TreeNode* c = CreateTreeNode('c');
    TreeNode* d = CreateTreeNode('d');
    TreeNode* e = CreateTreeNode('e');
    TreeNode* f = CreateTreeNode('f');
    TreeNode* g = CreateTreeNode('g');
    a->lchild = b;
    a->rchild = c;
    b->lchild = d;
    b->rchild = e;
    e->lchild = g;
    c->rchild = f;
    root = a;

    printf("[      ]：");
    InOrder(root);
    printf("
");
}

void TestPostOrder(){
    TEST_HEADER;
    TreeNode* root;
    TreeInit(&root);
    TreeNode* a = CreateTreeNode('a');
    TreeNode* b = CreateTreeNode('b');
    TreeNode* c = CreateTreeNode('c');
    TreeNode* d = CreateTreeNode('d');
    TreeNode* e = CreateTreeNode('e');
    TreeNode* f = CreateTreeNode('f');
    TreeNode* g = CreateTreeNode('g');
    a->lchild = b;
    a->rchild = c;
    b->lchild = d;
    b->rchild = e;
    e->lchild = g;
    c->rchild = f;
    root = a;

    printf("[      ]：");
    PostOrder(root);
    printf("
");
}

void TestLevelOrder(){
    TEST_HEADER;
    TreeNode* root;
    TreeInit(&root);
    TreeNode* a = CreateTreeNode('a');
    TreeNode* b = CreateTreeNode('b');
    TreeNode* c = CreateTreeNode('c');
    TreeNode* d = CreateTreeNode('d');
    TreeNode* e = CreateTreeNode('e');
    TreeNode* f = CreateTreeNode('f');
    TreeNode* g = CreateTreeNode('g');
    a->lchild = b;
    a->rchild = c;
    b->lchild = d;
    b->rchild = e;
    e->lchild = g;
    c->rchild = f;
    root = a;

    printf("[      ]：");
    LevelOrder(root);
    printf("
");
}

void TestCreate(){
    TEST_HEADER;
    TreeNodeType array[] = "abd##eg###c#f##";
    TreeNode* root = TreeCreate(array,strlen(array),'#');

    printf("[      ]：");
    PreOrder(root);
    printf("
");

    printf("[      ]：");
    InOrder(root);
    printf("
");

    printf("[      ]：");
    PostOrder(root);
    printf("
");
}

void TestDestroy(){
    TEST_HEADER;
    TreeNodeType array[] = "abd##eg###c#f##";
    TreeNode* root = TreeCreate(array,strlen(array),'#');

    TreeDestroy(&root);
    printf("root expect NULL, actual %p
", root);
}

void TestClone(){
    TEST_HEADER;
    TreeNodeType array[] = "abd##eg###c#f##";
    TreeNode* root = TreeCreate(array,strlen(array),'#');

    TreeNode* new_root = TreeClone(root);
    printf("new_root: %p, root: %p
",new_root,root);

    printf("[      ]：");
    PreOrder(new_root);
    printf("
");

    printf("[      ]：");
    InOrder(new_root);
    printf("
");

    printf("[      ]：");
    PostOrder(new_root);
    printf("
");
}

void TestSize(){
    TEST_HEADER;
    TreeNodeType array[] = "abd##eg###c#f##";
    TreeNode* root = TreeCreate(array,strlen(array),'#');
    printf("size expect 7, actual %lu
",TreeSize(root));
}

void TestLeafSize(){
    TEST_HEADER;
    TreeNodeType array[] = "abd##eg###c#f##";
    TreeNode* root = TreeCreate(array, strlen(array), '#');
    printf("leafsize expect 3, actual %lu
", TreeLeafSize(root));
}

void TestKLevelSize(){
    TEST_HEADER;
    TreeNodeType array[] = "abd##eg###c#f##";
    TreeNode* root = TreeCreate(array, strlen(array), '#');
    printf("3LevelSize expect 3, actual %lu
", TreeKLevelSize(root, 3));
}

void TestHeight(){
    TEST_HEADER;
    TreeNodeType array[] = "abd##eg###c#f##";
    TreeNode* root = TreeCreate(array, strlen(array), '#');
    printf("height expect 4, actual %lu
", TreeHeight(root));
}

void TestFind(){
    TEST_HEADER;
    TreeNodeType array[] = "abd##eg###c#f##";
    TreeNode* root = TreeCreate(array, strlen(array), '#');
    TreeNode* find = TreeFind(root, 'd');
    printf("find->data expect d, actual %c
", find->data);
}

void TestLChild(){
    TEST_HEADER;
    TreeNodeType array[] = "abd##eg###c#f##";
    TreeNode* root = TreeCreate(array, strlen(array), '#');
    TreeNode* find = TreeFind(root, 'b');
    TreeNode* lchild = LChild(find);
    printf("lchild->data expect d, actual %c
", lchild->data);
}

void TestRChild(){
    TEST_HEADER;
    TreeNodeType array[] = "abd##eg###c#f##";
    TreeNode* root = TreeCreate(array, strlen(array), '#');
    TreeNode* find = TreeFind(root, 'b');
    TreeNode* rchild = RChild(find);
    printf("rchild->data expect e, actual %c
", rchild->data);
}

void TestParent(){
    TEST_HEADER;
    TreeNodeType array[] = "abd##eg###c#f##";
    TreeNode* root = TreeCreate(array, strlen(array), '#');
    TreeNode* find = TreeFind(root, 'b');
    TreeNode* parent = Parent(root, find);
    printf("b parent expect a, actual %c
", parent->data);

    find = TreeFind(root, 'f');
    parent = Parent(root, find);
    printf("f parent expect c, actual %c
", parent->data);
}

void TestPreOrderByLoop(){
    TEST_HEADER;
    TreeNodeType array[] = "abd##eg###c#f##";
    TreeNode* root = TreeCreate(array, strlen(array), '#');
    printf("[      ]：");
    PreOrderByLoop(root);
}

void TestInOrderByLoop(){
    TEST_HEADER;
    TreeNodeType array[] = "abd##eg###c#f##";
    TreeNode* root = TreeCreate(array, strlen(array), '#');
    printf("[      ]：");
    InOrderByLoop(root);
}

void TestPostOrderByLoop(){
    TEST_HEADER;
    TreeNodeType array[] = "abd##eg###c#f##";
    TreeNode* root = TreeCreate(array, strlen(array), '#');
    printf("[      ]：");
    PostOrderByLoop(root);
}

void TestMirror(){
    TEST_HEADER;
    TreeNodeType array[] = "abd##eg###c#f##";
    TreeNode* root = TreeCreate(array, strlen(array), '#');
    TreeMirror(root);
    printf("[      ]：");
    PreOrderByLoop(root);
    printf("[      ]：");
    InOrderByLoop(root);
    printf("[      ]：");
    PostOrderByLoop(root);
}

void TestIsCompleteTree(){
    TEST_HEADER;
    TreeNodeType array[] = "abd##eg###c#f##";
    TreeNode* root = TreeCreate(array, strlen(array), '#');
    int ret = isCompleteTree(root);
    printf("ret expect 0, actual %d
", ret);

    TreeNodeType array1[] = "abd##e##cf###";
    TreeNode* root1 = TreeCreate(array1, strlen(array1), '#');
    ret = isCompleteTree(root1);
    printf("ret expect 1, actual %d
", ret);
}

int main(){
    TestInit();
    TestPreOrder();
    TestInOrder();
    TestPostOrder();
    TestLevelOrder();
    TestCreate();
    TestDestroy();
    TestClone();
    TestSize();
    TestLeafSize();
    TestKLevelSize();
    TestHeight();
    TestFind();
    TestLChild();
    TestRChild();
    TestParent();
    TestPreOrderByLoop();
    TestInOrderByLoop();
    TestPostOrderByLoop();
    TestMirror();
    TestIsCompleteTree();
    return 0;
}

c言語で実現された多形スタック――小柄精悍