好资源导航 » 文章资讯 » python实现二叉查找树实例代码

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

2023-09-16 15:15:05 54

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

1.二叉查找树的定义：

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

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

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

classTreeNode:
def__init__(self,val):
self.val=val;
self.left=None;
self.right=None;
definsert(root,val):
ifrootisNone:
root=TreeNode(val);
else:
ifvalroot.val:
root.right=insert(root.right,val);
returnroot;

defquery(root,val):
ifrootisNone:
return;
ifroot.valisval:
return1;
ifroot.valroot.val:
returndelnum(root.right,val);
else:#删除要区分左右孩子是否为空的情况
if(root.leftandroot.right):

tmp=finmin(root.right);#找到后继结点
root.val=tmp.val;
root.right=delnum(root.right,val);#实际删除的是这个后继结点

else:
ifroot.leftisNone:
root=root.right;
elifroot.rightisNone:
root=root.left;
returnroot;


#测试代码
root=TreeNode(3);
root=insert(root,2);
root=insert(root,1);
root=insert(root,4);

#printquery(root,3);
printquery(root,1);
root=delnum(root,1);
printquery(root,1);

结果：

1
None
>>>

总结

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

返回顶部
514930285
czq8825@qq.com

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

总结

热门推荐

随机推荐