出来混总是要还的， 大一的时候没有好好学习数据结构， 现在要补上了

二叉树的数据结构

结点

每一个二叉树的结点中至少含有三个元素, 即结点上的数据, 指向左子树的指针, 指向右子树的指针. 假定我们每个结点中的数据整数, 使用c语言描述结点这个数据结构如下

1
2
3
4
5
struct node {
	int data;	// 数据域
	struct node* left; // 左指针/孩子
	struct node* right;	// 右指针/孩子
}

树

对于每一颗树来说, 我们知道了它的根结点, 就能根据每一个结点上的指针找到它的所有子结点, 也就是说, 找到了它根结点就相当于找到了它的全部结点, 那么我们就来定义一个树的数据结构

1
2
3
struct Tree {
	Node* root; // 根节点
}

二叉树的遍历

前序遍历(根->左->右)

前序遍历, 又称先序遍历, 先根遍历. 对于每一个结点, 先遍历它的根节点, 然后遍历它的左孩子结点, 再遍历右孩子结点, 因此要先把根节点的左子树全部遍历完, 才可以遍历根结点, 然后是右子树
那么用递归法肯定是最好的一种方法

1
2
3
4
5
6
7
8
9
10
void preorder(Node* node) {
	if (node == NULL) { // 递归出口
		return ;
	} 
	else {
		printf("%d\n", node -> data);	// 显示根节点, 相当于遍历了根节点
		preorder(node -> left);
		preorder(node -> right);
	}
}

中序遍历(左->根->右)

中序遍历, 又称中根遍历, 即对于每一个结点, 先遍历其左子树, 然后遍历其根节点, 然后遍历右子树.
用递归方法实现如下

1
2
3
4
5
6
7
8
9
10
void in_order(Node* node) {
	if (node == NULL) { // 递归出口
		return ;	
	}
	else {
		in_order(node -> left);
		printf("%d\n", node -> data);
		in_order(node -> right);
	}
}

后序遍历(左->右->根)

后续遍历又称后根遍历， 顾名思义就是根在最后一个遍历， 先遍历左孩子， 然后遍历右孩子， 最后遍历根节点， 递归代码表示如下

1
2
3
4
5
6
7
8
9
10
void post_order(Node* node) {
	if (node == NULL) {
		return ;
	}
	else {
		post_order(node -> left);
		post_order(node -> right);
		printf("%d \n", node -> data);
	}
}

二叉搜索树(BST)

二叉搜索树, (binary search tree)就是一个有序的树， 其中对于任意一个子树， 其左孩子中的元素值 小于根节点的元素值 小于右孩子的元素的值， 即，node.left.data < node.right.data , 那么由我们上面的遍历方式， 可以看出若使用中序遍历， 当结点中的元素为数字时候， 那么中序遍历就会是一个从小到大的一个顺序，因此二叉搜索树， 又称为二叉排序树， 那么我们如何创建一颗二叉搜索树呢？

插入法创建二叉搜索树

如果我们将一个元素放在一颗二叉搜索树中， 首先我们要跟根节点中的元素进行比较， 若小于， 那么就放在左边， 继续跟左边的结点元素值进行比较， 若大于， 则放在右边，然后继续跟右边的结点元素值进行比较。若为空， 那么就放在当前节点。 那么我们可以对这样一种方法进行代码实现

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
void insert_bst(Tree* tree, int value) {
	Node* node = malloc(sizeof(Node)); // 将这个元素创建为一个结点
	node -> data = value;
	node -> left = NULL;
	node -> right = NULL;
	
	if (tree -> root == NULL) {
		tree -> root = node;
		return ; // 插入完成之后就停止, 不然程序会一直运行
	}
	else {
		Node* temp = tree -> root;
		while (temp != NULL) {
			if (value < temp -> data) { // 小于当前节点
				if (temp -> left == NULL) {
					temp -> left = node;
					return ; // 插入完成之后就停止, 不然程序会一直运行
				}
				else {
					temp = temp -> left; // 继续向左搜寻, 比较
				}
			}
			else { // 小于当前结点
				if (temp -> right == NULL) {
					temp -> right = node;
					return ;
				}
				else {
					temp = temp -> right; // 继续向右
				}
			}
		}
	}
}

测试代码

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
#include <stdio.h>
#include <stdlib.h>

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

typedef struct {
	Node* root;
} Tree;


void insert_bst(Tree* tree, int value) {
	Node* node = malloc(sizeof(Node));
	node -> data = value;
	node -> left = NULL;
	node -> right = NULL;
	
	if (tree -> root == NULL) {
		tree -> root = node;
		return ;
	}
	else {
		Node* temp = tree -> root;
		while (temp != NULL) {
			if (value < temp -> data) {
				if (temp -> left == NULL) {
					temp -> left = node;
					return ;
				}
				else {
					temp = temp -> left;
				}
			}
			else {
				if (temp -> right == NULL) {
					temp -> right = node;
					return ;
				}
				else {
					temp = temp -> right;
				}
			}
		}
	}
}

void preorder(Node* node) {
	if (node == NULL) {
		return ;
	}
	else {
		printf("%d\n", node -> data);
		preorder(node -> left);
		preorder(node -> right);
	}
}

void in_order(Node* node) {
	if (node == NULL) {
		return ;
	}
	else {
		in_order(node -> left);
		printf("%d\n", node -> data);
		in_order(node -> right);
	}
}

void post_order(Node* node) {
	if (node == NULL) {
		return ;
	}
	else {
		post_order(node -> left);
		post_order(node -> right);
		printf("%d\n", node -> data);
	}
}

int main() {
	int arr[] = {1, 3, 2, 4, 0, 1, 2);
	int length = sizeof(arr) / sizeof(arr[0]);
	
	Tree tree;
	tree.root = NULL;
	
	for (int i = 0; i < length; i++) {
		insert_bst(&tree, arr[i]);
	}
	
	in_order(tree.root);
	return 0;
}

JAVA

Java 代码与C语言相比没有什么太多出入, 我就直接写一个测试类供大家参考

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
public class TestTree {

	public static void insert_BST(Tree tree, int value) {
		Node node = new Node(value);

		if (tree.root == null) {
			tree.root = node;
			return;
		} else {
			Node temp = tree.root;
			while (temp != null) {
				if (value < temp.data) {
					if (temp.left == null) {
						temp.left = node;
						return;
					} else {
						temp = temp.left;
					}
				} else {
					if (temp.right == null) {
						temp.right = node;
						return ;
					} else {
						temp = temp.right;
					}
				}
			}
		}
	}
	
	public static void inOrder(Node node) {
		if (node == null) {
			return ;
		} else {
			inOrder(node.left);
			System.out.println(node.data);
			inOrder(node.right);
		}
	}
	
	
	public static void main(String[] args) {
		int[] arr = {5, 8, 2, 1, 4, 3, 9, 7, 6};
		Tree tree = new Tree();
		
		for (int i = 0; i < arr.length; i++) {
			insert_BST(tree, arr[i]);
		}
		
		inOrder(tree.root);
	}
}

class Node {
	int data;
	Node left;
	Node right;

	public Node() {

	}

	public Node(int data) {
		this.data = data;
	}
}

class Tree {
	Node root;
}