- A+
最近比较懒，一直没有更新，耐不住迷妹们在后台频繁的鼓励，今天我们来蹭个热点，了解下二叉树。 最近最火的一个新闻莫过于某著名程序员面试Google被拒，原因是不会反转二叉树。
今天我们就来学习二叉树。
什么是二叉树
二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。
二叉树常被用于实现二叉查找树和二叉堆。
如何定义一个二叉树
根据定义，我们知道二叉树最重要的是根节点，左节点和右节点，我们来实现一个类来代表二叉树：
12345 |
class BinaryTree(object):def __init__(self, val, left=None, right=None):self.val = valself.left = leftself.right = right |
实现二叉查找树（Binary Search Tree）
首先， 二叉查找树，又称二叉排序树（Binary Sort Tree）， 二叉搜索树，
它有如下特点：
（0）它是一颗空树，如果不是，它一定符合下列性质：
（1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
先看一个二叉查找树的例子：
下面来实现它：
12345678910111213 |
class BST:def insert_tree(self, root, value):if root.val > value:if not root.left:root.left = Node(value)else:self.insert_tree(root.left, value)if root.val < value:if not root.right:root.right = Node(value)else:self.insert_tree(root.right, value) |
那么，二叉树如何实现查找呢？根据二叉树的特点，我们知道：
1.如果要查找的值等于根节点的值，成功退出。
2.如果要查找的值小于根节点的值， 递归查找左分支树， 否则，递归查找右分支树，
3.如果发现等同于要查找的值，成功退出。
4.如果子树为空，返回空。
在查找之前，我们先看看如何遍历二叉树：
1234567891011121314151617181920212223242526272829 |
#先访问根节点，再遍历左子树，最后遍历右子树；#并且在遍历左右子树时，仍需先访问根节点，然后遍历左子树，最后遍历右子树。def preorder(self, root):if not root:return []result = [root.val]left_result = self.preorder(root.left)right_result = self.preorder(root.right)return result + left_result + right_result#中序遍历：先遍历左子树、然后访问根节点，最后遍历右子树；#并且在遍历左右子树的时候。仍然是先遍历左子树，然后访问根节点，最后遍历右子树。def midorder(self, root):if not root:return []left_result = self.midorder(root.left)result = [root.val]right_result = self.midorder(root.right)return left_result + result + right_result#后续遍历：先遍历左子树，然后遍历右子树，最后访问根节点；#同样，在遍历左右子树的时候同样要先遍历左子树，然后遍历右子树，最后访问根节点。def postorder(self, root):if not root:return []left_result = self.postorder(root.left)right_result = self.postorder(root.right)result = [root.val]return left_result + right_result + result |
查找：
123 |
def search_node(self, root, value):if value in self.postorder(root):return True |
最后，我们来看下大神回答不出来的那个问题， 交换二叉树的左右节点。
1234567 |
def switch_node(self, root):if not root:return Noneroot.left, root.right = root.right, root.leftself.switch_node(root.left)self.switch_node(root.right)return self.preorder(root) |
由此可以看出， 二叉树的操作，最多的用到的是递归,递归的本质是自己调用自己，下面给一个函数来理解：
12345678910111213141516171819202122 |
#求阶乘def factorial(n):if n<=1:return 1else:return n*factorial(n-1)如何理解呢？n = 5;x = factorial (n);x = factorial (5); x = (5 * factorial (4)); # recursion starts, until logic requirement satisfiedx = (5 * (4 * factorial (3)));x = (5 * (4 * (3 * factorial (2))));x = (5 * (4 * (3 * (2 * factorial (1)))));x = (5 * (4 * (3 * (2 * (1))))); # all calls made, logic ceases the recursionx = (5 * (4 * (3 * (2 * 1)))); # returns start as resolutions/calculations beginx = (5 * (4 * (3 * 2)));x = (5 * (4 * 6));x = (5 * 24);x = (120); # final resolution/calculation before returnx = 120; |
递归的理解不尽相同， 不过读者大可不必去关心函数如何一层层调用的，因为
Recursion is the process of solving a problem in terms of smaller versions of the same problem. Since the problem gets smaller each time, the process eventually terminates in a problem (the “base case”) that can be solved directly. Be sure of three things:
The problem gets smaller each time.
You include a solution for the base case.
Each case is handled correctly.
That’s really all there is to it.
写在最后
前几天有私信小编要Python的学习资料，小编整理了一些有深度的Python教程和参考资料，从入门到高级的都有，文件已经打包好了，正在学习Python的同学可以下载学习学习。文件下载方式：点击小编头像，关注后私信回复“资料”即可下载。首先把代码撸起来！首先把代码撸起来！首先把代码撸起来！重要的事说三遍，哈哈。“编程是门手艺活”。什么意思？得练啊。
