二叉树的建立与基本操作
二叉树是一种特殊的树形结构，它由节点（node）组成，每个节点最多有两个子节点。二叉树的基本操作包括建立二叉树、遍历二叉树、查二叉树节点、插入和删除节点等。本文将详细介绍二叉树的建立和基本操作，并给出相应的代码示例。
一、建立二叉树
建立二叉树有多种方法，包括使用数组、链表和前序、中序、后序遍历等。下面以使用链表的方式来建立二叉树为例。
1.定义二叉树节点类
首先，定义一个二叉树节点的类，包含节点值、左子节点和右子节点三个属性。
```python
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
```
2.建立二叉树
使用递归的方法来建立二叉树，先构造根节点，然后递归地构造左子树和右子树。
```python
def build_binary_tree(lst):
if not lst:  # 如果 lst 为空，则返回 None
return None
mid = len(lst) // 2  # 取 lst 的中间元素作为根节点的值
root = Node(lst[mid])
root.left = build_binary_tree(lst[:mid])  # 递归构造左子树
root.right = build_binary_tree(lst[mid+1:])  # 递归构造右子树
return root
```
下面是建立二叉树的示例代码：
```python
lst = [1, 2, 3, 4, 5, 6, 7]
root = build_binary_tree(lst)
```
二、遍历二叉树
遍历二叉树是指按照其中一规则访问二叉树的所有节点，常见的遍历方式有前序遍历、中序遍历和后序遍历。
1.前序遍历
前序遍历是指先访问根节点，然后访问左子节点，最后访问右子节点。
```python
def pre_order_traversal(root):
if root:
print(root.value)  # 先访问根节点
pre_order_traversal(root.left)  # 递归访问左子树
pre_order_traversal(root.right)  # 递归访问右子树
```
2.中序遍历
中序遍历是指先访问左子节点，然后访问根节点，最后访问右子节点。
```python
def in_order_traversal(root):
if root:
in_order_traversal(root.left)  # 递归访问左子树
print(root.value)  # 访问根节点
in_order_traversal(root.right)  # 递归访问右子树
```
3.后序遍历
二叉树的基本性质后序遍历是指先访问左子节点，然后访问右子节点，最后访问根节点。
```python
def post_order_traversal(root):
if root:
post_order_traversal(root.left)  # 递归访问左子树
post_order_traversal(root.right)  # 递归访问右子树
print(root.value)  # 访问根节点
```
下面是遍历二叉树的示例代码：
```python
pre_order_traversal(root)
in_order_traversal(root)
post_order_traversal(root)
```
三、查二叉树节点
查二叉树节点可以通过遍历的方式实现，也可以通过递归的方式实现。
1.遍历查
遍历查是指按照其中一种遍历方式遍历二叉树的所有节点，到目标节点。
```python
def find_node(root, value):
if not root:
return None
if root.value == value:

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。