root07 二叉树 Python 代码：数据结构和算法的基石
简介
二叉树是一种非线性数据结构，它由称为 节点 的元素组成，每个节点最多有两个称为 子节点 的子元素。二叉树通常用于表示分层数据或实现高效的搜索和排序算法。在 Python 中，可以使用 `collections.deque` 或 `heapq` 等内置数据结构来表示二叉树。
1. 节点类
二叉树的基石是 `Node` 类，它封装了节点的数据和指向其子节点的引用。
```python
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
```
2. 树类
```python
class BinaryTree:
def __init__(self):
self.root = None
```
3. 插入节点
将节点插入二叉树的过程称为 插入。此操作将新节点添加到树中，同时保持二叉树的性质。
```python
def insert(self, data):
new_node = Node(data)
if self.root is None:
self.root = new_node
else:
self._insert(new_node, self.root)
```
```python
def _insert(self, new_node, current_node):
if new_node.data < current_node.data:
if current_node.left is None:
current_node.left = new_node
else:
self._insert(new_node, current_node.left)
else:
if current_node.right is None:
current_node.right = new_node
else:
self._insert(new_node, current_node.right)
```
4. 搜索节点
在二叉树中查找特定数据值的节点的过程称为 搜索。
```python
def search(self, data):
if self.root is None:
return None
else:
return self._search(data, self.root)
```
```python
def _search(self, data, current_node):
if current_node is None:
return None
if current_node.data == data:
return current_node
elif data < current_node.data:
return self._search(data, current_node.left)
else:
return self._search(data, current_node.right)
```
5. 删除节点
从二叉树中删除节点的过程称为 删除。此操作将节点从树中移除，同时保持二叉树的性质。
```python
def delete(self, data):
if self.root is None:
return
else:
self._delete(data, self.root)
```
```python
def _delete(self, data, current_node):
if current_node is None:
return
if data < current_node.data:
self._delete(data, current_node.left)
elif data > current_node.data:
self._delete(data, current_node.right)
else:
if current_node.left is None:
temp = current_node.right
current_node = None
return temp
elif current_node.right is None:
temp = current_node.left
current_node = None
return temp
node = self._get_predecessor(current_node.left)
current_node.data = node.data
self._delete(node.data, current_node.left)
```
```python
def _get_predecessor(self, node):
if node.right is None:
return node
return self._get_predecessor(node.right)
```
6. 前序遍历
前序遍历是一种深度优先遍历，它首先访问根节点，然后递归访问左子树和右子树。
```python
def preorder(self, root):
if root is None:
return
print(root.data, end=" ")
self.preorder(root.left)
self.preorder(root.right)
```
7. 中序遍历
中序遍历也是一种深度优先遍历，它首先访问左子树，然后访问根节点，最后访问右子树。
```python
def inorder(self, root):
if root is None:
return
self.inorder(root.left)
print(root.data, end=" ")
self.inorder(root.right)
```
8. 后序遍历
后序遍历是一种深度优先遍历，它首先访问左子树，然后访问右子树，最后访问根节点。
```python
def postorder(self, root):
if root is None:
return
self.postorder(root.left)
self.postorder(root.right)
print(root.data, end=" ")
```
9. 层次遍历
层次遍历是一种广度优先遍历，它按层访问节点，先访问根节点，然后访问第一层的节点，依此类推。
```python
def level_order(self):
if self.root is None:
return
queue = [self.root]
while queue:
node = queue.pop(0)
print(node.data, end=" ")
if node.left is not None:
queue.append(node.left)
if node.right is not None:
queue.append(node.right)
```
10. 高度
二叉树的高度是树中从根节点到最深叶子节点的最长路径的长度。
```python
def height(self):
if self.root is None:
return 0
return self._height(self.root)
```
```python
def _height(self, node):
if node is None:
return 0
return 1 + max(self._height(node.left), self._height(node.right))
```
11. 大小
二叉树的大小是树中节点的数量。
```python
def size(self):
if self.root is None:
return 0
return self._size(self.root)
```
```python
def _size(self, node):
if node is None:
return 0
return 1 + self._size(node.left) + self._size(node.right)
```
12. 是否平衡
平衡二叉树是高度差不超过 1 的二叉树。
```python
def is_balanced(self):
if self.root is None:
return True
return self._is_balanced(self.root)
```
```python
def _is_balanced(self, node):
if node is None:
return True
lh = self._height(node.left)
rh = self._height(node.right)
return abs(lh - rh) <= 1 and self._is_balanced(node.left) and self._is_balanced(node.right)
```
13. 寻找最小值
寻找二叉树中的最小值，即从根节点到最左叶子节点的最短路径上的节点。
```python
def find_min(self):
if self.root is None:
return None
return self._find_min(self.root)
```
```python
def _find_min(self, node):
if node.left is None:
return node
return self._find_min(node.left)
```
14. 寻找最大值
寻找二叉树中的最大值，即从根节点到最右叶子节点的最短路径上的节点。
```python
def find_max(self):
if self.root is None:
return None
return self._find_max(self.root)
```
```python
def _find_max(self, node):
if node.right is None:
return node
return self._find_max(node.right)
```
15. 镜像
镜像二叉树是指将左子树和右子树互换的二叉树。
```python
def mirror(self):
if self.root is None:
return
self._mirror(self.root)
```
```python
def _mirror(self, node):
if node is None:
return
temp = node.left
node.left = node.right
node.right = temp
self._mirror(node.left)
self._mirror(node.right)
```
16. 是完全二叉树
完全二叉树是指除了最后一行外
