Python 编程实现键盘输入元素进行排序(二)二叉树排序

2022-09-14 08:18:19

今天咱们来将点不一样的排序方式——二叉树排序。这个排序方法比较有意思,而且也便于操作。

本文参考《Python数据分析从入门到精通》张啸宇、李静,电子工业出版社5.3.2 排序

二叉树排序

二叉树排序的过程主要是二叉树的构建和遍历过程。本篇文章中所用二叉树遍历方法是二叉树的中序遍历

中序遍历:如果二叉树不为空,则先访问左子树。然后访问根节点,最后访问右子树;否则,程序退出。

其主要代码如下:

definorder(node):#中序遍历if node.data:if node.left:
            inorder(node.left)
        node.show()if node.right:
            inorder(node.right)

构建二叉树(关键部分)

二叉树排序主要是从无到有再到排序。所以构建二叉树便成了关键的一步。

从无到有:

 例如:由一组数据3,5,7,20,43,2,15,30,则二叉树的构建过程如下:

1)、首先将第一个数据3放入根节点:

2)、将数据5与根节点中的数据3进行比较,由于5大于3,因此将5放入3的右子树中。
在这里插入图片描述
3)、将数据7与根节点中的数据3比较,由于7大于3,因此将7放入3的右子树中;由于3已经有了右子树5,所以将7与5进行比较,7大于5,应将7放入5的右子树中。
在这里插入图片描述
4)、将数据20与根节点数据3比较,由于20大于3,因此将20放入3的右子树中;重复比较,最终将20放入7的右子树中。
在这里插入图片描述
5)、将数据43与树中节点值进行比较,最终放入20的右子树中。
6)、将数据2与根节点数据3比较,2小于3,放入左子树中。
7)、同样,将数据15与30进行处理,最终形成如下图的而二叉树。
二叉树排序
其主要代码如下:

definsert(node,value):#构建二叉树if value> node.data:if node.right:
            insert(node.right,value)else:
            node.insertRight(value)else:if node.left:
            insert(node.left, value)else:
            node.insertLeft(value)

排序

当树构建好后,对树进行中序遍历,得到的遍历结果就是对数据从小到大进行排序的结果。如果要从大到小进行排序;则可以先从右子树开始进行中序遍历。

通过采用二叉树排序方式对数据进行排序代码实现如下:
#classBTree:#二叉树节点def__init__(self,value):#初始化函数
        self.left=None#左儿子
        self.data= value#节点值
        self.right=None#右儿子definsertLeft(self,value):#左子树添加
        self.left= BTree(value)return self.leftdefinsertRight(self,value):#右子树添加
        self.right= BTree(value)return self.rightdefshow(self):#输出节点数据print(self.data)definorder(node):#中序遍历,从小到大if node.data:if node.left:
            inorder(node.left)
        node.show()if node.right:
            inorder(node.right)defrinorder(node):#从大到小,中序遍历if node.data:if node.right:
            rinorder(node.right)
        node.show()if node.left:
            rinorder(node.left)definsert(node,value):#构建二叉树if value> node.data:if node.right:
            insert(node.right,value)else:
            node.insertRight(value)else:if node.left:
            insert(node.left, value)else:
            node.insertLeft(value)if __name__=='__main__':
    l1=input("输入列表元素,用“,”(英文)隔开:").split(',')##键盘输入
    l=[int(l1[i])for iinrange(len(l1))]#生成初始列表
    Root= BTree(l[0])
    node= Rootfor iinrange(1,len(l)):
        insert(Root, l[i])print('*'*30)print('**从小到大**')print('*'*30)
    inorder(Root)print('*'*30)print('**从大到小**')print('*'*30)
    rinorder(Root)
最终结果如下:
输入列表元素,用“,”(英文)隔开:3,5,7,20,43,2,15,30
******************************
**从小到大**
******************************
2
3
5
7
15
20
30
43
******************************
**从大到小**
******************************
43
30
20
15
7
5
3
2

结语
编程的世界没有唯一,欢迎大家补充和优化代码。

  • 作者:飨喰__小天
  • 原文链接:https://blog.csdn.net/m0_48278789/article/details/119493259
    更新时间:2022-09-14 08:18:19