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.