二叉树查找之python实现--（插入）
浏览数：99 /
时间：2015年06月08日
借维基百科的话来说就是二叉树就是一种每个节点最多有两个子树的树结构。但是今天讨论的是二叉查找树，这个查找树就是二叉树的一种延伸吧，加了几条限制就变成了二叉查找树。
下面我们来看看二叉查找树有什么性质呢，如果左子树不为空，那么一定全部小于等于根节点，同样右子树也是一样的，而且左右子树都是二叉查找树。最后树中没有键值相同的节点。如果满足上述四条性质的二叉树就是二叉查找树。下面我们来一张二叉查找树的图片吧，现在不是都讲究有图有真相吗。
我们还是得从头开始，因为它二叉树是一种数据结构，那么就一定有定义，我们来看一下它是怎么定义的呢，其实就是数据、左子树、右子树。它就是一个类，如果你想创建一个节点root = Node(8)，像这样你就创建了一个根节点。
class Node:
"""
二叉树左右枝
"""
def __init__(self, data):
"""
节点结构
"""
self.left = None
self.right = None
self.data = data 现在节点的定义已经ok了，那我们来看一下插入函数吧，insert。其实插入函数里就是二分的思想，因为二叉查找树的性质，我们可以使用二分的方法来寻找插入的位置。里面还有递归的意思，大概意思就是不到叶子节点就一直往下找，找到合数的就将其data的值插入相应的节点中。
def insert(self, data):
"""
插入节点数据
"""
if data < self.data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
elif data > self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data) 我们可以继续构造我们的小树啊，继续插入几个节点来完善这个小小树。
root.insert(3) root.insert(10) root.insert(1)我们可以来模拟一下插入的过程啊，插入3时和8比较小于8且8的左节点为空，所以插入到8的左节点上。插入10的时候呢就直接插到8的右节点上了，插入1的时候先和8比较小于8，且8的左子树不为空，递归调用8的左子树，之后和3比较，比3小且3的左子树为空，插入到3的左节点。
root.insert(6) root.insert(4) root.insert(7) root.insert(14) root.insert(13)
又到点了，小伙伴们该睡觉了，那么明天再写遍历神马的吧。
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
