浅谈二叉树

前言

浅谈二叉树

一、什么是二叉树？

二叉树是一种树形数据结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点

其中节点1为根节点，节点2为节点1的左子节点，节点3为节点1的右子节点。如果将节点2视为父节点，那么节点4和节点5分别为节点2的左子节点和右子节点。
注意，只有第一层没有父节点的节点称为根节点

二、二叉树的特点

• 每个节点最多有两个子节点，分别为左子节点和右子节点
• 子节点的顺序不能颠倒，即左子节点始终在右子节点之前
• 二叉树可以为空，此时称为空二叉树
• 二叉树的节点通常包含一个值（或键），还可能包含指向其左子节点和右子节点的指针

三、二叉树使用

1.创建节点类

代码如下：

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

节点类包括左子节点、右子节点和该节点本身的value

2.创建二叉树类

代码如下：

class BinaryTree:
    def __init__(self, root_value):
        self.root = TreeNode(root_value)

创建一个二叉树类，由于构造函数中只有一个self.root，所以该类只包含一个根节点

3.插入节点

代码如下：

def insert(self, value):
    """
    :param value: 当前要插入的值
    """
    self._inset_recursively(self.root, value)

def _inset_recursively(self, current_node, value):
    """
    :param current_node: 当前操作的节点
    :param value: 要插入的值
    """
    if value < current_node.value:
        if current_node.left is None:
            current_node.left = TreeNode(value)
        else:
            self._inset_recursively(current_node.left, value)
    else:
        if current_node.right is None:
            current_node.right = TreeNode(value)
        else:
            self._inset_recursively(current_node.right, value)

在插入节点时，先判断要插入的值是否小于当前节点值，如果小于则在左子节点插入，如果大于则在右子节点插入。在插入过程中，如果子节点已经存在，则在当前子节点的子节点中继续插入。
注意，插入节点时的比较大小不是必须的，可以任意插入在某个节点，如果是完全二叉树或者二叉搜索树则需要按照一定的规则插入。此处作为示例，使用了自定义插入规则。

4.搜索节点

代码如下：

def search(self, value):
    """
    :param value: 要查询的值
    """
    self._search_recursively(self.root, value)

def _search_recursively(self, current_node, value):
    """
    :param current_node: 当前操作的节点
    :param value: 要查询的值
    :return:
    """
    if current_node is None:
        return False
    if current_node.value == value:
        return True
    elif value < current_node.value:
        self._search_recursively(current_node.left, value)
    else:
        self._search_recursively(current_node.right, value)

在搜索节点时，先判断当前节点是否为空，如果为空，则必然不会再有子节点，所以可以直接返回False。如果当前节点不为空，则进一步判断当前节点值是否等于要搜索的值，如果等于，直接返回True。如果不存在，则判断当前值是否小于节点值，如果小于，则在子节点中搜索。否则在右节点中搜索。
注意，该搜索方式是因为在插入的过程中使用了自定义规则：如果插入值小于当前节点值，插入左子节点，否则插入右子节点。所以在搜索的时候才会有对应的小于当前节点值在左子节点中迭代查询，否则在右子节点中迭代查询的情况。

5.完整代码

代码如下：

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


class BinaryTree:
    def __init__(self, root_value):
        self.root = TreeNode(root_value)

    def insert(self, value):
        """
        :param value: 当前要插入的值
        """
        self._inset_recursively(self.root, value)

    def _inset_recursively(self, current_node, value):
        """
        :param current_node: 当前操作的节点
        :param value: 要插入的值
        """
        if value < current_node.value:
            if current_node.left is None:
                current_node.left = TreeNode(value)
            else:
                self._inset_recursively(current_node.left, value)
        else:
            if current_node.right is None:
                current_node.right = TreeNode(value)
            else:
                self._inset_recursively(current_node.right, value)

    def search(self, value):
        """
        :param value: 要查询的值
        """
        self._search_recursively(self.root, value)

    def _search_recursively(self, current_node, value):
        """
        :param current_node: 当前操作的节点
        :param value: 要查询的值
        :return:
        """
        if current_node is None:
            return False
        if current_node.value == value:
            return True
        elif value < current_node.value:
            self._search_recursively(current_node.left, value)
        else:
            self._search_recursively(current_node.right, value)

总结

本文仅仅适用于二叉树入门，二叉树还有大量的知识后续慢慢分享。