1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

/* BST = Binary Search Tree
 *
 * ... a particular kind of tree.
 *
 * Q: What is a tree?
 * A: Dynamic structure like a linked list but with more than one "out link".
 *    IOW, instead of .next, you have .left and .right  (in the case of a
 *    "binary" tree).
 *
 */

typedef struct _BSTNode {
    int value;
    struct _BSTNode* left;
    struct _BSTNode* right;
} BSTNode;

// Reminder:  You can't refer to the shortcut name (BSTNode) until you get to it,
// so you have to use the long name (struct _BSTNode) within the struct definition.





/* Binary tree of size 1.  The root is [∙ | 6 | ∙].  It has no children (yet).
 *
 *              root  (like the head in a linked list)
 *                ↓
 *           [∙ | 6 | ∙ ]
 *            ↓       ↓
 *           NULL    NULL
 *
 * Binary search tree
 * Each node has a value.
 * node -> left ->  value must be less    than               node -> value
 * node -> right -> value must be greater than (or equal to) node -> value
 *
 *               root  (like the head in a linked list)
 *                ↓
 *           [∙ | 6 | ∙ ]
 *            ↓       ↓
 *    [∙ | 4 | ∙]    [∙ | 8 | ∙]     ← leaf nodes
 *     ↓       ↓      ↓       ↓       
 *   NULL     NULL    NULL   NULL
 *
 * Leaf node is a node that has no children.
 *
 * Root node is a node that is not the child of any other node.
 *
 * Binary search trees let you do something similar to binary search.
 *
 *                         root  (like the head in a linked list)
 *                          ↓
 *                     [∙ | 6 | ∙ ]
 *                      ↓       ↓
 *              [∙ | 4 | ∙]    [∙ | 8 | ∙]
 *               ↓       ↓      ↓       ↓       
 *         [∙|3|∙]  [∙|5|∙]  [∙|7|∙]   [∙|9|∙]
 *
 *
 * Q:  Is 9 in the structure above?
 * A:  Clearly yes, but with a BST, it is faster to find out.
 *
 * With a linked list, you would have to go through the whole list.
 * Assuming it is not sorted:
 *
 * 4 → 8 → 7 → 9 → 3 → 5 → 6
 *
 *
 * To add a new number to the BST, we start at the root.
 *
 * If the root is NULL, then add it at the root.  This just like
 * the first node in a linked list.
 *
 * Just like an empty linked list is NULL, so is an empty BST.
 *
 * Left subtree of the above tree rooted at […|6|…]:
 *
 *              [∙ | 4 | ∙]
 *               ↓       ↓
 *         [∙|3|∙]      [∙|5|∙]
 *
 *
 * Left subtree of the above tree rooted at […|4|…]:
 *
 *         [∙|3|∙]
 *          ↓   ↓
 *       NULL   NULL
 *
 *
 * Left subtree of the above tree rooted at […|3|…]:
 *
 *         NULL  (empty tree)
 */

// DO NOT COPY THIS CODE (Reminder:  Our code is not fair game unless it
// explicitly says "Okay to copy/adapt" (or similar).  Your code may
// come out very similar, but you should write it without looking at
// this.

void insert(int value, BSTNode** a_root) {
    if (*a_root == NULL) {  // is tree empty?
        BSTNode* new_node = { .value = value, .left = NULL, .right = NULL };
        *a_root = NULL;
    }
}

int main(int argc, char* argv[]) {
    // Empty tree
    BSTNode* root = NULL;

    // Insert a new node:  6
    insert(value, &root);
    // Type of  root is  BSTNode*   (address of a BSTNode)
    // Type of &root is  BSTNode**  (address of an address of a BSTNode)

    return EXIT_SUCCESS;
}
/* vim: set tabstop=4 shiftwidth=4 fileencoding=utf-8 noexpandtab: */

© Copyright 2020 Alexander J. Quinn         This content is protected and may not be shared, uploaded, or distributed.