本文目前分享的题目都是来自于July的分享，然后把具体算法实现。搜索树转双向链表主要的实现逻辑是在中序遍历时，调整节点的左右子树；因为中序遍历是递归调用，所以在调整时一定要注意调整的位置，如果写错了，很有可能造成死循环。避免的主要办法是在读完左子树时调整左节点，遍历完右子树时调整右节点，具体代码见trans函数。算法的时间复杂度是o(logn)。
输入树构建完成后是：
image
代码如下：
# -*- 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
欢迎关注订阅号“白话算法”
baihua.png
网友评论