python数据结构基础(8)

今天来使用python实现二叉树,二叉树中每个节点都是Node类对象,通过Tree类中的add()方法逐个向二叉树中加入树节点,构成完全二叉树或者非完全二叉树,代码如下:

class Node(object):
    """
    树节点类，用于构建二叉树。
    
    Attributes:
    - val: 节点存储的值。
    - right: 右子节点的引用。
    - left: 左子节点的引用。
    """
    def __init__(self, val=None, right=None, left=None):
        self.val = val  # 初始化节点值
        self.left = left  # 初始化左子节点为None
        self.right = right  # 初始化右子节点为None

class Tree(object):
    """
    树类，用于管理二叉树。
    
    Attributes:
    - root: 树的根节点。
    """
    def __init__(self, node=None):
        self.root = node  # 初始化树的根节点为None或传入的节点

    def add(self, item=None):
        """
        向树中添加一个新的节点。
        
        Args:
        - item: 新节点的值。
        """
        node = Node(val=item)  # 创建一个新的节点
        if not self.root or self.root.val is None:  # 如果树为空或根节点值为None
            self.root = node  # 将新节点设置为根节点
        else:
            queue = []  # 使用队列来实现层序遍历
            queue.append(self.root)  # 将根节点加入队列
            while True:  # 循环直到找到合适的插入位置
                current_node = queue.pop(0)  # 从队列中取出一个节点
                if current_node.val is None:  # 如果当前节点值为None，跳过
                    continue
                if not current_node.left:  # 如果当前节点的左子节点为空
                    current_node.left = node  # 将新节点设置为左子节点
                    return  # 返回，结束添加操作
                elif not current_node.right:  # 如果当前节点的右子节点为空
                    current_node.right = node  # 将新节点设置为右子节点
                    return  # 返回，结束添加操作
                else:  # 如果当前节点的左右子节点都不为空
                    queue.append(current_node.left)  # 将左子节点加入队列
                    queue.append(current_node.right)  # 将右子节点加入队列

接下来使用自定义二叉树类,将得到一棵二叉树:

tree = Tree()
for i in range(10):
    if i == 3:
        i = None
    tree.add(i)

原文地址：https://blog.csdn.net/pianmian1/article/details/143649454

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！