数据结构学习笔记 --- 二叉树

树

二叉树

二叉树（binary tree）是一种非线性数据结构，代表“祖先”与“后代”之间的派生关系，体现了“一分为二”的分治逻辑。与链表类似，二叉树的基本单元是节点，每个节点包含值、左子节点引用和右子节点引用。

二叉树结点

struct TreeNode{
	int val;		//节点值
	TreeNode* left; //左节点指针
    TreeNode* right;//右节点指针
    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
}
1
2
3
4
5
6

每个节点都有两个引用（指针），分别指向左子节点（left-child node）和右子节点（right-child node），该节点被称为这两个子节点的父节点（parent node）。当给定一个二叉树的节点时，我们将该节点的左子节点及其以下节点形成的树称为该节点的左子树（left subtree），同理可得右子树（right subtree）。在二叉树中，除叶节点外，其他所有节点都包含子节点和非空子树。

常见术语：

• 根节点（root node）：位于二叉树顶层的节点，没有父节点。
• 叶节点（leaf node）：没有子节点的节点，其两个指针均指向 None 。
• 边（edge）：连接两个节点的线段，即节点引用（指针）。
• 节点所在的层（level）：从顶至底递增，根节点所在层为 1 。
• 节点的度（degree）：节点的子节点的数量。在二叉树中，度的取值范围是 0、1、2 。
• 二叉树的高度（height）：从根节点到最远叶节点所经过的边的数量。
• 节点的深度（depth）：从根节点到该节点所经过的边的数量。
• 节点的高度（height）：从距离该节点最远的叶节点到该节点所经过的边的数量

常用性质：

如果将根节点的层数定为1，二叉树的第 i 层上最多有2^{i-1}个结点

如果将根节点的层数定为1，二叉树的高度为h的情况下，最多有2^h-1个结点

具有n个结点的完全二叉树的深度为log2n+1

初始化二叉树

class BinaryTree {
public:
	BinaryTree(); 
	~BinaryTree();
	void insert(); //插入节点
private:
	TreeNode* root;
};

BinaryTree::BinaryTree()
{
	root = nullptr;
}

BinaryTree::~BinaryTree()
{
	delete root;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

插入结点

void BinaryTree::insert(int val)
{
	if (root == nullptr) {
		root = new TreeNode(val);
		return;
	}
	TreeNode* current = root;
	TreeNode* parent = nullptr;

	//我们使用循环而不是递归来找到要插入的位置，并且根据val的值来判断是插入到左子树还是右子树。这样就避免了无限递归的问题。
	while (current != nullptr) {
		parent = current;
		if (val < current->val) {
			current = current->left;
		}
		else {
			current = current->right;
		}
	}

	if (val < parent->val) {
		parent->left = new TreeNode(val);
	}
	else {
		parent->right = new TreeNode(val);
	}
}
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

删除节点

仅适用于简单二叉树！！！

void BinaryTree::deleteNode(int val)
{
	if (root == nullptr) return;
	TreeNode* current = root;
	TreeNode* parent = nullptr;

	while (current->val != val) {
		parent = current;
		if (val < current->val) {
			current = current->left;
		}
		else {
			current = current->right;
		}
	}

	if (val < parent->val) {
		parent->left = NULL;
	}
	else {
		parent->right = NULL;
	}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

遍历结点

先序遍历,其余两种代码顺序不同

void BinaryTree::preOrder(TreeNode* root)
{
	if (root == nullptr) return;

	cout << root->val << endl;
	preOrder(root->left);
	preOrder(root->right);
}
1
2
3
4
5
6
7
8