二叉查找树的增加，删除，遍历 python

栏目: Python · 发布时间: 7年前

内容简介：二叉查找树的增加，删除，遍历 python

本文主要使用 python 实现二叉查找树的如下部分：

二叉查找树构造
二叉查找树插入
二叉查找树遍历
二叉查找树删除

二叉查找树是一颗二叉树，并且基本数据结构要求满足如下条件：

所有左接点的值均小于它的根结点
所有的右接点值均大于它的根结点
所有的左右子树均是二叉查找树（每个接点都大于它左侧子树的任意接点，并小于右侧子树的任意接点）

来个栗子:

二叉查找树的增加，删除，遍历 python

二叉查找树的构造：

我们想来构造一个树，我们需要3个变量：

左节点
右节点
根节点数据

class Node:
    """
    Tree node: left and right child + data which can be any object
    """
    def __init__(self, data):
        """
        Node constructor
 
        @param data node data object
        """
        self.left = None
        self.right = None
        self.data = data

让我们来创建一个值为8的根结点，这个时候，左右节点均是None

root = Node( 8 )

如下图看到的，我们创建了一个只有一个节点的树

二叉查找树的增加，删除，遍历 python

插入方法

我们需要一个方法来插入元素让我们的单个节点的树变的充实起来，这个方法的参数是个数值和某个节点本身（根节点/二叉查找树）

class Node:
    ...
    def insert(self, data):
        """
        Insert new node with data
 
        @param data node data object to insert
        """
        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data

插入方法会递归的调用，直到为我们的元素（节点）找到合适的位置

让我们来增加3个元素（节点），然后看看我们的插入方法是如何运行的

`1`	`root.insert(` `3` `)`

`2`	`root.insert(` `10` `)`

`3`	`root.insert(` `1` `)`

插入元素3（节点）的过程:

第一步：根结点调用插入方法，调用时传入的变量为3
第二步：3比8小，而且根节点8的左节点为None，所以我们直接把3这个节点（3的左右节点均为None）,放到8的左节点上

插入元素10（节点）的过程:

根节点调用insert方法，传入变量10
10大于根节点，并且根节点的右分支为None,所以我们把10放到根节点的右分支

插入元素1（节点）的过程:

根节点调用insert方法，传入参数1
1比8小，并且8这个根结点有左侧分值（不为None）,所以，根结点的左节点调用insert方法，传入参数1
这个时候，1比3小，并且3没有左分支，我们就把1放到了3的左节点上

现在的结构是:

二叉查找树的增加，删除，遍历 python

让我们继续插入新的元素让树更加充实.

`1`	`root.insert(` `6` `)`

`2`	`root.insert(` `4` `)`

`3`	`root.insert(` `7` `)`

`4`	`root.insert(` `14` `)`

`5`	`root.insert(` `13` `)`

插入完成后的栗子:

二叉查找树的增加，删除，遍历 python

遍历

我们需要一个方法能够帮助我们找到具体的某一个节点，这个方法会接收一个数值，返回这个数值所在的节点，并返回它的父节点（如果不寸再就返回None）

class Node:
    ...
    def lookup(self, data, parent=None):
        """
        Lookup node containing data
 
        @param data node data object to look up
        @param parent node's parent
        @returns node and node's parent if found or None, None
        """
        if data < self.data:
            if self.left is None:
                return None, None
            return self.left.lookup(data, self)
        elif data > self.data:
            if self.right is None:
                return None, None
            return self.right.lookup(data, self)
        else:
            return self, parent

我们试着查找下6

`1`	`node, parent` `=` `root.lookup(` `6` `)`

具体的查找过程:

第一步：传入参数6，默认的parent = None
第二步：6 小于根节点的8
第三步：这个时候，根结点的左节点3，继续调用lookup函数，这个时候的parent就是当前的节点了
第四步：6比3大
第五步：然后3的右节点（孩子），调用lookup
第六步：发现6等于3的右孩子，找到了！

二叉查找树的增加，删除，遍历 python

删除方法

删除方法需要传入的参数就是一个节点的值

class Node:
    ...
    def delete(self, data):
        """
        Delete node containing data
 
        @param data node's content to delete
        """
        # get node containing data
        node, parent = self.lookup(data)
        if node is not None:
            children_count = node.children_count()
        ...

删除的时候有三种情况：

1：被删除的节点没有子节点
2：被删除的节点有一个子节点.
3：被删除的节点有2个子节点

第一种情况是非常简单的，我只需要将这个节点删除，然后将它的父节点相应的子节点置为None即可

def delete(self, data):
    ...
    if children_count == 0:
        # if node has no children, just remove it
        if parent:
            if parent.left is node:
                parent.left = None
            else:
                parent.right = None
            del node
        else:
            self.data = None
    ...

注：方法children_count()会返回一个节点的子节点的个数

children_count:

class Node:
    ...
    def children_count(self):
        """
        Returns the number of children
 
        @returns number of children: 0, 1, 2
        """
        cnt = 0
        if self.left:
            cnt += 1
        if self.right:
            cnt += 1
        return cnt

举个例子，我们想删除节点1，3的左分支会被设置成None

`1`	`root.delete(` `1` `)`

二叉查找树的增加，删除，遍历 python

让我们来看一下第二种情况，这个时候，我们需要用它的子节点来代替被删除的节点

def delete(self, data):
    ...
    elif children_count == 1:
        # if node has 1 child
        # replace node with its child
        if node.left:
            n = node.left
        else:
            n = node.right
        if parent:
            if parent.left is node:
                parent.left = n
            else:
                parent.right = n
            del node
        else:
            self.left = n.left
            self.right = n.right
            self.data = n.data
    ...

举个例子，我们想删除节点14，这个时候，13会代替14，然后新的13的左右分支会被置为None

`1`	`root.delete(` `14` `)`

二叉查找树的增加，删除，遍历 python

让我们来看一下最后一种可能，就是被删除节点有两个子节点，我们会用其中一个来代被删除的节点，并递归的完成这个过程

def delete(self, data):
    ...
    else:
        # if node has 2 children
        # find its successor
        parent = node
        successor = node.right
        while successor.left:
            parent = successor
            successor = successor.left
        # replace node data by its successor data
        node.data = successor.data
        # fix successor's parent's child
        if parent.left == successor:
            parent.left = successor.right
        else:
            parent.right = successor.right

举例子：我们想要删除3，这个时候我们会递归的去查找右测元素，终于找到4，我们将4替换3，然后将6的子节点值None

`1`	`root.delete(` `3` `)`

二叉查找树的增加，删除，遍历 python

参考地址： http://www.laurentluce.com/posts/binary-search-tree-library-in-python/comment-page-1/

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。

码农书籍

加密与解密（第4版）

段钢 / 电子工业出版社 / 2018-10-1 / 198

《加密与解密（第4版）》以加密与解密为切入点，讲述了软件安全领域的基础知识和技能，如调试技能、逆向分析、加密保护、外壳开发、虚拟机设计等。这些知识彼此联系，读者在掌握这些内容之后，很容易就能在漏洞分析、安全编程、病毒分析、软件保护等领域进行扩展。从就业的角度来说，掌握加密与解密的相关技术，可以提高自身的竞争能力；从个人成长的角度来说，研究软件安全技术有助于掌握一些系统底层知识，是提升职业技能的重要......一起来看看《加密与解密（第4版）》这本书的介绍吧!

码农工具