Python实现二叉树的基础操作

布满荆棘的人生 2022-03-30 09:18 173阅读 0赞

本篇的主要内容：

*  Python实现二叉树的建立与遍历
 *  如何判断完全二叉树

最近遇到这个问题，要使用Python实现二叉树的一些操作，在网上这部分的资源不是很多，也没有找好很好的，只好按照自己的思路简单写了一下，本来算法是不局限于语言的，说是这么说，但是还是遇到了一些问题，在此梳理记录一下。

#### 二叉树建立 ####

首先定义二叉树的先序字符串，并使用`#`表示某个节点的子树为空的情况：

二叉树类的定义为：

class TreeNode:
        def __init__(self, x):
            self.val = x
            self.left = None
            self.right = None

创建二叉树：

pos = 0
    def create(seq):
        global pos
        ch = seq[pos]
        pos += 1
        if ch == '#':
            return None
        else:
            temp = TreeNode(ch)
            temp.left = create(seq)
            temp.right = create(seq)
            return temp
     
    seq = "abd###ce###"
    root = create(seq)

这里创建的二叉树形状为：

a
           /   \
          b     c
         /     /
        d     e

不过这里还要注意一个问题，在这里记录下来，提醒自己以后不要犯相同的错误，一开始我的创建树的代码是这样的：

def create(root):
        global pos
        if(seq[pos]=='#'):
            root = None
            pos += 1
            return
        root = TreeNode(seq[pos])
        pos += 1
        root.left = None
        root.right = None
        create(root.left)
        create(root.right)

这个创建的思路是我在C++写树的时候也经常用的方式，这里与上面的方式有点不同，上面对于创建的树节点全都是return回去的，而这里则没有，在C++中，这样创建也是可以的，因为使用引用作为参数的时候，所有的操作都是在一块内存上进行的，但是Python中却不是，改变了对象，那么这个引用指向的地址也会改变，这样上面的函数中所有的操作相当于只是在函数内有效，而外层是记录不到这一系列创建树的操作的，这里请看（[我的理解][Link 1]）。

#### 主要的几种遍历方式 ####

*  先序遍历、中序遍历以及后序遍历（这里使用递归方式，差别不大）

def pre_travel(root):
        if root:
            print(root.val, end=" ")
            pre_travel(root.left)
            pre_travel(root.right)
    def in_travel(root):
        if root:
            in_travel(root.left)
            print(root.val, end=" ")
            in_travel(root.right)
    def last_travel(root):
        if root:
            last_travel(root.left)
            last_travel(root.right)
            print(root.val, end=" ")

*  层次遍历（在C++中，实现层次遍历一般都会使用队列，在Python中队列这一数据结构直接使用列表就好了，pop对应的就是del(index)， push对应的就是append方法）

def level_travel(root):
        que = []
        if root is None:
            print("None.")
            return
        else:
            que.append(root)
        while len(que) != 0:
            temp = que[0]
            print(temp.val, end=" ")
            del(que[0])
            if temp.left:
                que.append(temp.left)
            if temp.right:
                que.append(temp.right)

#### 关于判断一棵树是否为完全二叉树 ####

这也是最近遇到的一个问题，在这里一块整理了：

首先要明确完全二叉树的概念，简单来说，就是二叉树的叶节点只出现在最下层和次下层，并且最下层的叶节点必须从左边依次出现，如果按照定义来进行判断，其实写起来还是有些麻烦的，主要是一些比较特殊的情况，判定条件不容易写，例如：

a
               / \
              b   c
             /   /
            d   e

我是觉得这种类似的树不是很好加判断，所以不如直接不使用这些条件，换种角度，如果将树进行遍历，那么完全二叉树的所有结非空结点都会是相邻的，所以我们不如直接将所有的结点遍历出来，如果出现了空结点，但是空结点之后还有非空结点，那么就不是完全二叉树了，当然这个过程要在层次遍历中进行，代码如下：

def judge(root):
        que = []
        que.append(root)
        while que[0] is not None:        # 整体就是层次遍历，不同之处是要保存空结点 这里结束的时候说明遇到了空结点
            que.append(que[0].left)
            que.append(que[0].right)
            del(que[0])
        while len(que)!=0:
            if que[0] is not None:         # 既然之前遇到了空结点，说明下面所有的也必须都是空结点 如果遇到非空结点 
                return False                   #也就不是完全二叉树了
            del(que[0])
        return True

想到别的再进行补充。

以上~

[Link 1]: https://blog.csdn.net/sinat_34328764/article/details/85871714