您的位置：首页 > 脚本大全 > > 正文

python 二叉树的深度遍历（python 将有序数组转换为二叉树的方法）

更多时间：2021-10-27 10:49:31 类别：脚本大全浏览量：1366

python 二叉树的深度遍历

python 将有序数组转换为二叉树的方法

题目：将[0,1,2,3,4,5,6,7,8,9,10]存储到二叉树，原数组有序，转换为二叉排序树。

二叉排序树的特点：当前节点的左子树上的所有节点都小于该节点，右子树上的所有节点都小于该节点。

二叉排序也称为二叉查找树。

我的实现思路：

取有序数组的中间节点作为根节点，将数组分为左右两个部分，对左右两个子数组做相同的操作，递归的实现。

图示：

python 二叉树的深度遍历（python 将有序数组转换为二叉树的方法）

代码实现：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18 def array_to_bitree(array):

#判断arr是否为空

if len(array)==0:

return bitnode(array[0])

mid=len(array)//2 # 有序数组的中间元素的下标

#print(mid)

#start=0 # 数组第一个元素的下标

#end=-1 # 数组最后一个元素的下标

if len(array)>0:

#将中间元素作为二叉树的根

root=bitnode(array[mid])

#如果左边的元素个数不为零，则递归调用函数，生成左子树

if len(array[:mid])>0:

root.left_child = arraytobitree(array[:mid])

#如果右边的元素个数不为零，则递归调用函数，生成左子树

if len(array[mid+1:])>0:

root.right_child = arraytobitree(array[mid+1:])

return root

我们调用前面写的三种遍历方法看一看，我们构造的树是否正确：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18 #将[0,1,2,3,4,5,6,7,8,9,10]存储到二叉树

if __name__ == '__main__':

#先构造一个有序数组、链表

arr=[]

for i in range(10):

arr.append(i)

print(arr)

#调用函数

bt=arraytobitree(arr)

#前序遍历二叉树

print("前序")

print_tree_pre_order(bt)

# 中序遍历二叉树

print("中序")

print_tree_mid_order(bt)

# 后序遍历二叉树

print("后序")

print_tree_after_order(bt)

输出：

python 二叉树的深度遍历（python 将有序数组转换为二叉树的方法）

根据这三种遍历结果可以判断出二叉树的结构，结果和前面的是一样的，代码如下：

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

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93 #定义二叉树结点类型

class bitnode:

"""docstring for bitnode"""

def __init__(self,arg):

self.data = arg

self.left_child = none

self.right_child = none

#前序遍历

def print_tree_pre_order(root):

#先判断二叉树是否为空

#if root.left_child is none and root.right_child is none:

if root is none:

return root

#先根

print(root.data)

#再左

if root.left_child is not none:

print_tree_pre_order(root.left_child)

#再右

if root.right_child is not none:

print_tree_pre_order(root.right_child)

#中序遍历二叉树

def print_tree_mid_order(root):

#先判断二叉树是否为空,当左右节点都为空时

if root is none:

return

#中序遍历左根右

#遍历左子树

if root.left_child is not none:

print_tree_mid_order(root.left_child)

#遍历根节点

print(root.data)

#遍历右子树

if root.right_child is not none:

print_tree_mid_order(root.right_child)

#后序遍历

def print_tree_after_order(root):

#先判断二叉树是否为空

if root is none:

return root

#再左

if root.left_child is not none:

print_tree_after_order(root.left_child)

#再右

if root.right_child is not none:

print_tree_after_order(root.right_child)

#先根

print(root.data)

def array_to_bitree(array):

#判断arr是否为空

if len(array)==0:

return bitnode(array[0])

mid=len(array)//2 # 有序数组的中间元素的下标

#print(mid)

#start=0 # 数组第一个元素的下标

#end=-1 # 数组最后一个元素的下标

if len(array)>0:

#将中间元素作为二叉树的根

root=bitnode(array[mid])

#如果左边的元素个数不为零，则递归调用函数，生成左子树

if len(array[:mid])>0:

root.left_child = array_to_bitree(array[:mid])

#如果右边的元素个数不为零，则递归调用函数，生成左子树

if len(array[mid+1:])>0:

root.right_child = array_to_bitree(array[mid+1:])

return root

#将[0,1,2,3,4,5,6,7,8,9,10]存储到二叉树

if __name__ == '__main__':

#先构造一个有序数组、链表

arr=[]

for i in range(9):

arr.append(i)

print(arr)

#调用函数

bt=array_to_bitree(arr)

#前序遍历二叉树

print("前序")

print_tree_pre_order(bt)

# 中序遍历二叉树

print("中序")

print_tree_mid_order(bt)

# 后序遍历二叉树

print("后序")

print_tree_after_order(bt)

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持开心学习网。

原文链接：https://www.jianshu.com/p/b7492d68a39f

标签：Python 二叉树有序数组

上一篇：mysql建立索引的主要目的（浅谈Mysql哪些字段适合建立索引）

下一篇：python将txt数据写入excel（Python将列表数据写入文件txt, csv，excel）

您可能感兴趣

python 二叉树的深度遍历（python 将有序数组转换为二叉树的方法）

python 二叉树的深度遍历

热门推荐

排行榜