python - 树

python - 树

树：多个有层次的节点的集合

特点：

1. 每个节点有零个或多个子节点
2. 没有父节点的节点称为根节点
3. 每一个非根节点有且只有一个父节点
4. 除了根节点外，每个子节点可以分为多个不相交的子树

术语：

1. 节点的度：一个节点含有的子树的个数称为该节点的度
2. 树的度：一棵树中，最大的节点的度称为树的度
3. 叶节点或终端节点：度为零的节点
4. 父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点
5. 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点
6. 兄弟节点：具有相同父节点的节点互称为兄弟节点
7. 层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推
8. 高度或深度：树中节点的最大层次
9. 堂兄弟节点：父节点在同一层的节点互为堂兄弟
10. 节点的祖先：从根到该节点所经分支上的所有节点
11. 子孙：以某节点为根的子树中任一节点都称为该节点的子孙
12. 森林：由m（m>=0）棵互不相交的树的集合称为森林

种类：

1. 无序树：树中任意节点的子节点之间没有顺序关系
2. 有序树：树中任意节点的子节点之间有顺序关系
   • 二叉树：每个节点最多含有两个子树的树称为二叉树
     • 完全二叉树：对于一颗二叉树，假设其深度为d。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列
     • 平衡二叉树：当且仅当任何节点的两棵子树的高度差不大于1的二叉树；
     • 排序二叉树，也称二叉搜索树、有序二叉树
   • 霍夫曼树：带权路径最短的二叉树称为哈夫曼树或最优二叉树
   • B树：一种对读写 *** 作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多余两个子树

二叉树：

结构如图示： 

树，由多个节点构成，节点 = 元素 + 左子节点 + 右子节点

树的创建和遍历：

遍历 = 广度遍历 + 深度遍历

广度遍历：从左往右挨个遍历

深度遍历  = 先序 + 中序 + 后序

先序：根 - 左 - 右

中序：左 - 根 - 右

后序：左 - 右 - 根

无论是哪种遍历方式，左一定在右前面

# coding:utf-8
# 创建二叉树

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):
        '''先序'''
        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=" ")