ツリーの問題の要約(1)—基本的な問題

1、二叉検索ツリーの作成
ツリーは、左サブツリーの値がルートノードよりも大きくなく、右サブツリーの値がルートノードよりも大きくなるようにソートされたツリーです.ノードを二叉探索ツリーに挿入するには、再帰的または非再帰的メソッドを使用します.再帰メソッドを使用するコードは簡単で、非再帰を使用すると分かりやすい.
二叉探索ツリーBST定義:

struct node {
    int data;
    struct node* left;
    struct node* right;
};

二叉検索ツリーでノードコードを作成します.

struct node* newNode(int data)
{
    struct node* nd = (struct node*)malloc(sizeof(struct node)); //    
    nd->data = data;                  //  data 
    nd->left = nd->right = NULL;      //          NULL
    return nd;
}

二叉検索ツリー挿入ノードコード1(再帰、関数はルートノードを返します):

struct node* insert(struct node* root, int data)
{
    if (root == NULL) {  //     ，         。
        return newNode(data);
    } else {
        if (root->data >= data) { //              ，         。
            root->left = insert(root->left, data); 
        } else {                  //           ，         。
            root->right = insert(root->right, data);
        }
        return root;    //       。
    }
}

二叉探索ツリー挿入ノードコード2(再帰、関数に戻り値なし):

void insert2(struct node** rootRef, int data)          
{                                                      
    struct node* root = *rootRef;                      
    if (root == NULL) {                                
        *rootRef = newNode(data);                      
        return;                                        
    }                                                  
    if (root->data >= data)                            
        insert2(&(root->left), data);                  
    else                                               
        insert2(&(root->right), data);                 
}                                                      
                  

ツリー挿入ノードコード3(再帰的でない):

void insert3(struct node** rootRef, int data)
{
    struct node* root = *rootRef;
    struct node* nd = newNode(data);
    if (root == NULL) {
        *rootRef = nd;
        return;
    }
    struct node* parent = NULL;
    struct node* current = root;
    while (current != NULL) {
        parent = current;   //parent      ，        NULL
        if (current->data >= data)
            current = current->left;
        else
            current = current->right;
    }
    if (parent->data >= data) //               
        parent->left = nd;
    else
        parent->right = nd;
}

3つのノードを含む2つの検索ツリーを作成します.

//       
struct node* build123a() {
struct node* root = newNode(2);
root->left = newNode(1);
root->right = newNode(3);
return(root);
}

//  insert       
struct node* build123b() {
struct node* root = NULL;
root = insert(root, 2);
root = insert(root, 1);
root = insert(root, 3);
return(root);
}

2、ツリーのノード数(ツリーの検索は不要)

//    =       +       +1（   ）
int size(struct node* root)
{
    if (root == NULL) return 0;
    return size(root->left) + size(root->right) + 1;
}

3、ツリーの深さ(ルートノードから最も遠いリーフノードまでの距離、空のツリーの深さは0)

int maxDepth(struct node* root)
{
    if (root == NULL)
        return 0;
    else {
        int lDepth = maxDepth(root->left);  //         
        int rDepth = maxDepth(root->right); //       
        return lDepth>rDepth? lDepth+1: rDepth+1; //    +1       
    }
}

4、二叉探索木最小値(最大値類似、右サブツリー照会可)

//         ，          
int minValue(struct node* root)
{
    assert(root != NULL);
    struct node* current = root;
    while (current->left != NULL) {
        current = current->left;
    }
    return current->data;
}

//              
int minValue(struct node* root)
{
    assert(root != NULL);
    if (root->left == NULL) return root->data;
    else return minValue(root->left);
}

5、二叉検索ツリーに値があるかどうかを検索する

/*              target   */
bool lookup(struct node* root, int target)
{
    if (root == NULL)
        return false;
    if (root->data == target)
        return true;
    else if (root->data > target)
        return lookup(root->left, target);
    else
        return lookup(root->right, target);
}