二叉树的定义初始化创建

二叉树是一种树形结构，其中每个结点最多有两个子结点，分别称为左子结点和右子结点。下面是二叉树的定义、初始化和创建的方法：

1.定义二叉树结点类BTNode，包含数据data和左右子结点指针lchild和rchild：

class BTNode:
    def __init__(self, data):
        self.data = data
        self.lchild = None
        self.rchild = None

2.定义二叉树类BinaryTree，包含头结点root和各种操作函数：

class BinaryTree:
    def __init__(self):
        self.root = None

    # 创建二叉树
    def create(self, data):
        if not data:
            return None
        self.root = BTNode(data[0])
        queue = [self.root]
        front = 0
        index = 1
        while index < len(data):
            node = queue[front]
            front += 1
            if data[index] != None:
                node.lchild = BTNode(data[index])
                queue.append(node.lchild)
            else:
                node.lchild = None
                queue.append(None)
            index += 1
            if index == len(data):
                break
            if data[index] != None:
                node.rchild = BTNode(data[index])
                queue.append(node.rchild)
            else:
                node.rchild = None
                queue.append(None)
            index += 1
    # 遍历二叉树
    def pre_order(self, root):
        if root == None:
            return
        print(root.data, end=' ')
        self.pre_order(root.lchild)
        self.pre_order(root.rchild)

    def in_order(self, root):
        if root == None:
            return
        self.in_order(root.lchild)
        print(root.data, end=' ')
        self.in_order(root.rchild)

    def post_order(self, root):
        if root == None:
            return
        self.post_order(root.lchild)
        self.post_order(root.rchild)
        print(root.data, end=' ')

    # 求二叉树的结点个数
    def get_node_num(self, root):
        if root == None:
            return 0
        return 1 + self.get_node_num(root.lchild) + self.get_node_num(root.rchild)

    # 求二叉树的叶子结点个数
    def get_leaf_num(self, root):
        if root == None:
            return 0
        if root.lchild == None and root.rchild == None:
            return 1
        return self.get_leaf_num(root.lchild) + self.get_leaf_num(root.rchild)

    # 求二叉树的深度
    def get_depth(self, root):
        if root == None:
            return 0
        left_depth = self.get_depth(root.lchild)
        right_depth = self.get_depth(root.rchild)
        return max(left_depth, right_depth) + 1

3.创建二叉树对象并调用create函数初始化：

tree = BinaryTree()
data = [1, 2, 3, 4, None, 5, 6, None, None, None, None, 7, None, None, None]
tree.create(data)