[数据结构与算法]2021-07-22

二叉树

用list形式表示二叉树吧btree[0]表示结点数据，btree[1]表示左子树，btree[2]表示右子树。里面就是列表套列表……这里完全没必要用类了，就用一些方法就行了，构造成一个类挺麻烦的，应该也能行。

def BinTree(data, left=None, right=None):
    return [data, left, right]


def is_empty_BinTree(btree):
    return btree is None


def root(btree):
    return btree[0]


def left(btree):
    return btree[1]


def right(btree):
    return btree[2]

def set_root(btree, data):
    btree[0] = data


def set_left(btree, data):
    btree[1] = data


def set_right(btree, right):
    btree[2] = right


if __name__ == '__main__':
    tree = BinTree(2, BinTree(4), BinTree(8))
    print(tree)
    set_left(left(tree), BinTree(5))
    print(tree)

结果:
[2, [4, None, None], [8, None, None]]
[2, [4, [5, None, None], None], [8, None, None]]

二叉树类（这个是重点）

from stack.SStack import SStack


class BinTNode(object):
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right


class BinTree(object):                        # 基于链表模式实现二叉树
    def __init__(self):
        self._root = None

    def is_empty(self):                       # 二叉树为空
        return self._root is None

    def root(self):
        return self._root

    def leftchind(self):
        return self._root.left

    def rightchind(self):
        return self._root.right

    def set_root(self, rootnode):
        self._root = rootnode

    def set_left(self, leftchild):
        self._root.left = leftchild

    def set_right(self, rightchild):
        self._root.right = rightchild

    def preorder_elements(self):
        t, s = self._root, SStack()
        while t is not None or not s.is_empty():
            while t is not None:
                s.push(t.right)
                yield t.data
                t = t.left
            t = s.pop()


def preorder(t):                                            # 根序遍历
    if t is None:
        return
    print(t.data, end=' ')
    preorder(t.left)
    preorder(t.right)


def print_BinNode(t):                                        # 输出这棵树
    if t is None:
        print("^", end='')                                   # 空树输出^
        return
    print("(" + str(t.data), end='')
    print_BinNode(t.left)
    print_BinNode(t.right)
    print(")", end='')


def count_BinTNodes(t):                                # 统计结点的个数
    if t is None:
        return 0
    else:
        return 1 + count_BinTNodes(t.left) + count_BinTNodes(t.left)


def sum_BinTNode(t):                                  # 计算结点中的所有数值
    if t is None:
        return 0
    else:
        return t.data + sum_BinTNode(t.left) + sum_BinTNode(t.right)


if __name__ == '__main__':
    tree1 = BinTree()
    tree1.set_root(BinTNode(1))

    tree2 = BinTree()
    tree2.set_root(BinTNode(2))
    tree2.set_left(BinTNode(4))
    tree2.set_right(BinTNode(5))

    tree3 = BinTree()
    tree3.set_root(BinTNode(3))
    tree3.set_left(BinTNode(6))
    tree3.set_right(BinTNode(7))

    tree1.set_left(tree2.root())
    tree1.set_right(tree3.root())

    print_BinNode(tree2.root())
    print()
    print_BinNode(tree3.root())
    print()
    print_BinNode(tree1.root())
    print()

    count = count_BinTNodes(tree1.root())
    sum = sum_BinTNode(tree1.root())

    print(count)
    print(sum)
    preorder(tree1.root())

结果：
(2(4^^)(5^^))
(3(6^^)(7^^))
(1(2(4^^)(5^^))(3(6^^)(7^^)))
7
28
1 2 4 5 3 6 7 

我是创建了tree2和tree3再把他们添加给tree1的，成为tree的左右子树。其他的懒得罗嗦了，反正没人看……这是我的简单总结。