11-树

一、树

1.概念

• 树是一种典型的非线性结构
• 特点：
  1. 每个节点都有零个或多个子节点
  2. 没有父节点的节点称为根节点
  3. 每一个非根节点都有且只有一个父节点
  4. 除了根节点外，每个子节点都可以分为多个不相交的子树

2.术语

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

3.树的种类及存储

1）树的种类

• 无序树：树中任意节点的子节点之间没有顺序关系
• 有序树：
  • 霍夫曼树（用于信息编码）：带权路径最短的二叉树称为哈夫曼树或最优二叉树
  • B树：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多于两个的子树

2）二叉树

• 每个节点最多含有两个子树的树称为二叉树
• 完全二叉树：
  • 对于一颗二叉树，假设其深度为d(d>1)。除了第d层外，其它各层的节点数目均已达最大值
  • 且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树
• 满二叉树的定义是所有叶节点都在最底层的完全二叉树

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4FgQ0Mnl-1604975476238)(C:\Users\lzq\AppData\Roaming\Typora\typora-user-images\image-20200908151247899.png)]

• 平衡二叉树：当且仅当任意节点的子树层数相差不大于1的二叉树
• 排序二叉树（二叉查找树、有序二叉树）：
  • 1.若左子树不空，则左子树上所有节点的值均小于它的根节点的值
  • 2.若右子树不空，则右子树上所有节点的值均大于它的根节点的值
  • 3.左、右子树也分别为二叉排序树

3）二叉树的存储

顺序存储：将数据结构存储在固定的数组中

链式存储：每个节点有一个元素域和两个指针域

4.二叉树的概念和性质

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-V6ZBT8Gg-1604975476239)(C:\Users\lzq\AppData\Roaming\Typora\typora-user-images\image-20200908155515486.png)]

二、二叉树的遍历

1.二叉树的代码实现

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

        
class BinaryTree(object):
    """二叉树类"""
    def __init__(self, node = None):
        self.root = node

    def add(self, item):
        """添加节点"""
        if self.root is None:
            self.root = None(item)
        # 定义对列
        queue = []
        # 从尾部添加数据
        queue.append(self.root)
        while True:
            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)

           

2.广度优先遍历

def breadth_travel(self):
        """广度优先遍历"""
        if self.root is None:
            return
        # 定义对列
        queue = []
        # 从尾部添加数据
        queue.append(self.root)
        while len(queue) > 0:
            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)
           

3.深度优先遍历

先序：根 左 右

def preorder(self, root):
        """深度优先先序遍历"""
		if root is None:
			return
        print(root.item)
        self.preorder(root.lchild)
        self.preorder(root.rchild)
           

中序：左 根 右

def inorder(self, root):
        """深度优先中序遍历"""
        if root is None:
            return
        self.preorder(root.lchild)
        print(root.item)
        self.preorder(root.rchild)
           

后序：左 右 根

def postorder(self, root):
        """深度优先后序遍历"""
        if root is None:
            return
        self.preorder(root.lchild)
        self.preorder(root.rchild)
        print(root.item)
           

4.由遍历结果反推二叉树

• 根据 中序遍历 和 先序遍历或后序遍历 来反推二叉树

n

self.preorder(root.lchild)

self.preorder(root.rchild)

print(root.item)

## 4.由遍历结果反推二叉树

- 根据 **中序遍历** 和 **先序遍历或后序遍历** 来反推二叉树