python实现二叉排序树

目录
  • 方法一(粗暴)
  • 方法二(递归)

方法一(粗暴)

#二叉排序树
class BTree():
    def __init__(self,data):
        self.left = None
        self.right = None
        if type(data) == list:
            self.data = data[0]
            for d in data[1:]:
                self.insert(d)
        else:
            self.data = data
    def insert(self,data):
        bt = self
        while True:
            if data <= bt.data:
                if bt.left == None:
                    bt.left = BTree(data)
                    break
                else:
                    bt = bt.left
            else:
                if bt.right == None:
                    bt.right = BTree(data)
                    break
                else:
                    bt = bt.right
    def mid_order(self):
        res = []
        stack = []
        node = self 
        while node or stack:
            while node:
                stack.append(node) 
                node = node.left
            node = stack.pop()
            res.append(node.data)
            node = node.right
        return res

data = [5,1,2,3,6,8,9]
bt = BTree(data)
print(bt.mid_order())

方法二(递归)

class TreeNode(object):
    def __init__(self,data):
        self.data = data
        self.left = None
        self.right = None

class BinaryTree(object):
    def insert(self,root, node):
        if root is None:
            return node
        if node.data < root.data:
            root.left = self.insert(root.left, node)
        else:
            root.right = self.insert(root.right, node)
        return root
    def mid_order(self,root):
        node = root
        stack = []
        res = []
        while node or stack:
            while node:
                stack.append(node)
                node = node.left
            node = stack.pop()
            res.append(node.data)
            node = node.right
        return res
    
data = [5,1,2,3,6,8,9]
root = TreeNode(data[0])
tree = BinaryTree()
for i in data[1:]:
    tree.insert(root,TreeNode(i))
print(tree.mid_order(root))

到此这篇关于python实现二叉排序树的文章就介绍到这了,更多相关python二叉排序树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

时间: 2022-01-12

Python数据结构之二叉排序树的定义、查找、插入、构造、删除

前言   本篇章主要介绍二叉树的应用之一------二叉排序树,包括二叉排序树的定义.查找.插入.构造.删除及查找效率分析. 1. 二叉排序树的定义   二叉排序树 ( B i n a r y (Binary (Binary S o r t Sort Sort T r e e , B S T ) Tree,BST) Tree,BST),也称为二叉查找树,具有以下性质:   (1) 若左子树非空,则左子树上所有结点的值均小于根结点的值:   (2) 若右子树非空,则右子树上所有结点的值均大于根结点

Python数据结构之双向链表的定义与使用方法示例

本文实例讲述了Python数据结构之双向链表的定义与使用方法.分享给大家供大家参考,具体如下: 和单链表类似,只不过是增加了一个指向前面一个元素的指针而已. 示意图: python 实现代码: #!/usr/bin/python # -*- coding: utf-8 -*- class Node(object): def __init__(self,val,p=0): self.data = val self.next = p self.prev = p class LinkList(obje

Python数据结构与算法之链表定义与用法实例详解【单链表、循环链表】

本文实例讲述了Python数据结构与算法之链表定义与用法.分享给大家供大家参考,具体如下: 本文将为大家讲解: (1)从链表节点的定义开始,以类的方式,面向对象的思想进行链表的设计 (2)链表类插入和删除等成员函数实现时需要考虑的边界条件, prepend(头部插入).pop(头部删除).append(尾部插入).pop_last(尾部删除) 2.1 插入: 空链表 链表长度为1 插入到末尾 2.2 删除 空链表 链表长度为1 删除末尾元素 (3)从单链表到单链表的一众变体: 带尾节点的单链表

Python数据结构之哈夫曼树定义与使用方法示例

本文实例讲述了Python数据结构之哈夫曼树定义与使用方法.分享给大家供大家参考,具体如下: HaffMan.py #coding=utf-8 #考虑权值的haff曼树查找效率并非最高,但可以用于编码等使用场景下 class TreeNode: def __init__(self,data): self.data=data self.left=None self.right=None self.parent=None class HaffTree: def __init__(self): sel

Python数据结构与算法之二叉树结构定义与遍历方法详解

本文实例讲述了Python数据结构与算法之二叉树结构定义与遍历方法.分享给大家供大家参考,具体如下: 先序遍历,中序遍历,后序遍历 ,区别在于三条核心语句的位置 层序遍历  采用队列的遍历操作第一次访问根,在访问根的左孩子,接着访问根的有孩子,然后下一层 自左向右一一访问同层的结点 # 先序遍历 # 访问结点,遍历左子树,如果左子树为空,则遍历右子树, # 如果右子树为空,则向上走到一个可以向右走的结点,继续该过程 preorder(t): if t: print t.value preorde

Python cookbook(数据结构与算法)实现查找两个字典相同点的方法

本文实例讲述了Python实现查找两个字典相同点的方法.分享给大家供大家参考,具体如下: 问题:寻找两个字典中间相同的地方(相同的键.相同的值等) 解决方案:通过keys()或者items()方法来执行常见的集合操作(比如求并集.交集和差集) >>> a={'x':1,'y':2,'z':3} >>> b={'ww':10,'x':11,'y':2} >>> a.keys()& b.keys() #键的交集 {'y', 'x'} >>

Python数据结构之栈、队列及二叉树定义与用法浅析

本文实例讲述了Python数据结构之栈.队列及二叉树定义与用法.分享给大家供大家参考,具体如下: 目前只实现了三种,栈.队列和二叉树,哪天得空继续补吧~ 1. 栈 #栈 class Stack: def __init__(self,size = 16): self.stack = [] self.size = size self.top = -1 def setSize(self, size): self.size = size def isEmpty(self): if self.top ==

python数据结构之链表详解

数据结构是计算机科学必须掌握的一门学问,之前很多的教材都是用C语言实现链表,因为c有指针,可以很方便的控制内存,很方便就实现链表,其他的语言,则没那么方便,有很多都是用模拟链表,不过这次,我不是用模拟链表来实现,因为python是动态语言,可以直接把对象赋值给新的变量. 好了,在说我用python实现前,先简单说说链表吧.在我们存储一大波数据时,我们很多时候是使用数组,但是当我们执行插入操作的时候就是非常麻烦,看下面的例子,有一堆数据1,2,3,5,6,7我们要在3和5之间插入4,如果用数组,我

JavaScript数据结构之二叉查找树的定义与表示方法

本文实例讲述了JavaScript数据结构之二叉查找树的定义与表示方法.分享给大家供大家参考,具体如下: 树是一种非线性的数据结构,以分层的方式存储数据.树被用来存储具有层级关系的数据,比如文件系统中的文件:树还被用来存储有序列表.这里将研究一种特殊的树:二叉树.选择树而不是那些基本的数据结构,是因为在二叉树上进行查找非常快(而在链表上查找则不是这样),为二叉树添加或删除元素也非常快(而对数组执行添加或删除操作则不是这样). 树是n个结点的有限集.最上面的为根,下面为根的子树.树的节点包含一个数

Java数据结构之简单链表的定义与实现方法示例

本文实例讲述了Java数据结构之简单链表的定义与实现方法.分享给大家供大家参考,具体如下: 一.概述: 1.原理: 只有一个数据项(链接点Link),每个数据插入时都是对第一个数据的引用. 2.插入数据说明: 当链表没有数据时,插入的值就是第一个数据,如果链表里有数据,就把当前的数据的next指针指向第一个数据. 3.插入数据图: 4.特点:先进后出 5.实现功能: 数据插入,指定位置插入,显示,查询,删除等 6.删除原理 7.插入头节点原理 二.实现: 1.创建节点 /** * @描述 节点

C语言实现带头结点的链表的创建、查找、插入、删除操作

本文实例讲述了C语言实现带头结点的链表的创建.查找.插入.删除操作.是数据结构中链表部分的基础操作.分享给大家供大家参考.具体方法如下: #include <stdio.h> #include <stdlib.h> typedef struct node { int data; struct node* next;// 这个地方注意结构体变量的定义规则 } Node, *PNode; Node* createLinklist(int length) { int i = 0; PNo