这次用完成的是二叉树,是一种简单的树型结构。同样使用python实现 多的不说了,上代码吧。
# -*- coding: cp936 -*- #--------------------------------------------- # # author chile # version 1.0 # date 2014-02-17 # desc 二叉树 # # # #--------------------------------------------- class bintree: def __init__(self): self.root = None # 前驱节点 def treePredecessor(self,entry): if entry.left != None: return self.maxTree(entry.left) preNode = entry.parent tempNode = entry while preNode != None and preNode.right.value != entry.value: tempNode = preNode preNode = preNode.parent return preNode #后继节点 def treeSuccessor(self,entry): if entry.right != None: return self.minTree(entry.right) preNode = entry.parent tempNode = entry while preNode != None and preNode.left.value != entry.value: tempNode = preNode preNode = preNode.parent return preNode def add(self,value): tempNode = self.root parentNode = None entry = bintree.entry(value = value) while tempNode != None: parentNode = tempNode if cmp(value,parentNode.value) < 0: tempNode = tempNode.left else: tempNode = tempNode.right if parentNode == None: self.root = entry elif cmp(value,parentNode.value) < 0: parentNode.left = entry entry.parent = parentNode else: parentNode.right = entry entry.parent = parentNode #这里删除是全部删除节点(包括所有子节点) def remove(self,value): root = self.root parentNode = None if value == root.value: root.left = None root.right = None while root != None: parentNode = root.parent if value == root.value: root.left = None root.right = None if parentNode.left != None and parentNode.left.value == value: parentNode.left = None break else: parentNode.right = None break elif cmp(value,root.value) < 0: root = root.left else: root = root.right #查找节点 def search(self,value): root = self.root while root != None and root.value != value: if cmp(value,root.value) < 0: root = root.left else: root = root.right return root #最小值的节点,其实就是找左边的叶子节点 def minTree(self,root): entry = root while entry.left != None: entry = entry.left return entry #最大值的节点 def maxTree(self,root): entry = root while entry.right != None: entry = entry.right return entry #中序遍历 def iterator(self,root): if root != None: self.iterator(root.left) print root.value self.iterator(root.right) class entry: def __init__(self, value=None): self.left = None self.right = None self.parent = None self.value = value arr = [15,5,3,12,10,13,6,7,16,20,18,23] tree = bintree() for val in arr: tree.add(val) tree.iterator(tree.root) node = tree.search(16) print node.left , node.right , node.parent.value print tree.maxTree(node).value print tree.treePredecessor(node).value print tree.treeSuccessor(node).value #print tree.maxTree() , tree.minTree()
相关推荐
1. 定义 2. 查找与插入 3. 删除 1. 如果待删除的节点是叶子节点,那么可以立即被删除,如下图所示: 2. 如果节点只有一个儿子,则将此节点parent
本文研究的主要是python实现二叉查找树的相关内容,具体介绍及实现如下。 1. 二叉查找树的定义: 左子树不为空的时候,左子树的结点值小于根节点,右子树不为空时,右子树的结点值大于根节点,左右子树分别为二叉...
二叉查找树
主要介绍了Python实现二叉搜索树BST的方法示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
本人用python实现了二叉搜索树的查找(递归与非递归)与插入(递归与非递归)和打印功能,并生成n个随机数插入二叉搜索树当中,中序遍历输出。学习数据结构的同学可以参考一下!!!
二叉搜索树(二叉查找树,Binary Search Tree)又称为排序二叉树、有序二叉树。 二叉搜索树的实现可以参考:https://blog.csdn.net/weixin_43790276/article/details/105753543 本文使用 Python 实现二叉搜索树的删除...
用python编写的简单二叉查找树,初学者可以借鉴一下
二叉搜索树(二叉排序树)它的每个节点的数据结构为1个父节点指针,1个左孩子指针,1个有孩子指针,还有就是自己的数据部分了,因为只有左右两孩子,所以才叫二叉树,在此基础上,该二叉树还满足另外一个条件:每个结点的左...
剑指Offer(Python多种思路实现):二叉搜索树的第K大节点 面试54题: 题目:二叉搜索树的第K大节点 题:给定一颗二叉搜索树,请找出其中的第k小的结点。例如, 5 / \ 3 7 /\ /\ 2 4 6 8 中,按结点数值大小顺序第三个...
本文实例讲述了Python实现查找二叉搜索树第k大的节点功能。分享给大家供大家参考,具体如下: 题目描述 给定一个二叉搜索树,找出其中第k大的节点 就是一个中序遍历的过程,不需要额外的数组,便利到节点之后,k减...
树 * 字典树 ...* 二叉查找树-从有序数组中构造二叉查找树 * 二叉查找树-从有序链表构造平衡的二叉查找树 * 二叉树-的最大深度 数组&字符串 查找排序 排列组合 动态规划 树 链表 数学 位运算 编程之美
Python 树表查找_千树万树梨花开,忽如一夜春风来(二叉排序树、平衡二叉树).doc
二叉排序树查找,Python3 数据结构与算法的... 查找算法: 顺序查找、二分查找、哈希表查找、二叉查找树、平衡二叉查找树(AVL树、红黑树)、平衡多路查找树(B树、B+树);4. LeetCode 和《剑指Offer》刷题、多种方法的题解
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。 解法一:递归法 # -*- coding:utf-8 -*- class Solution: def ...
32_二叉查找树 33_AVL树的python实现 34_python实现ADT Graph 35_词梯WordLadder问题 36_BFS和DFS实现 37_图的应用-骑士周游问题 38_图的应用-拓扑排序 39_图的应用-强连通分支Kosaraju 40_图的应用-最短路径问题 41...
递归 # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def isValidBST(self, root): ...