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

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

内容简介：二叉查找树的增加，删除，遍历 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/

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

查看所有标签

猜你喜欢:

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

码农书籍

Data Structures and Algorithm Analysis in Java

Mark A. Weiss / Pearson / 2011-11-18 / GBP 129.99

Data Structures and Algorithm Analysis in Java is an “advanced algorithms” book that fits between traditional CS2 and Algorithms Analysis courses. In the old ACM Curriculum Guidelines, this course wa......一起来看看《Data Structures and Algorithm Analysis in Java》这本书的介绍吧!

码农工具

Base64 编码/解码

html转js在线工具

RGB CMYK 转换工具

RGB CMYK 互转工具