树的概念
树（英语：tree）是一种抽象数据类型（ADT）或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：        1. 每个节点有 零个或多个子节点；2. 没有父节点的节点称为根节点；3.每一个非根节点有且只有一个父节点；4.除了根节点外，每个子节点可以分为多个不相交的子树；


二叉树
每个节点最多含有两个子树的树称为二叉树，下面直接上代码：

[Python] 纯文本查看 复制代码

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()

树的概念
树（英语：tree）是一种抽象数据类型（ADT）或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：        1. 每个节点有 零个或多个子节点；2. 没有父节点的节点称为根节点；3.每一个非根节点有且只有一个父节点；4.除了根节点外，每个子节点可以分为多个不相交的子树；


二叉树
每个节点最多含有两个子树的树称为二叉树，下面直接上代码：

[Python] 纯文本查看 复制代码

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()