二叉树的类实现（python语言）

红太狼 2022-05-23 09:57 149阅读 0赞

# -*- coding: UTF-8 -*-
    
    
    class BinTNode:  # 定义一个二叉树节点类
        def __init__(self, dat, left=None, right=None):
            self.data = dat  # 节点数据
            self.left = left  # 左子节点
            self.right = right  # 右子节点
    
    
    def count_bin_t_node(t):  # 统计树中节点的个数
        if t is None:
            return
        else:
            return 1 + count_bin_t_node(t.left) + count_bin_t_node(t.right)
    
    
    def sum_bin_t_node(t):  # 计算二叉树中所有节点的和
        if t is None:
            return 0
        else:
            return t.dat + sum_bin_t_node(t.left) + sum_bin_t_node(t.right)
    
    
    # 递归定义遍历函数
    def preorder(t, proc):  # 按先根序遍历二叉树（proc是具体的节点数据操作）
        if t is None:
            return
        proc(t.data)
        preorder(t.left)
        preorder(t.right)
    
    
    def print_bin_t_nodes(t):
        if t is None:
            print('^', end='')
            return
        print('(' + str(t.data), end='')
        print_bin_t_nodes(t.left)
        print_bin_t_nodes(t.right)
        print(")", end='')
    
    
    # 宽度优先遍历函数
    from SQueue import *
    
    
    def level_order(t, proc):
        qu = SQueue()
        qu.enqueue(t)
        while not qu.is_empty():
            n = qu.dequeue()
            if t is None:  # 弹出的树为空则直接跳过
                continue
            qu.enqueue(t.left)
            qu.enqueue(t.right)
            proc(t.data)
    
    
    # 非递归的先根序遍历函数
    def preorder_nonrec(t, proc):
        s = SStack
        while t is not None or not s.is_empty:
            while t is not None:  # 沿左分支下行
                proc(t.data)  # 先根序先处理根数据
                s.push(t.right)  # 右分支入栈
                t = t.left
            t = t.pop()  # 遇到空树，回溯
    
    
    # 通过生成器函数遍历
    def preorder_elements(t):
        s = SStack
        while t is not None or not s.is_empty():
            while t is not None:
                s.push(t.right)
                yield t.data
                t = left
            t = s.pop()
    
    
    # 非递归的后根序遍历算法
    def postorder_nonrec(t, proc):
        s =SStack()
        while t is not None or not s.is_empty():
            while t is not None:  # 下行循环，直到栈顶的两子树空
                s.push()
                t = t.left if t.left is not None else t.right  # 能左就左，否则向右一步
    
            t = s.pop()  # 栈顶是应访问节点
            proc(t, data)
            if not s.is_empty() and s.top().left ==t:
                t = s.top().right()  # 栈不空且当前节点是栈顶的左子节点
            else:
                t = None  # 没有右子树或右子树遍历完毕，强迫退栈
    
    
    # 二叉树类定义
    def BinTree:
        def __init__(self):
            self._root = None
    
        def is_empty(self):
            return self._root is None
    
        def root(self):
            return self._root
    
        def left_child(self):
            return self._root.left
    
        def right_child(self):
            return self._root.right
    
        def set_root(self, root_node):
            self._root = root_node
    
        def self_left(self, root_child):
            self._root.left = left_child
    
        def self_right(self, right_child):
            self._rootright = right_child
    
        def preorder_elements(self):  # 元素迭代器
            t, s = self._root, SStack()
            while t is not None or not s.is_empty():
                s.push(t.right)
                yield t.data  # 函数返回一个t.data生成器
                t = t.left
            t = s.pop()