大飞

关注TA

挑战一切!

  • 世界的顶端
  • 混口饭吃

可爱的留言者

Python 二叉树排序

2018年12月03 21:14 75 0

    一.。二叉树定义:

    二叉查找树(Binary Search Tree),又称为二叉搜索树、二叉排序树。其或者是一棵空树;或者是具有以下性质的二叉树:

       1.若左子树不空,则左子树上所有结点的值均小于或等于它的根结点的值

       2.若右子树不空,则右子树上所有结点的值均大于或等于它的根结点的值

       3.左、右子树也分别为二叉排序树 

     WX20181203-210934@2x.png

二。二叉树的基本遍历

1.先序遍历:先访问跟节点 后左节点 最后右节点  如上图访问顺序:4 2 1 3 9 7 6 5 8
2.中序遍历:先访问左节点 后跟节点 最后右节点 如上图访问顺序:1 2 3 4 5 6 7 8 9
3.后序遍历:先访问左节点 后右节点 最后跟节点 如上图访问顺序:1 3 2 5 6 8 7 9 4

三。二叉树的生成,关键点,左右有分支,左节点比右节点小

     1.构建节点类

class Node:
def __init__(self, value):
self.data = value
self.left = None
self.right = None

# 插入左节点
def insert_left(self, value):
self.left = Node(value)
return self.left

# 插入右节点
def insert_right(self, value):
self.right = Node(value)
return self.right

# 输出节点数据
def show(self):
print(self.data)

  2.插入节点判断语句


# 对二叉树进行排序
def insert(node, value):
# 插入右节点
if value > node.data:
if node.right:
insert(node.right, value)
else:
node.insert_right(value)
# 插入左节点
else:
if node.left:
insert(node.left, value)
else:
node.insert_left(value)

三。展示生成的二叉树数据


{

"data": 4,

"left": {

"data": 2,

"left": {

"data": 1,

"left": null,

"right": null

},

"right": {

"data": 3,

"left": null,

"right": null

}

},

"right": {

"data": 9,

"left": {

"data": 7,

"left": {

"data": 6,

"left": {

"data": 5,

"left": null,

"right": null

},

"right": null

},

"right": {

"data": 8,

"left": null,

"right": null

}

},

"right": null

}

}

最后生成的二叉树结构如上图

4.排序展示

# 中序排序 从小到大 左根右
def mid_order(node):
if node.data:
# 左
if node.left:
mid_order(node.left)
# 根
node.show()
# 右
if node.right:
mid_order(node.right)


# 遍历从大到小排序 右根左
def big_to_small_order(node):
# 右
if node.right:
big_to_small_order(node.right)
# 根
node.show()
# 左
if node.left:
big_to_small_order(node.left)

下面是输出结果:

90988E4D-8018-4AEB-AF63-98211F37CB3D.png

本次实例完整代码如下:

import json

"""
1.二叉树排序
2.二叉树查找
3.二叉树插入
4.二叉树删除
"""


class Node:
def __init__(self, value):
self.data = value
self.left = None
self.right = None

# 插入左节点
def insert_left(self, value):
self.left = Node(value)
return self.left

# 插入右节点
def insert_right(self, value):
self.right = Node(value)
return self.right

# 输出节点数据
def show(self):
print(self.data)


# 对二叉树进行排序
def insert(node, value):
# 插入右节点
if value > node.data:
if node.right:
insert(node.right, value)
else:
node.insert_right(value)
# 插入左节点
else:
if node.left:
insert(node.left, value)
else:
node.insert_left(value)


# 中序排序 从小到大 左根右
def mid_order(node):
if node.data:
# 左
if node.left:
mid_order(node.left)
# 根
node.show()
# 右
if node.right:
mid_order(node.right)


# 遍历从大到小排序 右根左
def big_to_small_order(node):
# 右
if node.right:
big_to_small_order(node.right)
# 根
node.show()
# 左
if node.left:
big_to_small_order(node.left)


if __name__ == '__main__':
L = [4, 2, 9, 1, 7, 6, 5, 3, 8]
# 设置根节点
Root = Node(L[0])
# 生成二叉树
for i in range(len(L) - 1):
insert(Root, L[i + 1])
# 输出排序后的二叉树json
print(json.dumps(Root, default=lambda obj: obj.__dict__))
print('--------------小到大----------------')
# 输出中序排序 从小到大
mid_order(Root)
print('--------------大到小----------------')
# 输出中序排序 从大到小
big_to_small_order(Root)


"""
1.先序遍历:先访问跟节点 后左节点 最后右节点
2.中序遍历:先访问左节点 后跟节点 最后右节点
3.后序遍历:先访问左节点 后右节点 最后跟节点
"""

实例GitHub地址:https://github.com/tzz2015/DTF/tree/develop

点赞(0)
本文标签算法 python
点了个评