Data Structure - Tree
A tree is a typical nonlinear data structure, composed of nodes and edges connecting nodes, used to represent a "one-to-many" hierarchical relationship among elements.
Basic Terminology of Trees
Tree Terminology Diagram
ARoot node
Depth 0
Depth 0
BDepth 1
CDepth 1
DLeaf node
Depth 2
Depth 2
ELeaf node
FLeaf node
Root nodeNo parent, unique
Child nodeDirect child
Leaf nodeNo children
DepthNumber of edges from root to this node
HeightNumber of edges from this node to the deepest leaf
Binary treeEach node has at most 2 children
To understand tree structures, you need to master a few basic terms first:
| Term | Meaning |
|---|---|
| Root node (Root) | The starting node of a tree, with no parent node |
| Child node (Child) | The node at the next level directly connected to a given node |
| Parent node (Parent) | The node at the previous level directly connected to a given node |
| Leaf node (Leaf) | A node with no children, i.e., the end of a tree |
| Depth (Depth) | Number of edges from the root node to this node; the root has a depth of 0 |
| Height (Height) | Number of edges from this node to the deepest leaf node |
Binary Tree Traversal
Four traversal methods for binary trees — using the same tree as an example
1
2
3
4
5
Preorder (root → left → right)
1 2 4 5 3Inorder (left → root → right)
4 2 5 1 3Postorder (left → right → root)
4 5 2 3 1Level order (layer by layer)
1 2 3 4 5The four common traversal methods are as follows:
| Traversal method | Visit order | Typical application |
|---|---|---|
| Preorder traversal | Root → left → right | Copying trees, generating prefix expressions |
| Inorder traversal | Left → root → right | BST outputs sorted sequence |
| Postorder traversal | Left → right → root | Deleting trees, generating postfix expressions |
| Level order traversal | Layer by layer, left to right | BFS, printing by layers |
Example
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};
struct TreeNode* createNode(int value) {
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->data = value;
node->left = NULL;
node->right = NULL;
return node;
}
/* Preorder traversal: root → left → right */
void preOrder(struct TreeNode* root) {
if (root == NULL) return;
printf("%d ", root->data); /* Visit root first */
preOrder(root->left); /* Then traverse left subtree */
preOrder(root->right); /* Finally traverse right subtree */
}
/* Inorder traversal: left → root → right */
void inOrder(struct TreeNode* root) {
if (root == NULL) return;
inOrder(root->left); /* Traverse left subtree first */
printf("%d ", root->data); /* Then visit root */
inOrder(root->right); /* Finally traverse right subtree */
}
/* Postorder traversal: left → right → root */
void postOrder(struct TreeNode* root) {
if (root == NULL) return;
postOrder(root->left); /* Traverse left subtree first */
postOrder(root->right); /* Then traverse right subtree */
printf("%d ", root->data); /* Finally visit root */
}
int main() {
/* Build the following binary tree:
1
/ \
2 3
/ \
4 5 */
struct TreeNode* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
printf("Preorder: "); preOrder(root); printf("\n"); /* 1 2 4 5 3 */
printf("Inorder: "); inOrder(root); printf("\n"); /* 4 2 5 1 3 */
printf("Postorder: "); postOrder(root); printf("\n"); /* 4 5 2 3 1 */
return 0;
}
#include <stdlib.h>
struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};
struct TreeNode* createNode(int value) {
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->data = value;
node->left = NULL;
node->right = NULL;
return node;
}
/* Preorder traversal: root → left → right */
void preOrder(struct TreeNode* root) {
if (root == NULL) return;
printf("%d ", root->data); /* Visit root first */
preOrder(root->left); /* Then traverse left subtree */
preOrder(root->right); /* Finally traverse right subtree */
}
/* Inorder traversal: left → root → right */
void inOrder(struct TreeNode* root) {
if (root == NULL) return;
inOrder(root->left); /* Traverse left subtree first */
printf("%d ", root->data); /* Then visit root */
inOrder(root->right); /* Finally traverse right subtree */
}
/* Postorder traversal: left → right → root */
void postOrder(struct TreeNode* root) {
if (root == NULL) return;
postOrder(root->left); /* Traverse left subtree first */
postOrder(root->right); /* Then traverse right subtree */
printf("%d ", root->data); /* Finally visit root */
}
int main() {
/* Build the following binary tree:
1
/ \
2 3
/ \
4 5 */
struct TreeNode* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
printf("Preorder: "); preOrder(root); printf("\n"); /* 1 2 4 5 3 */
printf("Inorder: "); inOrder(root); printf("\n"); /* 4 2 5 1 3 */
printf("Postorder: "); postOrder(root); printf("\n"); /* 4 5 2 3 1 */
return 0;
}
Binary Search Tree (BST)
Binary Search Tree (BST) — left smaller, right larger
50
30
70
20
40
60
80
BST properties and operations
Property: all values in left subtree < root < all values in right subtree
Insertion/search: go left subtree if smaller, go right subtree if larger, O(log n) when balanced
Inorder traversal outputs ascending sequence: 20 30 40 50 60 70 80
Note: inserting in order 1,2,3... degenerates into a linked list O(n); AVL tree can solve this
Binary Search Tree (BST)Requirement: For each node, all values in the left subtree are less than the node, and all values in the right subtree are greater than the node.
Example
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};
/* BST Insertion: recursively locate the appropriate position based on the value's size
Time complexity: O(h), h is the height of the tree, O(log n) when balanced. */
struct TreeNode* insert(struct TreeNode* root, int value) {
if (root == NULL) {
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->data = value;
node->left = node->right = NULL;
return node;
}
if (value < root->data) {
root->left = insert(root->left, value); /* If less than root, insert into left subtree */
} else if (value > root->data) {
root->right = insert(root->right, value); /* If greater than root, insert into right subtree */
}
return root; /* If equal, ignore (BST usually does not store duplicate values) */
}
/* BST Search: compare with current node to decide whether to search left or right */
struct TreeNode* search(struct TreeNode* root, int target) {
if (root == NULL || root->data == target) {
return root; /* Target found or reached a leaf node */
}
if (target < root->data) {
return search(root->left, target); /* Target is smaller, search in the left subtree */
}
return search(root->right, target); /* Target is larger, search in the right subtree */
}
/* In-order traversal (verify BST ordering) */
void inOrder(struct TreeNode* root) {
if (root == NULL) return;
inOrder(root->left);
printf("%d ", root->data);
inOrder(root->right);
}
int main() {
struct TreeNode* root = NULL;
int values[] = {50, 30, 70, 20, 40, 60, 80};
/* Insert sequentially to build the BST */
for (int i = 0; i < 7; i++) {
root = insert(root, values[i]);
}
printf("BST in-order traversal (ascending): ");
inOrder(root); /* Output: 20 30 40 50 60 70 80 */
printf("\n");
/* Search test */
int target = 40;
struct TreeNode* found = search(root, target);
printf("%d %s\n", target, found ? "Found!" : "Not found");
/* Output: 40 Found! */
return 0;
}
#include <stdlib.h>
struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};
/* BST Insertion: recursively locate the appropriate position based on the value's size
Time complexity: O(h), h is the height of the tree, O(log n) when balanced. */
struct TreeNode* insert(struct TreeNode* root, int value) {
if (root == NULL) {
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->data = value;
node->left = node->right = NULL;
return node;
}
if (value < root->data) {
root->left = insert(root->left, value); /* If less than root, insert into left subtree */
} else if (value > root->data) {
root->right = insert(root->right, value); /* If greater than root, insert into right subtree */
}
return root; /* If equal, ignore (BST usually does not store duplicate values) */
}
/* BST Search: compare with current node to decide whether to search left or right */
struct TreeNode* search(struct TreeNode* root, int target) {
if (root == NULL || root->data == target) {
return root; /* Target found or reached a leaf node */
}
if (target < root->data) {
return search(root->left, target); /* Target is smaller, search in the left subtree */
}
return search(root->right, target); /* Target is larger, search in the right subtree */
}
/* In-order traversal (verify BST ordering) */
void inOrder(struct TreeNode* root) {
if (root == NULL) return;
inOrder(root->left);
printf("%d ", root->data);
inOrder(root->right);
}
int main() {
struct TreeNode* root = NULL;
int values[] = {50, 30, 70, 20, 40, 60, 80};
/* Insert sequentially to build the BST */
for (int i = 0; i < 7; i++) {
root = insert(root, values[i]);
}
printf("BST in-order traversal (ascending): ");
inOrder(root); /* Output: 20 30 40 50 60 70 80 */
printf("\n");
/* Search test */
int target = 40;
struct TreeNode* found = search(root, target);
printf("%d %s\n", target, found ? "Found!" : "Not found");
/* Output: 40 Found! */
return 0;
}
Other extensionsIn the ideal case (when the tree remains balanced), BST insertion, deletion, and search can all achieve O(log n). However, if the data itself is ordered (such as inserting by 1, 2, 3, 4...), the BST degenerates into a linked list, and efficiency drops to O(n). To solve this problem, computer science has developedAVL treeand other self-balancing binary search trees.