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 125 126 127 128 129 130 131 132 | #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 this an empty tree
// Create a new node
BSTNode* new_node = {.value = value, .left=NULL, .right=NULL};
*a_root = new_node;
}
else if(value < (*a_root) -> value) {
insert(value, &(*a_root) -> left);
}
else {
insert(value, &(*a_root) -> right);
}
}
int main(int argc, char* argv[]) {
// Empty tree
BSTNode* root = NULL; // just like with an empty linked list
// Type of root is BSTNode* (address of a BSTNode)
// Type of &root is BSTNode** (address of an address of a BSTNode)
insert(6, &root);
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.