二叉树及其遍历

• 二叉树:每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）
• 完全二叉树:若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树
• 满二叉树:除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。

class Node(object):

    def __init__(self, item):
        self.item = 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
        else:
            # 从上到下，从左往右 使用队列
            queue = []
            queue.append(self.root)

            while queue:
                child = queue.pop(0)
                if child.lChild is None:
                    child.lChild = node
                    return
                if child.rChild is None:
                    child.rChild = node
                    return
                queue.append(child.lChild)
                queue.append(child.rChild)

深度优先一般用递归
广度优先一般用队列
一般情况下能用递归实现的算法大部分也能用堆栈来实现。

    # 广度优先遍历，层次遍历
    def breath_travel(self):

        if self.root is None:
            return
        queue = []
        queue.append(self.root)

        while queue:

            node = queue.pop(0)
            print(node.item, end=" ")

            if node.lChild is not None:
                queue.append(node.lChild)
            if node.rChild is not None:
                queue.append(node.rChild)

    # 深度优先遍历
    def depth_travel(self):
        self.post_order(self.root)
        print()

    # 先序 自己 左子树 右子树
    def pre_order(self, node):
        if node is None:
            return
        print(node.item, end=" ")
        self.pre_order(node.lChild)
        self.pre_order(node.rChild)

    # 中序  左子树 自己 右子树
    def in_order(self, node):
        if node is None:
            return
        self.in_order(node.lChild)
        print(node.item, end=" ")
        self.in_order(node.rChild)

    # 后序  左子树  右子树  自己
    def post_order(self, node):
        if node is None:
            return
        self.post_order(node.lChild)
        self.post_order(node.rChild)
        print(node.item, 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.breath_travel()
    tree.depth_travel()