微信号:TesterTalk

介绍:专注软件测试技术分享,包括不限于Web 测试,Mobile测试,API测试,自动化测试,性能测试知识/方法, 以及软件测试职位推荐.

Python算法分享系列 -- 二叉树

2018-02-07 21:39 iTesting

iTesting,爱测试,爱分享


最近比较懒,一直没有更新,耐不住迷妹们在后台频繁的鼓励,今天我们来蹭个热点,了解下二叉树。 最近最火的一个新闻莫过于某著名程序员面试Google被拒,原因是不会反转二叉树。
今天我们就来学习二叉树。

什么是二叉树

二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。
二叉树常被用于实现二叉查找树和二叉堆。

如何定义一个二叉树

根据定义,我们知道二叉树最重要的是根节点,左节点和右节点,我们来实现一个类来代表二叉树:

1

2

3

4

5

class BinaryTree(object):

def __init__(self, val, left=None, right=None):

self.val = val

self.left = left

self.right = right


实现二叉查找树(Binary Search Tree)

首先, 二叉查找树,又称二叉排序树(Binary Sort Tree), 二叉搜索树,
它有如下特点:
(0)它是一颗空树,如果不是,它一定符合下列性质:
(1)若左子树不空,则左子树上所有结点的值均小于或等于它的根结点的值;
(2)若右子树不空,则右子树上所有结点的值均大于或等于它的根结点的值;
(3)左、右子树也分别为二叉排序树;

先看一个二叉查找树的例子:

下面来实现它:

1

2

3

4

5

6

7

8

9

10

11

12

13

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.如果子树为空,返回空。

在查找之前,我们先看看如何遍历二叉树:

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

#先访问根节点,再遍历左子树,最后遍历右子树;

#并且在遍历左右子树时,仍需先访问根节点,然后遍历左子树,最后遍历右子树。

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

查找:

1

2

3

def search_node(self, root, value):

if value in self.postorder(root):

return True


最后,我们来看下大神回答不出来的那个问题, 交换二叉树的左右节点。

1

2

3

4

5

6

7

def switch_node(self, root):

if not root:

return None

root.left, root.right = root.right, root.left

self.switch_node(root.left)

self.switch_node(root.right)

return self.preorder(root)


由此可以看出, 二叉树的操作,最多的用到的是递归,递归的本质是自己调用自己,下面给一个函数来理解:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

#求阶乘

def factorial(n):

if n<=1:

return 1

else:

return n*factorial(n-1)

如何理解呢?

n = 5;

x = factorial (n);

x = factorial (5);                        

x = (5 * factorial (4));                   # recursion starts, until logic requirement satisfied

x = (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 recursion

x = (5 * (4 * (3 * (2 * 1))));             # returns start as resolutions/calculations begin

x = (5 * (4 * (3 * 2)));

x = (5 * (4 * 6));

x = (5 * 24);

x = (120);                                 # final resolution/calculation before return

x = 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.




文末惯例放赞赏码:)


 
iTesting 更多文章 Python算法分享系列 -- 查找,排序,递归 测试往何处去 -- 新时期测试如何面对挑战 Python自动化测试--关于datetime的一点思考2 QA如何做静态代码分析 Python自动化测试--关于datetime的一点思考
猜您喜欢 超50个项目!IBM开源商业软件移至云端 完美解决无法解析的外部符号 __imp___vsnprintf问题 IPCS与Linux共享内存 全球皆可访问的Google codelabs网站 我被下面的代码搞晕了,为什么它们会返回不同的值