[数据结构与算法]算法01树

1 树的定义

• root：根节点
• degree：节点拥有的子树树
• leaf：degree=0的节点
• depth：树的深度或者高度

2 二叉树

2.1 遍历

二叉树的遍历指的是：从根节点出发，按照某种次序依次访问二叉树中的所有节点。

2.1.1 前序遍历

先访问根节点，然后前序遍历左子树，再前序遍历右子树。

代码逻辑（递归）

void pre_order_traverse(Node* root) {
	if (nullptr == root) {
		return root;
	}
	// do something with root
	std::cout << root->val << std::endl;
	// 前序遍历左子树
	pre_order_traverse(root->left);
	// 前序遍历右子树
	pre_order_traverse(root->right);
}

2.1.2 中序遍历

从根节点开始（并非先do something with root），中序遍历根节点的左子树，然后访问根节点，最后中序遍历右子树
代码逻辑（递归）

void in_order_traverse(Node* root) {
	if (nullptr == root)
		return root;
	in_order_traverse(root-left);
	// do something with root
	in_order_traverse(root->right);
}

2.1.3 后序遍历（同理、不重复）

2.2 二叉排序树

• 如果左子树不为空，左子树上所有节点的值 < 它的根节点的值；
• 如果右子树不为空，右子树上所有节点的值 > 它的根节点的值；
• 它的左子树和右子树也分别为二叉排序树；

查找

Node* get_node(Node* root, int key) {
	if (nullptr == root)
		return root;

	if (key == root->key) {
		return root;
	} else if (key < root->key) {
		return get_node(root->left, key);
	} else if (key > root->key) {
		return get_node(root->right, key);
	}
}