Python实现查找二叉搜索树第k大的节点功能示例

本文实例讲述了Python实现查找二叉搜索树第k大的节点功能。分享给大家供大家参考，具体如下：

题目描述

给定一个二叉搜索树，找出其中第k大的节点

就是一个中序遍历的过程，不需要额外的数组，便利到节点之后，k减一就行。

代码1

class TreeNode:
  def __init__(self, x):
    self.val = x
    self.left = None
    self.right = None
class Solution:
  def __init__(self):
    self.k = 0
  def recursionKthNode(self, Root):
    result = None
    if result == None and Root.left:
      result = self.recursionKthNode(Root.left)
    if result == None:
      if self.k == 1:
        return Root
      self.k -= 1
    if result == None and Root.right:
      result = self.recursionKthNode(Root.right)
    return result
  def KthNode(self, Root, k):
    if Root == None:
      return None
    self.k = k
    return self.recursionKthNode(Root)
Root = TreeNode(5)
Root.left = TreeNode(3)
Root.left.left = TreeNode(2)
Root.left.right = TreeNode(4)
Root.right = TreeNode(7)
Root.right.left = TreeNode(6)
Root.right.right = TreeNode(8)
print(Solution().KthNode(Root,3).val)

output : 4

代码2

class TreeNode:
  def __init__(self, x):
    self.val = x
    self.left = None
    self.right = None
class Solution:
  def __init__(self):
    self.k = 0
  def InOrder(self, Root):
    ans = None
    if Root:
      if ans == None and Root.left:
        ans = self.InOrder(Root.left)  #往左遍历
      if ans == None and self.k == 1:
        ans = Root           #遍历到目标节点
      if ans == None and self.k != 1:   #没有遍历到目标节点，k--
        self.k -= 1
      if ans == None and Root.right:   #往右遍历
        ans = self.InOrder(Root.right)
    return ans
  def KthNode(self, Root, k):
    if Root == None or k <= 0:
      return None
    self.k = k
    return self.InOrder(Root)

更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》

希望本文所述对大家Python程序设计有所帮助。

赞 (0)

相关推荐

  • Python实现二叉搜索树

    Python实现二叉搜索树

    二叉搜索树 我们已经知道了在一个集合中获取键值对的两种不同的方法.回忆一下这些集合是如何实现ADT(抽象数据类型)MAP的.我们讨论两种ADT MAP的实现方式,基于列表的二分查找和哈希表.在这一节中,我们将要学习二叉搜索树,这是另一种键指向值的Map集合,在这种情况下我们不用考虑元素在树中的实际位置,但要知道使用二叉树来搜索更有效率. 搜索树操作 在我们研究这种实现方式之前,让我们回顾一下ADT MAP提供的接口.我们会注意到,这种接口和Python的字典非常相似. Map() 创建了一个新的

  • Python二叉搜索树与双向链表转换实现方法

    本文实例讲述了Python二叉搜索树与双向链表实现方法.分享给大家供大家参考,具体如下: # encoding=utf8 ''' 题目:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表. 要求不能创建任何新的结点,只能调整树中结点指针的指向. ''' class BinaryTreeNode(): def __init__(self, value, left = None, right = None): self.value = value self.left = left self.

  • Python单向链表和双向链表原理与用法实例详解

    Python单向链表和双向链表原理与用法实例详解

    本文实例讲述了Python单向链表和双向链表原理与用法.分享给大家供大家参考,具体如下: 链表是一种数据结构,链表在循环遍历的时候效率不高,但是在插入和删除时优势比较大. 链表由一个个节点组成. 单向链表的节点分为两个部分:存储的对象和对下一个节点的引用.注意是指向下一个节点. 而双向链表区别于单向链表的是它是由三个部分组成:存储的对象.对下一个节点的引用.对上一个节点的引用,可以实现双向遍历. 单向列表的结构如下图: head是头节点,tail是尾节点,每个节点由Data存储对象和Next对下

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

    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双向循环链表实现方法.分享给大家供大家参考,具体如下: 最近身边的朋友在研究用python来实现数据结构.遇到一个问题就是双向循环链表的实现,改指向的时候总是发蒙. 我自己尝实现了一个python的双向循环链表.附上代码,希望对大家有帮助. 如果不懂什么是双向循环链表的伙伴,需要补习一下数据结构的基础之后哦~~~ 在python当中 用一个类Node 来实现链表的节点,节点数据有三个变量: prev:前驱指针: 用于指向当前节点前一个节点 next: 后继指针  用于指

  • Python二叉树的遍历操作示例【前序遍历,中序遍历,后序遍历,层序遍历】

    本文实例讲述了Python二叉树的遍历操作.分享给大家供大家参考,具体如下: # coding:utf-8 """ @ encoding: utf-8 @ author: lixiang @ email: lixiang_cn@foxmail.com @ python_version: 2 @ time: 2018/4/11 0:09 @ more_info: 二叉树是有限个元素的集合,该集合或者为空.或者有一个称为根节点(root)的元素及两个互不相交的.分别被称为左子树和

  • Python实现的序列化和反序列化二叉树算法示例

    本文实例讲述了Python实现的序列化和反序列化二叉树算法.分享给大家供大家参考,具体如下: 题目描述 请实现两个函数,分别用来序列化和反序列化二叉树 序列化二叉树 先序遍历二叉树 def recursionSerialize(self, root): series = '' if root == None: series += ',$' else: series += (',' + str(root.val)) series += self.recursionSerialize(root.le

  • 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(object):    def __init__(self):        self.he

  • Python二叉搜索树与双向链表转换算法示例

    本文实例讲述了Python二叉搜索树与双向链表转换算法.分享给大家供大家参考,具体如下: 题目描述 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表.要求不能创建任何新的结点,只能调整树中结点指针的指向. 普通的二叉树也可以转换成双向链表,只不过不是排序的 思路: 1. 与中序遍历相同 2. 采用递归,先链接左指针,再链接右指针 代码1,更改doubleLinkedList,最后返回list的第一个元素: class TreeNode: def __init__(self, x): s

  • Python实现查找二叉搜索树第k大的节点功能示例

    Python实现查找二叉搜索树第k大的节点功能示例

    本文实例讲述了Python实现查找二叉搜索树第k大的节点功能.分享给大家供大家参考,具体如下: 题目描述 给定一个二叉搜索树,找出其中第k大的节点 就是一个中序遍历的过程,不需要额外的数组,便利到节点之后,k减一就行. 代码1 class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution: def __init__(self): self.k = 0 de

  • Python实现查找数组中任意第k大的数字算法示例

    本文实例讲述了Python实现查找数组中任意第k大的数字算法.分享给大家供大家参考,具体如下: 模仿partion方法,当high=low小于k的时候,在后半部分搜索,当high=low大于k的时候,在前半部分搜索.与快排不同的是,每次都减少了一半的排序. def partitionOfK(numbers, start, end, k): if k < 0 or numbers == [] or start < 0 or end >= len(numbers) or k > end

  • C++数据结构之二叉搜索树的实现详解

    C++数据结构之二叉搜索树的实现详解

    目录 前言 介绍 实现 节点的实现 二叉搜索树的查找 二叉搜索树的插入 二叉搜索树的删除 总结 前言 今天我们来学一个新的数据结构:二叉搜索树. 介绍 二叉搜索树也称作二叉排序树,它具有以下性质: 非空左子树的所有键值小于其根节点的键值 非空右子树的所有键值大于其根节点的键值 左,右子树都是二叉搜索树 那么我先画一个二叉搜索树给大家看看,是不是真的满足上面的性质. 我们就以根节点6为例子来看,我们会发现比6小的都在6的左边,而比6大的都在6的右边.对于6的左右子树来说,所有的节点都遵循这个规则.

  • 利用java实现二叉搜索树

    利用java实现二叉搜索树

    二叉搜索树的定义 它是一颗二叉树 任一节点的左子树上的所有节点的值一定小于该节点的值 任一节点的右子树上的所有节点的值一定大于该节点的值 特点: 二叉搜索树的中序遍历结果是有序的(升序)! 实现一颗二叉搜索树 实现二叉搜索树,将实现插入,删除,查找三个方面 二叉搜索树的节点是不可以进行修改的,如果修改,则可能会导致搜索树的错误 二叉搜索树的定义类 二叉搜索树的节点类 -- class Node 二叉搜索树的属性:要找到一颗二叉搜索树只需要知道这颗树的根节点. public class BST {

  • Java深入了解数据结构之二叉搜索树增 插 删 创详解

    Java深入了解数据结构之二叉搜索树增 插 删 创详解

    目录 ①概念 ②操作-查找 ③操作-插入 ④操作-删除 1. cur.left == null 2. cur.right == null 3. cur.left != null && cur.right != null ⑤性能分析 ⑥完整代码 ①概念 二叉搜索树又称二叉排序树,它或者是一棵空树**,或者是具有以下性质的二叉树: 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值 它的左右子树也分别为二叉搜索树 ②操作-查找

  • Java数据结构超详细分析二叉搜索树

    Java数据结构超详细分析二叉搜索树

    目录 1.搜索树的概念 2.二叉搜索树的简单实现 2.1查找 2.2插入 2.3删除 2.4修改 3.二叉搜索树的性能 1.搜索树的概念 二叉搜索树是一种特殊的二叉树,又称二叉查找树,二叉排序树,它有几个特点: 如果左子树存在,则左子树每个结点的值均小于根结点的值. 如果右子树存在,则右子树每个结点的值均大于根结点的值. 中序遍历二叉搜索树,得到的序列是依次递增的. 二叉搜索树的左右子树均为二叉搜索树. 二叉搜索树的结点的值不能发生重复. 2.二叉搜索树的简单实现 我们来简单实现以下搜索树,就不

  • C++深入细致探究二叉搜索树

    C++深入细致探究二叉搜索树

    目录 1.二叉搜索树的概念 2.二叉搜索树的操作 二叉搜索树的查找 二叉搜索树的插入 二叉搜索树的删除 3.二叉搜索树的实现 4.二叉搜索树的性能分析 1.二叉搜索树的概念  二叉搜索树又称二叉排序树,它可以是一颗空树,亦可以是一颗具有如下性质的二叉树:   ①若根节点的左子树不为空,则左子树上的所有节点的值域都小于根节点的值   ②若根节点的右子树不为空,则右子树上的所有节点的值域都大于根节点的值   ③根节点的左右子树分别也是一颗二叉搜索树 例如下面的这棵二叉树就是一棵二叉搜索树: 注意:判

  • Java 求解如何把二叉搜索树转换为累加树

    Java 求解如何把二叉搜索树转换为累加树

    一.题目 给出二叉搜索树的根节点,该树的节点值各不相同,请你将其转换为累加树(Greater Sum Tree),使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和. 提醒一下,二叉搜索树满足下列约束条件: 节点的左子树仅包含键 小于 节点键的节点. 节点的右子树仅包含键 大于 节点键的节点. 左右子树也必须是二叉搜索树. 二.题解 观察示例图发现,树的遍历顺序为右,中,左的顺序,每个节点的值,是按照这个顺序累加的状态 由于是需要累加,所以需要pre指针记录当前遍历节点

  • Python实现二叉搜索树BST的方法示例

    二叉排序树(BST)又称二叉查找树.二叉搜索树 二叉排序树(Binary Sort Tree)又称二叉查找树.它或者是一棵空树:或者是具有下列性质的二叉树: 1.若左子树不空,则左子树上所有结点的值均小于根结点的值: 2.若右子树不空,则右子树上所有结点的值均大于根节点的值: 3.左.右子树也分别为二叉排序树. 求树深度 按序输出节点值(使用中序遍历) 查询二叉搜索树中一个具有给点关键字的结点,返回该节点的位置.时间复杂度是O(h),h是树的高度. 递归/迭代求最大关键字元素 递归/迭代求最小关

随机推荐