Python算法练习--把搜索树转成双向链表

时间:2021-12-10 12:51:36

本文目前分享的题目都是来自于July的分享,然后把具体算法实现。搜索树转双向链表主要的实现逻辑是在中序遍历时,调整节点的左右子树;因为中序遍历是递归调用,所以在调整时一定要注意调整的位置,如果写错了,很有可能造成死循环。避免的主要办法是在读完左子树时调整左节点,遍历完右子树时调整右节点,具体代码见trans函数。算法的时间复杂度是o(logn)。

输入树构建完成后是:

Python算法练习--把搜索树转成双向链表

代码如下:

# -*- coding: utf-8 -*-
"""
题目:输入一棵二叉搜索树(记住是搜索树),将该二叉搜索树转换为一个排序的双向链表。要求:不能创建任何新的结点,只能调整树中结点指针的指向。
1 2 3 4 5 6 7 输入顺序 4 3 1 2 5 6 7用这个顺序建立二叉查找树
基本思路:用中序遍历的方式,每一个节点左侧连接的应该是左子数的最右边一个节点,而右边连接的应该是右子树最左边的节点
"""
class TreeNode:
"""
树的节点定义,后面的很多操作都是基于节点的
""" def __init__(self):
"""
定义一个树的节点,初始状态左右节点为空
"""
self.leftNode = None
self.rightNode = None def setData(self, data):
"""
设置数字的方法
args: data节点值
"""
self.data = data def setLeftNode(self, leftNode):
"""
设置左节点的方法
args: leftNode 左节点
"""
self.leftNode = leftNode def setRightNode(self, rightNode):
"""
设置右节点的方法
args: rightNode 右节点
"""
self.rightNode = rightNode def getData(self):
"""
获取节点数字
return:返回节点数字
"""
return self.data def getLeftNode(self):
"""
获取左节点
return:返回左节点
"""
return self.leftNode def getRightNode(self):
"""
获取右节点
return:返回右节点
"""
return self.rightNode class BuildTree:
"""
以输入顺序构建二叉查找树,左边的比根节点小,右侧的比根节点大
""" def build(self, dataList):
"""
开始构建树
args:dataList 树的节点值
"""
#遍历输入数组
for i in range(len(dataList)):
currData = dataList[i]
#初始化一个节点
newTreeNode = TreeNode()
newTreeNode.setData(currData);
#如果是一个输入,则作为树的根节点
if i==0:
self.tree = newTreeNode
#否则进行大小的比较,构建二叉查找树
else:
flagNode = self.tree
while flagNode is not None:
if currData <= flagNode.getData():
#如果当然值小于等于根节点,并且左节点为空的话,则进行左节点赋值
if flagNode.getLeftNode() is None:
flagNode.setLeftNode(newTreeNode)
break;
else:
#否则继续找左节点
flagNode = flagNode.getLeftNode()
else:
#如果当然值大于根节点,并且右节点为空的话,则进行右节点赋值
if flagNode.getRightNode() is None:
flagNode.setRightNode(newTreeNode)
break;
else:
#否则继续找右节点
flagNode = flagNode.getRightNode() def trans(self, tempNode):
"""
递归进行中序遍历
在左子树遍历完时,找左子树最右边的节点,做为节点的左子树
在右子树遍历完时,找左子树最右变的节点,做为节点的右子树
args:tempNode 初始为树的根节点
"""
if tempNode is not None:
#递归遍历左子树
self.trans(tempNode.getLeftNode())
#左子树遍历完成,进行左侧最右节点的查找
if tempNode.getLeftNode() is not None:
tempNode2 = tempNode.getLeftNode()
while tempNode2.getRightNode() is not None:
tempNode2 = tempNode2.getRightNode()
tempNode.setLeftNode(tempNode2)
tempNode2.setRightNode(tempNode)
#递归遍历右子树
self.trans(tempNode.getRightNode())
#右子树遍历完成,进行右侧最左节点的查找
if tempNode.getRightNode() is not None:
tempNode2 = tempNode.getRightNode()
while tempNode2.getLeftNode() is not None:
tempNode2 = tempNode2.getLeftNode()
tempNode.setRightNode(tempNode2)
tempNode2.setLeftNode(tempNode) def callTrans(self):
"""
用根节点对trans进行调用
"""
self.trans(self.tree); def test(self):
"""
进行数据的测试,分别从左到右读和从右到左读取数据
"""
tempNode = self.tree
while tempNode.getLeftNode() is not None:
#找到最左节点
tempNode = tempNode.getLeftNode()
#print tempNode.getData()
#从左向右读
while tempNode.getRightNode() is not None:
print tempNode.getData()
tempNode = tempNode.getRightNode()
print tempNode.getData()
#从右向左读
while tempNode is not None:
print tempNode.getData()
tempNode = tempNode.getLeftNode() if __name__ == "__main__":
#初始化数组
dataList = [10,6,4,8,2,5,7,9,20,15,28,14,16,24,29]
test = BuildTree()
#构建排序数
test.build(dataList)
#递归构建双向链表
test.callTrans()
#测试输出
test.test()             

输出结果:

2 4 5 6 7 8 9 10 14 15 16 20 24 28 29 29 28 24 20 16 15 14 10 9 8 7 5 4 2

欢迎关注订阅号“白话算法”

Python算法练习--把搜索树转成双向链表