个人中心
gpt4 book ai didi

python实现二叉查找树实例代码

转载 作者：qq735679552 更新时间：2022-09-28 22:32:09 24 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章python实现二叉查找树实例代码由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

本文研究的主要是python实现二叉查找树的相关内容，具体介绍及实现如下.

1. 二叉查找树的定义:

左子树不为空的时候，左子树的结点值小于根节点，右子树不为空时，右子树的结点值大于根节点，左右子树分别为二叉查找树 。

2. 二叉查找树的最左边的结点即为最小值，要查找最小值，只需遍历左子树的结点直到为空为止，同理，最右边的结点结尾最大值，要查找最大值，只需遍历右子树的结点直到为空为止。二叉查找树的插入查找和删除都是通过递归的方式来实现的，删除一个结点的时候，先找到这个结点S，如果这个结点左右孩子都不为空，这时并不是真正的删除这个结点S，而是在其右子树找到后继结点，将后继结点的值付给S，然后删除这个后继结点即可。如果结点S的左孩子或者右孩子为空，可以直接删除这个结点S.

3. 二叉查找树的python实现:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class TreeNode:
   def __init__( self ,val):
     self .val = val;
     self .left = None ;
     self .right = None ;
def insert(root,val):
   if root is None :
     root = TreeNode(val);
   else :
     if val<root.val:
       root.left = insert(root.left,val);  #递归地插入元素
     elif val>root.val:
       root.right = insert(root.right,val); 
   return root;
 
def query(root,val):
   if root is None :
     return ;
   if root.val is val:
     return 1 ;
   if root.val <val:
     return query(root.right,val); #递归地查询
   else : 
     return query(root.left,val);
def findmin(root):
   if root.left:
     return findmin(root.left);
   else :
     return root;
   
def delnum(root,val):
   if root is None :
     return ;
   if val<root.val:
     return delnum(root.left,val);
   elif val>root.val:
     return delnum(root.right,val);
   else :                       # 删除要区分左右孩子是否为空的情况
     if (root.left and root.right):
       
       tmp = finmin(root.right);       #找到后继结点
       root.val = tmp.val;
       root.right = delnum(root.right,val);  #实际删除的是这个后继结点
       
     else :
       if root.left is None :
         root = root.right;
       elif root.right is None :
         root = root.left;
   return root;
         
         
#测试代码      
root = TreeNode( 3 );
root = insert(root, 2 );
root = insert(root, 1 );
root = insert(root, 4 );
 
#print query(root,3);
print query(root, 1 );
root = delnum(root, 1 );
print query(root, 1 );

结果:

1 None >>> 。

总结 。

以上就是本文关于python实现二叉查找树实例代码的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题，如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！ 。

原文链接：http://blog.csdn.net/u011608357/article/details/35785553 。

最后此篇关于python实现二叉查找树实例代码的文章就讲到这里了,如果你想了解更多关于python实现二叉查找树实例代码的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

24 4 0
文章推荐： Python的CGIHTTPServer交互实现详解
文章推荐： Python获取CPU、内存使用率以及网络使用状态代码
文章推荐： Redmi MAX 86 英寸智能电视明天开卖：4K 120Hz， 7999 元
文章推荐： 单链表反转python实现代码示例
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com