树的基础知识

# 树节点的定义
class Node(object):
    def __init__(self, val=None, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 三种遍历方式
class Travaltree(object):
    def __init__(self):
        self.res = []

    def preorder(self, root):
        if root is None:
            return
        self.res.append(root.val)
        self.preorder(root.left)
        self.preorder(root.right)
        return self.res

    def inorder(self, root):
        if root is None:
            return
        self.inorder(root.left)
        self.res.append(root.val)
        self.inorder(root.right)
        return self.res

    def postorder(self, root):
        if root is None:
            return
        self.postorder(root.left)
        self.postorder(root.right)
        self.res.append(root.val)
        return self.res

 # 二叉搜索树的构建、插入节点的函数
def insert(root, val):
    newnode = Node(val)
    if root is None:
        root = newnode
    else:
        temp = root
        while temp is not None:
            if val < temp.val:
                if temp.left is None:
                    temp.left = newnode
                    return root
                else:
                    temp = temp.left
            else:
                if temp.right is None:
                    temp.right = newnode
                    return root
                else:
                    temp = temp.right
    return root

# 二叉搜索树的构建
def build_binary_search_tree(arr):
    tree = None
    for item in arr:
        tree = insert(tree, item)
    return tree

# 获取树的最大高度
def get_height(root):
    if root is None:
        return 0
    return max(get_height(root.left), get_height(root.right)) + 1

# 获取树中最大的值
def get_max(root):
    if root is None:
        return float("-inf")
    if root.left is None and root.right is None:
        return root.val
    left_max = get_max(root.left)
    right_max = get_max(root.right)
    max_ = max(left_max, right_max)
    max_ = max(max_, root.val)
    return max_

arr = [6, 3, 8, 2, 5, 1, 7]
tree = build_binary_search_tree(arr)

travaltree = Travaltree()
preres = travaltree.preorder(tree)

travaltree.res = []
inres = travaltree.inorder(tree)

travaltree.res = []
postres = travaltree.postorder(tree)

print(preres)
print(inres)
print(postres)

height = get_height(tree)
print(height)

max_ = get_max(tree)
print(max_)