• Why need Binary Tree?
• 树也是节点结构
• 规定
• 术语
• 树的创建
• 树的查找
• 查找效率

Why need Binary Tree?

有时候，我们希望数据按照特定顺序排列。
比如：

• 想要按字母顺序排列人名；
• 按价格顺序排列产品；
• ...

树也是节点结构

规定

• 二叉树的每个节点的子节点数量都是0、1、2；
• 每个节点最多有一个左子节点和右子节点；
• 一个节点的左子树的值都 小于 节点本身，
• 一个节点的右子树的值都 大于 节点本身；
• 这一规律适用于所有节点。

术语

• 层级
  

• 平衡
  

树的创建

class TreeNode:
	def _init_(self, val, left=None, right=None):
		self.value = val
		self.leftChild = left
		self.rightChild = right

构建一棵简单的树:

node1 = TreeNode(25)
node2 = TreeNode(75)
root = TreeNode(50, node1, node2)

树的查找

给你一颗二叉树，

需要查找61，

查找步骤：

1. 算法开始时，根节点就是第一个“当前节点”；
   
   检查当前节点的值，如果时这个值，那就找到了。

2. 如果要找到值小于当前节点值，那么就在其左子树中继续查找。

3. 如果要找的值大于当前节点的值，那么就在其右子树中继续查找。

查找效率

每一步排除了大约一半的剩余节点，因此，二叉查找树的查找需要O（log N）时间。