python实现二叉树

概念：二叉树是指模拟的树状结构，每个节点最多有两个子树的树结构，即左子树和右子树的数据集合【可以看成是对链表的一个扩充】

1.1 python实现二叉树

1.1.1 构造节点

• 类似链表节点的构造方法
• 初始时左右节点分别为None
• elem属性等于传入的item值

class Node(object):
    def __init__(self,item):
        """定义当前节点和左右子节点"""
        self.elem = item
        self.lchild = None  # 左节点
        self.rchild = None  # 右节点

1.1.2 构造方法

• 构造根节点，初始值设置为None
• 区别于链表的构造方法，不需要设置为私有属性，构造时不传入参数【即创建空树】 tree = Tree()

class Tree(object):
    
    def __init__(self):
        # 区别于链表的私有属性
        # 构造时使用tree = Tree()即可
        self.root = None

1.1.3 add方法

• 使用队列的思想进行添加，在队列中不断地添加和取出需要遍历的节点，逐个判断，将新节点添加到遍历到的空节点上
• 当根节点为None时，直接将需要添加的节点作为根节点
  当根节点不为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)
            # 左节点为空时，则直接添加node到左节点
            if cur_node.lchild is None:
                cur_node.lchile = node
                return 
            else:
                queue.append(cur_node.lchild)
            # 右节点为空时，则添加node到右节点
            if cur_node.rchild is None:
                cur_node.rchild = node
                return
            else:
                queue.append(cur_node.rchild)

1.1.4 遍历

• 层次遍历：一层一层进行遍历，与add思路相同
• 先序遍历：按 根 --> 左节点 --> 右节点 进行遍历，使用递归思想【node代表传入的根节点】
• 中序遍历：左节点 --> 根 --> 右节点
• 后序遍历：左 --> 右 --> 根

def breadth_travel(self):
        """广度遍历 -- 层次遍历，与add思路相同"""
        if self.root is None:
            return
        queue = [self.root]
        while queue:
            cur_node = queue.pop(0)
            print(cur_node.elem)
            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)
        
        self.preorder(node.lchild)   # 遍历左节点
        
        self.preorder(node.rchild)   # 遍历右节点
    
    def inorder(self,node):
        # 中序遍历  左 -> 根 -> 右
        if node is None:
            return 
        self.inorder(node.lchild)
        print(node.elem)
        self.inorder(node.rchild)
    
    def postorder(self,node):
        # 后序遍历   左 -> 右 -> 根
        if node is None:
            return 
        self.postorder(node.lchild)
        self.postorder(node.rchild)
        print(node.elem)
    

---

1.2 完整代码

class Node(object):
    def __init__(self,item):
        """定义当前节点和左右子节点"""
        self.elem = item
        self.lchild = None  # 左节点
        self.rchild = None  # 右节点

class Tree(object):
    
    def __init__(self):
        # 区别于链表的私有属性
        # 构造时使用tree = Tree()即可
        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)
            # 左节点为空时，则直接添加node到左节点
            if cur_node.lchild is None:
                cur_node.lchile = node
                return 
            else:
                queue.append(cur_node.lchild)
            # 右节点为空时，则添加node到右节点
            if cur_node.rchild is None:
                cur_node.rchild = node
                return
            else:
                queue.append(cur_node.rchild)
                
    def breadth_travel(self):
        """广度遍历 -- 层次遍历，与add思路相同"""
        if self.root is None:
            return
        queue = [self.root]
        while queue:
            cur_node = queue.pop(0)
            print(cur_node.elem)
            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)
        
        self.preorder(node.lchild)   # 遍历左节点
        
        self.preorder(node.rchild)   # 遍历右节点
    
    def inorder(self,node):
        # 中序遍历  左 -> 根 -> 右
        if node is None:
            return 
        self.inorder(node.lchild)
        print(node.elem)
        self.inorder(node.rchild)
    
    def postorder(self,node):
        # 后序遍历   左 -> 右 -> 根
        if node is None:
            return 
        self.postorder(node.lchild)
        self.postorder(node.rchild)
        print(node.elem)