二叉树的创建与遍历

二叉树

二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）

class Node(object):
    """二叉树节点类"""
    def __init__(self,item):
        self.item = item
        self.lchild = None
        self.rchild = None


class BinaryTree(object):
    """二叉树"""
    def __init__(self,node = None):
   		# 初始的时候二叉树是空的根节点指向None
        self.root = node

    def add(self,item):
        """
        广度优先遍历方式添加节点
        :param item:
        :return:
        """
        # 如果没有根节点，添加的节点就是根节点
        if self.root is None:
            self.root = Node(item)
            return
        # 创建一个空列表用于当做队列模式
        queue = list()
        # 将根节点添加到列表
        queue.append(self.root)
        while len(queue) > 0:
            # 取列表中的第一个节点
            node = queue.pop(0)
            # 如果这个节点没有左子节点把添加的节点放在这个节点的左子节点位置,添加完成
            if node.lchild is None:
                node.lchild = Node(item)
                return
            else:
                # 否则将这个节点的左子节点添加到列表尾部
                queue.append(node.lchild)
            # 如果这个节点没有右子节点把添加的节点放在这个节点的右子节点位置，添加完成
            if node.rchild is None:
                node.rchild = Node(item)
                return
            else:
                # 否则将这个节点添加到列表尾部
                queue.append(node.rchild)

    def breadh_travel(self):
        """广度优先遍历"""
        # 如果根节点不存在不用遍历了
        if not self.root:
            return
        # 创建一个列表用于用队列存放节点，在依次取出节点并打印
        queue = list()
        # 添加根节点
        queue.append(self.root)
        # 循环遍历直到列表里面没有数据
        while len(queue) > 0:
            # 取出先添加的节点
            node = queue.pop(0)
            # 打印在前面的节点
            print(node.item,end=" ")
            # 如果这个节点有左子节点
            if node.lchild:
                # 将这个左子节点添加到列表尾部
                queue.append(node.lchild)
            # 如果这个节点有右子节点
            if node.rchild:
                # 将这个右子节点添加到列表尾部
                queue.append(node.rchild)

    def preordef_travel(self,root):
        """先序遍历  根  左  右  """
        # 如果节点存在的话
        if root:
            # 打印这个节点的数值
            print(root.item,end=" ")
            # 将这个节点的左子节点调有这个先序方法继续遍历
            self.preordef_travel(root.lchild)
            # 将这个节点的右子节点调有这个先序方法继续遍历
            self.preordef_travel(root.rchild)

    def inordef_travel(self,root):
        """中序遍历   左  根  右  """
        # 如果节点存在的话
        if root:
            # 将这个节点的左子节点调有这个中序方法继续遍历
            self.inordef_travel(root.lchild)
            # 打印这个节点的数值
            print(root.item, end=" ")
            # 将这个节点的右子节点调有这个中序方法继续遍历
            self.inordef_travel(root.rchild)

    def postordef_travel(self,root):
        """后序遍历  左  右  根  """
        # 如果节点存在的话
        if root:
            # 将这个节点的左子节点调有这个后序方法继续遍历
            self.postordef_travel(root.lchild)
            # 将这个节点的右子节点调有这个后序方法继续遍历
            self.postordef_travel(root.rchild)
            # 打印这个节点的数值
            print(root.item, end=" ")


if __name__ == '__main__':
    # node = ErChaShu()
    node = BinaryTree()
    node.add(0)
    node.add(1)
    node.add(2)
    node.add(3)
    node.add(4)
    node.add(5)
    node.add(6)
    node.add(7)
    node.add(8)
    node.add(9)
    node.breadh_travel()
    print()
    node.preordef_travel(node.root)
    print()
    node.inordef_travel(node.root)
    print()
    node.postordef_travel(node.root)

           

遍历的原理