本文共 10881 字，大约阅读时间需要 36 分钟。

Python实现完全二叉树

一、二叉树的存储结构

对于线性表、栈、队列等数据结构，数据都可以使用物理有序和逻辑有序的方式存储，二叉树也可以使用这两种方式存储。

物理有序将数据存储在连续的内存空间中，例如存储在一个列表中，这种方式因为有下标，在遍历速度上有一定的优势，但是，对于一棵二叉树来说，将数据存储在一个线性的列表中，不容易体现出树中父节点与子节点之间的关系。

根据二叉树的结构特点，二叉树是由一个个的节点构成的，节点与节点之间通过父子关系链接在一起，所以，二叉树通常以链式方式存储。

二、实现完全二叉树类

一棵普通的二叉树中，节点的排列不一定是从上到下、从左到右依次排列的。满足从上到下、从左到右依次排列的二叉树是完全二叉树。所以为了从简到繁，本文先实现完全二叉树。

完全二叉树由一个个节点组成，先实现一个节点的类 Node 类。

# coding=utf-8class Node(object):    def __init__(self, data):        self.data = data        self.parent = None        self.left_child = None        self.right_child = None

创建节点时，实例化一个节点类的实例即可，节点初始化时是一个孤立的节点，指向的父节点、左子节点、右子节点都为空。将节点“挂”到树上(添加到树中)后，才属于树的一部分。

接下来实现一个完全二叉树的类 PerfectBinaryTree 。

class PerfectBinaryTree(object):    def __init__(self):        self.__root = None    def is_empty(self):        return not self.__root

一棵二叉树，只要先找到树的根节点(Root)，就可以依次根据节点的父子关系找到所有节点，所以初始化一棵二叉树时，只要先指向树的根节点即可。

在还没有添加节点到二叉树中时，树是一棵空二叉树，所以指向为空。

先实现is_empty()方法: 判断树是否为一棵空二叉树，如果树的根指向为空(对应布尔值False)，则树为空二叉树(is_empty为True)，反之。

if __name__ == '__main__':    tree = PerfectBinaryTree()    print(tree)    print("is_empty: ", tree.is_empty())

运行结果：

<__main__.PerfectBinaryTree object at 0x00000277429F27F0>is_empty:  True

可以看到已经实例化了一个 PerfectBinaryTree 的对象，现在还没有添加节点，所以树是空树。

三、实现完全二叉树的遍历和添加节点

现在开始向完全二叉树中添加节点。完全二叉树的节点是从上到下、从左到右依次排列的，中间不能有空位，所以向完全二叉树中添加节点也要遵循这个顺序。

添加节点的第一步是找到添加的位置。如果树是一棵空树，节点直接添加在根节点的位置，树的根直接指向节点即可。

如果树中只有根节点一个节点，则根节点的左子节点为空，节点应该添加在根节点的左子节点的位置，如果已经有了左子节点，则节点应该添加在根节点的右子节点的位置。如果根节点的子节点满了，再判断根节点的左子节点的子节点是否有空位，以此类推。

这就需要对二叉树的节点进行遍历，依次判断每个节点的左子节点和右子节点是否为空，这种遍历方式是一层一层地从上到下、从左到右遍历，按层进行遍历，也叫层次遍历。那么，怎么实现二叉树的层次遍历呢？

根据二叉树的结构，节点之间按链式方式存储，每一层的节点位置数都是上一层的两倍，不好判断什么时候转到下一层，直接遍历显然不好实现。

所以应该使用间接的方式对二叉树进行遍历，借助一个队列来实现。先将树中的节点依次添加到一个队列中，然后再从队列中取出每一个节点，队列是先进先出的，只要保证入队的先后，就可以保证出队的先后。

先将树的根节点入队，然后从队列中取出根节点进行判断，如果根节点的左子节点不为空，则将左子节点入队，如果右子节点不为空，则将右子节点入队。根节点判断完成，继续从队列中取下一个节点进行判断，这里取到的正好就是根节点的左子节点，同样，判断它的左子节点，不为空就入队，再判断它的右子节点，不为空就入队。然后继续从队列中取下一个节点进行判断，这里取到的刚好是根节点的右子节点。按这个方式找下去，就实现了对完全二叉树的遍历，从而找到从上到下、从左到右的第一个空位，将新节点添加在这个位置。

那么，先实现一个队列 TreeQueue ，只要有入队、出队和判断是否为空的方法即可满足使用。

class TreeQueue(object):    def __init__(self):        self.__members = list()    def is_empty(self):        return not len(self.__members)    def enter(self, data):        self.__members.insert(0, data)    def outer(self):        if self.is_empty():            return        return self.__members.pop()

这个队列使用一个列表来存储数据，只要列表长度为零，则队列为空。入队使用列表的insert(0, data)方法，出队使用列表的pop()方法。

关于队列的详细介绍可以参考：

有了队列，现在开始实现完全二叉树添加数据的功能。

def append(self, data):        node = Node(data)        if self.is_empty():            self.__root = node            return        queue = TreeQueue()        queue.enter(self.__root)        while not queue.is_empty():            cur = queue.outer()            if cur.left_child is None:                cur.left_child = node                node.parent = cur                return            queue.enter(cur.left_child)            if cur.right_child is None:                cur.right_child = node                node.parent = cur                return            queue.enter(cur.right_child)

append(data): 如果完全二叉树是一棵空树，则节点添加在根节点处，直接将树的根指向节点即可。如果树非空，则实例化一个队列，从根节点开始，将树的节点添加到队列中，然后从队列中依次取出节点判断是否有左右子节点，找到第一个空位，将新节点添加在此位置。如果空位是左子节点，将当前节点的左子节点指向新节点，将新节点的父节点指向当前节点，空位是右子节点同理。添加完成节点后退出循环。

已经实现添加节点到树中，现在实现一个展示数据的方法，来展示一下数据。

def show(self):        if self.is_empty():            print('空二叉树')            return        queue = TreeQueue()        queue.enter(self.__root)        while not queue.is_empty():            cur = queue.outer()            print(cur.data, end=' ')            if cur.left_child is not None:                queue.enter(cur.left_child)            if cur.right_child is not None:                queue.enter(cur.right_child)        print()

show()：已经知道怎么遍历完全二叉树的节点了，要依次打印数据就比较简单了，只要将树中的节点依次入队，然后依次出队，出队时打印当前节点中存储的数据即可。

tree.show()    for i in range(15):        tree.append(i)    tree.show()

运行结果：

空二叉树0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

四、实现完全二叉树的其他方法

实现判断一个数据是否存在完全二叉树中的方法。

def is_exist(self, data):        if self.is_empty():            return False        queue = TreeQueue()        queue.enter(self.__root)        while not queue.is_empty():            cur = queue.outer()            if cur.data == data:                return True            if cur.left_child is not None:                queue.enter(cur.left_child)            if cur.right_child is not None:                queue.enter(cur.right_child)        return False

is_exist(data)：这个方法是判断一个数据是否存在完全二叉树中，是常用的简单搜索功能，知道怎么遍历完全二叉树后，实现也很简单，只要遍历时判断当前节点存储的数据是否等于指定值，相等则返回True，遍历完整棵树都没有找到，则返回False。

print(tree.is_exist(2))    print(tree.is_exist(200))

运行结果：

TrueFalse

如果要修改节点中存储的数据的值，也可以使用相同的方式遍历，找到某个值的节点，然后修改为另一个值。

对于删除节点的方法，二叉树的删除方法相对于链表、队列等数据结构来说，比较复杂，以后再研究。

五、实现完全二叉树的树形展示方法

在上面添加数据后，实现了一个show()方法，用来展示数据，但只是将数据按遍历次序打印了出来。

接下来对这个方法进行优化，目的是达到像Linux中tree命令相同的效果，让人更直观地看到一棵树的结构，可以看到父节点与子节点之间的关系。

先在 PerfectBinaryTree 的 __init__() 方法中添加几个字符串变量，用于打印时的效果展示。

def __init__(self):        self.__root = None        self.prefix_branch = '├'        self.prefix_trunk = '|'        self.prefix_leaf = '└'        self.prefix_empty = ''        self.prefix_left = '─L─'        self.prefix_right = '─R─'

然后实现按树结构展示的方法 show_tree() 。

def show_tree(self):        if self.is_empty():            print('空二叉树')            return        print(self.__root.data)        self.__print_tree(self.__root)    def __print_tree(self, node, prefix=None):        if prefix is None:            prefix = ''            prefix_left_child = ''        else:            prefix = prefix.replace(self.prefix_branch, self.prefix_trunk)            prefix = prefix.replace(self.prefix_leaf, self.prefix_empty)            prefix_left_child = prefix.replace(self.prefix_leaf, self.prefix_empty)        if self.has_child(node):            if node.right_child is not None:                print(prefix + self.prefix_branch + self.prefix_right + str(node.right_child.data))                if self.has_child(node.right_child):                    self.__print_tree(node.right_child, prefix + self.prefix_branch + ' ')            else:                print(prefix + self.prefix_branch + self.prefix_right)            if node.left_child is not None:                print(prefix + self.prefix_leaf + self.prefix_left + str(node.left_child.data))                if self.has_child(node.left_child):                    prefix_left_child += '  '                    self.__print_tree(node.left_child, self.prefix_leaf + prefix_left_child)            else:                print(prefix + self.prefix_leaf + self.prefix_left)    def has_child(self, node):        return node.left_child is not None or node.right_child is not None

show_tree()：这个方法就是通过拼接字符串的方式，使打印出来的效果是树形的结构。先从根节点开始，判断是否有子节点，然后判断子节点是左子节点还是右子节点，有的话就按需要的效果打印拼接的字符串和子节点的值，打印完再递归判断子节点是否也有子节点，然后进行打印。

遇到递归比较绕，可以自己找几个例子来和代码对应一下，就能理解了。看一下效果吧。

tree.show_tree()

运行结果：

0├─R─2| ├─R─6| | ├─R─14| | └─L─13| └─L─5|   ├─R─12|   └─L─11└─L─1  ├─R─4  | ├─R─10  | └─L─9  └─L─3    ├─R─8    └─L─7

六、完整代码

# coding=utf-8class Node(object):    def __init__(self, data):        self.data = data        self.parent = None        self.left_child = None        self.right_child = Noneclass TreeQueue(object):    def __init__(self):        self.__members = list()    def is_empty(self):        return not len(self.__members)    def enter(self, data):        self.__members.insert(0, data)    def outer(self):        if self.is_empty():            return        return self.__members.pop()class PerfectBinaryTree(object):    def __init__(self):        self.__root = None        self.prefix_branch = '├'        self.prefix_trunk = '|'        self.prefix_leaf = '└'        self.prefix_empty = ''        self.prefix_left = '─L─'        self.prefix_right = '─R─'    def is_empty(self):        return not self.__root    def append(self, data):        node = Node(data)        if self.is_empty():            self.__root = node            return        queue = TreeQueue()        queue.enter(self.__root)        while not queue.is_empty():            cur = queue.outer()            if cur.left_child is None:                cur.left_child = node                node.parent = cur                return            queue.enter(cur.left_child)            if cur.right_child is None:                cur.right_child = node                node.parent = cur                return            queue.enter(cur.right_child)    def show(self):        if self.is_empty():            print('空二叉树')            return        queue = TreeQueue()        queue.enter(self.__root)        while not queue.is_empty():            cur = queue.outer()            print(cur.data, end=' ')            if cur.left_child is not None:                queue.enter(cur.left_child)            if cur.right_child is not None:                queue.enter(cur.right_child)        print()    def is_exist(self, data):        if self.is_empty():            return False        queue = TreeQueue()        queue.enter(self.__root)        while not queue.is_empty():            cur = queue.outer()            if cur.data == data:                return True            if cur.left_child is not None:                queue.enter(cur.left_child)            if cur.right_child is not None:                queue.enter(cur.right_child)        return False    def show_tree(self):        if self.is_empty():            print('空二叉树')            return        print(self.__root.data)        self.__print_tree(self.__root)    def __print_tree(self, node, prefix=None):        if prefix is None:            prefix = ''            prefix_left_child = ''        else:            prefix = prefix.replace(self.prefix_branch, self.prefix_trunk)            prefix = prefix.replace(self.prefix_leaf, self.prefix_empty)            prefix_left_child = prefix.replace(self.prefix_leaf, self.prefix_empty)        if self.has_child(node):            if node.right_child is not None:                print(prefix + self.prefix_branch + self.prefix_right + str(node.right_child.data))                if self.has_child(node.right_child):                    self.__print_tree(node.right_child, prefix + self.prefix_branch + ' ')            else:                print(prefix + self.prefix_branch + self.prefix_right)            if node.left_child is not None:                print(prefix + self.prefix_leaf + self.prefix_left + str(node.left_child.data))                if self.has_child(node.left_child):                    prefix_left_child += '  '                    self.__print_tree(node.left_child, self.prefix_leaf + prefix_left_child)            else:                print(prefix + self.prefix_leaf + self.prefix_left)    def has_child(self, node):        return node.left_child is not None or node.right_child is not Noneif __name__ == '__main__':    tree = PerfectBinaryTree()    print(tree)    print("is_empty: ", tree.is_empty())    tree.show()    for i in range(15):        tree.append(i)    tree.show()    print(tree.is_exist(2))    print(tree.is_exist(200))    tree.show_tree()

 

 

转载地址：http://kzppz.baihongyu.com/