python 实现二叉树

树:
树结构的例子就是你可能每天都会用到的文件系统。在一个文件系统中,磁盘的分支或
者文件夹构建成了一棵树。

二叉树的基本概念

二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)

理解:

二叉树作为一个Python中的典型,其实质就是一个分叉形式的数组,以一个节点开始,每次延伸出两个左右子节点,无限延伸直到没有子节点。

这些节点看似散乱,实际上是可以根据某种规律来按顺序读出来的,这就可以看做是一种专门的读取方法。假设最上级是一个总文件夹,后面的内容都是文件夹的下一级,二叉树的遍历方式就可以稳当的读出所有文件。

二叉树的性质(特性)
性质1: 在二叉树的第i层上至多有2^(i-1)个结点(i>0)
性质2: 深度为k的二叉树至多有2^k - 1个结点(k>0)
性质3: 对于任意一棵二叉树,如果其叶结点数为N0,而度数为2的结点总数为N2,则N0=N2+1;
性质4:具有n个结点的完全二叉树的深度必为 log2(n+1)
性质5:对完全二叉树,若从上至下、从左至右编号,则编号为i 的结点,其左孩子编号必为2i,其右孩子编号必为2i+1;其双亲的编号必为i/2(i=1 时为根,除外)

1)完全二叉树——若设二叉树的高度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第h层有叶子结点,并且叶子结点都是从左到右依次排布,这就是完全二叉树。

在这里插入图片描述

(2)满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。
在这里插入图片描述

二叉树的节点表示以及树的创建
通过使用Node类中定义三个属性,分别为elem本身的值,还有lchild左孩子和rchild右孩子
节点。

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

树的创建,创建一个树的类,并给一个root根节点,一开始为空,随后添加节点

class Tree(object):
    """树类"""
    def __init__(self, root=None):
        self.root = root

    def add(self, elem):
        """为树添加节点"""
        node = Node(elem)
        #如果树是空的,则对根节点赋值
        if self.root == None:
            self.root = node
        else:
            queue = []
            queue.append(self.root)
            #对已有的节点进行层次遍历
            while queue:
                #弹出队列的第一个元素
                cur = queue.pop(0)
                if cur.lchild == None:
                    cur.lchild = node
                    return
                elif cur.rchild == None:
                    cur.rchild = node
                    return
                else:
                    #如果左右子树都不为空,加入队列继续判断
                    queue.append(cur.lchild)
                    queue.append(cur.rchild)

二叉树的遍历

树的遍历是树的一种重要的运算。所谓遍历是指对树中所有结点的信息的访问,即依次对树中每个结点访问一次且仅访问一次,我们把这种对所有节点的访问称为遍历(traversal)。那么树的两种重要的遍历模式是深度优先遍历和广度优先遍历,
**深度优先一般用递归,广度优先一般用队列。**一般情况下能用递归实现的算法大部分也能用堆栈来实现。

深度优先遍历

对于一颗二叉树,深度优先搜索(Depth First Search)是沿着树的深度遍历树的节点,尽可能深的搜索树的分支。
那么深度遍历有重要的三种方法。这三种方式常被用于访问树的节点,它们之间的不同在于访问每个节点的次序不同。这三种遍历分别叫做先序遍历(preorder),中序遍历(inorder)和后序遍历(postorder)。我们来给出它们的详细定义,然后举例看看它们的应用。
先序遍历
在先序遍历中,我们先访问根节点,然后递归使用先序遍历访问左子树,再递归使用先序遍历访问右子树
根节点->左子树->右子树
A
↙ ↘
B C
↙ ↘ ↙ ↘
D E F G
前序:先把BDF,CFG看做是A的左右子节点,因此是从A开始读,A作为第一个,然后进到左子节点 BDE, 这时再把它看做一个小二叉树看待,其
顺序为BDF,读完这个,以A为根的三个结构就读完了根左,然后剩下CFG,这时在读CFG。到此为止,这组二叉树的前序组合为ABDRCFG,这种读法
从上往下,从根开始,把下面所有节点结构都以根左右的形式读取。就上上面讲的 根–左--右

def preorder(self, root):
      """递归实现先序遍历"""
      if root == None:
          return
      print (root.elem)
      self.preorder(root.lchild)
      self.preorder(root.rchild)

中序遍历
在中序遍历中,我们递归使用中序遍历访问左子树,然后访问根节点,最后再递归使用中序遍历访问右子树
左子树->根节点->右子树
上图:
先把BDF,CFG看做是A的左右子节点,A1,A2。中序的读法为左根右,A1,A,A2。然后再看A1,D为左,B为中,E为右,D为叶节点
(无子节点了),因此从D开始DBE,A1读完,然后为A,再看A2,A2为FCG,因此中序的顺序为:DBE>A>FCG。

def inorder(self, root):
      """递归实现中序遍历"""
      if root == None:
          return
      self.inorder(root.lchild)
      print (root.elem)
      self.inorder(root.rchild)

后序遍历
在后序遍历中,我们先递归使用后序遍历访问左子树和右子树,最后访问根节点
左子树->右子树->根节点

后序:左右根,A1,A2,A。A1在左右根:DEB,A2是FGC,A1,A2,A
便是DEBFGCA。

def postorder(self, root):
      """递归实现后续遍历"""
      if root == None:
          return
      self.postorder(root.lchild)
      self.postorder(root.rchild)
      print (root.elem)

在这里插入图片描述

广度优先遍历(层次遍历)
从树的root开始,从上到下从从左到右遍历整个树的节点

def breadth_travel(self, root):
        """利用队列实现树的层次遍历"""
        if root == None:
            return
        queue = []
        queue.append(root)
        while queue:
            node = queue.pop(0)
            print node.elem,
            if node.lchild != None:
                queue.append(node.lchild)
            if node.rchild != None:
                queue.append(node.rchild)
版权声明:本文为weixin_43096365原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_43096365/article/details/97640753