树和二叉树

# 二叉树中元素添加

class Node(object):
    def __init__(self,item):
        # 定义节点的左右子树
        self.elem = item
        self.lchild = None
        self.rchild = None
        
class Tree(object):   
    # 树类
    def __init__(self):
        # 定义树类
        self.root = None
        
    def add(self, item):
        # 实例化一个节点
        node = Node(item)
        # 如果根节点是空的，直接添加元素
        if self.root is None:
            self.root = node
            return 
        # 定义队列来存放元素，首先是根节点
        queue = [self.root]
        
        # 循环条件：队列是否为空
        while queue:
            # 通过队列来实现，一端进另一端出，先进先出
            # 删除首位元素
            cur_node = queue.pop(0)
            # 判断左右子树是否为空，是的话直接追加，不是则追到队列末尾
            if cur_node.lchild is None:
                cur_node.lchild = node
                return 
            else:
                queue.append(cur_node.lchild)

            if cur_node.rchild is None:
                cur_node.rchild = node
                return 
            else:
                queue.append(cur_node.rchild)
                
    def breadth_travel(self):
        # 广度遍历
        
        # 处理空的根节点
        if self.root is None:
            return
        
        # 非空节点通过队列来处理
        queue = [self.root]
        while queue:
            cur_node = queue.pop(0)
            print(cur_node.elem, end=" ")
            if cur_node.lchild is not None:
                queue.append(cur_node.lchild)
            if cur_node.rchild is not None:
                queue.append(cur_node.rchild)
                
                
    def preorder(self, node):
        # 先序遍历
        
        # 如果传进的节点是Node，说明是叶子节点，不必再进行遍历
        if node is None:
            return 
        print(node.elem, end=" ")
        
        # 处理根节点的左右子树
        self.preorder(node.lchild)
        self.preorder(node.rchild)
    
    def inorder(self, node):
        # 中序遍历
        # 只需要调整打印和两次递归调用的顺序，
        # 调用的是函数自身
        if node is None:
            return 
        # 左根右
        self.inorder(node.lchild)
        print(node.elem, end=" ")
        self.inorder(node.rchild) 
    
    def postorder(self, node):
        # 后序遍历
        if node is None:
            return 
        # 左右根
        self.postorder(node.lchild)
        self.postorder(node.rchild) 
        print(node.elem, end=" ")
                
if __name__ == "__main__":
    tree = Tree()
    # 添加的顺序和遍历出来的顺序是一样的
    tree.add(0)
    tree.add(1)
    tree.add(2)
    tree.add(3)
    tree.add(4)
    tree.add(5)
    tree.add(6)
    tree.add(7)
    tree.add(8)
    tree.add(9)
    tree.breadth_travel()
    print(" ")
    tree.preorder(tree.root)
    print(" ")
    tree.inorder(tree.root)
    print(" ")
    tree.postorder(tree.root)
    print(" ")

# res
0 1 2 3 4 5 6 7 8 9  
0 1 3 7 8 4 9 2 5 6  
7 3 8 1 9 4 0 5 2 6  
7 8 3 9 4 1 5 6 2 0