二叉树

每个节点最多含有两个子树称为二叉树

image.png

性质

  • 在二叉树的第i层上至多有2**i-1**个结点（i>0）

  • 深度为k的二叉树至多有n=2**k - 1**个结点（k>0）

  • n个结点的完全二叉树的深度为k= log2(n+1)

  • 叶子结点=度数为2的结点总数+1;

  • 完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，右孩子编号必为2i＋1；其双亲的编号必为i/2（i＝1 时为根,除外）

二叉树的实现

节点的创建

首先，根链表类似，要先定义节点，也就是每个树的叶子

因为二叉树中，每个节点上两个后继image.png，我们称为左孩子，右孩子

并且要有值的传入

  1. #定义一个二叉树节点的类
  3. class Node(object):
  4.     def __init__(self,item):#要输入数据
  5.         self.elem=item
  6.         self.lchild = None
  7.         self.rchild = None

树的创建

定义一个根节点即可，每个node都已经定义了左右节点

  1. class Tree(object):
  2.     def __init__(self):
  3.         self.root=None

添加元素

因为采用的是队列的思想
也就是，从树的根部开始，从左到右开始遍历
所以要定义queue队列，里面存放的是根节点

  • 利用Node的类将传入的值构造节点
  • 创建队列，并存放根节点
  • 找出队头，也就根节点用pop(0)
  • 判断找到的队头的左节点、右节点是否存在
  • 左节点是否存在
    • 不存在就是根节点
    • 存在，把它添加到队列中
  • 右节点是否存在
    • 不存在就是根节点
    • 存在，把它添加到队列中
  1. def add(self,item):
  2.     node=Node(item)
  3.     queue=[self.root]
  5.     cur_node=queue.pop(0)
  7.     while queue:
  8.         if cur_node.lchild is None:
  9.             cur_node=node
  10.         else:
  11.             queue.appned(cur_node.lchild)
  13.         if cur_node.rchild is None:
  14.             cur_node = node
  15.         else:
  16.             queue.append(cur_node.rchild)

特殊情况

queue=[self.root]，当self.root是空数None时

cur_node=queue.pop(0)返回就是None值[None]

此时的None值变成了根节点元素

所以当self.root== None，就直接返回成根节点

  1. def add(slef,item):
  2.     node=Node(item)
  4.     if self.root is None:
  5.         self.root=node
  7.     queue=[self.root]
  8.     while queue:
  9.         cur_node=queue.pop(0)
  10.         if cur_node.lchild is None:
  11.             cur_node=node
  12.             return
  13.         else:
  14.             queue.append(cur_node.lchidl)
  16.         if cur_node.rchild is None:
  17.             cur_node=node
  18.             return
  19.         else:
  20.             queue.append(cur_node.rchidl)

遍历

广度优先遍历（层次遍历）

与添加元素的思想一样，只不过需要，打印出节点

def breadth_travel(self):
    queue=[self.root]
    if self.root is None:
        return 
    while queue:
        cur_node=queue.pop(0)
        print(cur_node.elem)
        if cur_node.lchild is not None:
            queue.append(cur_node.lchild)
        if cur_node.rchild is not None:
            queue.append(cur_node.rchild)

深度优先遍历

  • 先序遍历：根节点—>左子树—>右子树
  • 中序遍历：右子树—>根节点—>右子树
  • 后序遍历：左子树—>右子树—>根节点

遍历的基本思想（注意考虑为空情况）

  1. 打印当前元素
  2. 递归遍历当前元素的左子树
  3. 递归遍历当前元素的右子树

其他的遍历方式，只是顺序不同

    print(node.elem)
    self.preorder(node.lchild)
    self.preorder(node.rchild)