Python语言建立二叉树的几种方式（适用于需要建树的场景）

目录

参考链接前提二叉树的存储结构创建一个节点建立二叉树的几种方式已知层次遍历顺序，建立二叉树使用队列使用数组

已知中序、后序建立二叉树参考练习题目模板代码

已知中序、前序建立二叉树参考练习题目模板代码

已知节点关系，建立二叉树（邻接表存储）参考练习题目模板代码

参考链接

https://blog.csdn.net/qq_21989927/article/details/108197861

前提

用null表示为空节点 上图中树的先序遍历为：1 2 3 4 5 上图中树的中序遍历为：2 1 4 3 5 上图中树的后序遍历为：2 4 5 3 1

若考虑每个节点下面的空节点，则先序遍历为： 1 2 null null 3 4 null null 5 null null

二叉树的存储结构

# Definition for a binary tree node.

class TreeNode:

def __init__(self, val=0, left=None, right=None):

self.val = val

self.left = left

self.right = right

创建一个节点

node = TreeNode(val)

建立二叉树的几种方式

已知层次遍历顺序，建立二叉树

这里又分两种方法： （1）边读入数据边建立二叉树，需要用到队列； （2）已知的层次遍历顺序在数组中存放好了。

使用队列

这种方法样例对应的读入是（中括号中的null可有可无）： 1 2 3 null null 4 5 [null null null null] 参考题目： LeetCode 297. 二叉树的序列化与反序列化

def deserialize(self, data):

"""Decodes your encoded data to tree.

:type data: str

:rtype: TreeNode

"""

def createTreeByLevelTraversal(node, strList):

deque = collections.deque([node])

i = 0

while deque and i < len(strList):

curNode = deque.popleft()

i += 1

if i < len(strList):

nxtStrval = strList[i]

if nxtStrval != 'null':

leftNode = TreeNode(int(nxtStrval))

curNode.left = leftNode

deque.append(leftNode)

i += 1

if i < len(strList):

nxtStrval = strList[i]

if nxtStrval != 'null':

rightNode = TreeNode(int(nxtStrval))

curNode.right = rightNode

deque.append(rightNode)

strList = [str(i) for i in data[1:-1].split(',')]

for i in reversed(range(len(strList))): # 去掉多余的null

if strList[i] == 'null':

strList.pop()

else:

break

length = len(strList)

if length == 0: # 若为空，直接返回None

return None

root = TreeNode(int(strList[0]))

# 调用创建函数

createTreeByLevelTraversal(root, strList)

return root

使用队列的方法，首先要入读一个值，判断这棵树是否存在，若是null，说明空树，不为null，创建节点后入队。 当队列不为空时，队列中每一个元素都需要再读取两个数字（就算是叶子节点也起码也得读两个null）。 这种方法建立二叉树，执行过程中会发现，每次读取的两个数，对应的都是队首元素的左右孩子，这和给定的层次遍历顺序对应。

使用数组

给定的层次遍历已经存放在数组a中，我们只需要判断一个节点的左右孩子是否存在即可，左孩子为i * 2，右孩子为i * 2 + 1。

这种方法样例对应的读入是： 1 2 3 null null 4 5 （这里只是碰巧和使用队列的读入一样，多数时候是不一样的）

注意要从a[1]开始存储，a[0]不用。

a = [0, 1, 2, 3, 'null', 'null', 4, 5]

def createTreeByLevelTraversal(node, i, a):

if a[i] == 'null':

return None

node = TreeNode(a[i])

if i * 2 <= len(a) - 1:

node.left = createTreeByLevelTraversal(node.left, i * 2)

if i * 2 + 1 <= len(a) - 1:

node.right = createTreeByLevelTraversal(node.right, i * 2 + 1)

return node

# 调用创建函数

createTreeByLevelTraversal(root, 1, a)

已知中序、后序建立二叉树

参考练习题目

PAT甲级 1020 Tree Traversals 已知二叉树的中序、后序转层序

模板代码

# Definition for a binary tree node.

class TreeNode:

def __init__(self, val=0, left=None, right=None):

self.val = val

self.left = left

self.right = right

inOrder = [2, 1, 4, 3, 5]

postOrder = [2, 4, 5, 3, 1]

# 已知中序、后序建立二叉树

def buildTree(r, start, end):

if start > end:

return None

i = start

while i < end and postOrder[r] != inOrder[i]:

i += 1

root = TreeNode(postOrder[r])

root.left = buildTree(r - (end - i + 1), start, i - 1)

root.right = buildTree(r - 1, i + 1, end)

return root

# 返回建立好的二叉树的根节点root

root = buildTree(4, 0, 4) # buildTree(n - 1, 0, n - 1) n为节点数

已知中序、前序建立二叉树

参考练习题目

牛客网编程题 满二叉树转换为求和树 通过前序、中序建立二叉树

模板代码

# Definition for a binary tree node.

class TreeNode:

def __init__(self, val=0, left=None, right=None):

self.val = val

self.left = left

self.right = right

inOrder = [2, 1, 4, 3, 5]

preOrder = [1, 2, 3, 4, 5]

# 已知中序、前序建立二叉树

def buildTree(r, start, end):

if start > end:

return None

i = start

while i < end and preOrder[r] != inOrder[i]:

i += 1

root = TreeNode(preOrder[r])

root.left = buildTree(r + 1, start, i - 1)

root.right = buildTree(r + (i - start) + 1, i + 1, end)

return root

# 返回建立好的二叉树的根节点root

root = buildTree(0, 0, 4) # buildTree(0, 0, n - 1) n为节点数

已知节点关系，建立二叉树（邻接表存储）

假设题目输入中，我们只知道 x , y 之间有一条边，但是并不知道 x , y 的父子关系的时候，可以使用邻接表的方法存储树，这时候可以把树看做一个图。

参考练习题目

洛谷 P3379 【模板】最近公共祖先（倍增LCA）

模板代码

这里使用了前向星，总体时间并不会逊色于邻接表，不会的可以点击： 什么是前向星

class Edge:

def __init__(self, to, nxt, weight):

self.to = to # edgeList[i].to表示第i条边的终点

self.nxt = nxt # edgeList[i].next表示与第i条边同起点的下一条边的存储位置

self.weight = weight # edgeList[i].to表示边权值

maxNode, maxEdge = 100, 100

head = [-1] * maxNode

edgeList = []

cnt = 0

# 加边

def add(u, v, weight){

edgeList.append(Edge(u, head[u], weight))

head[u] = cnt

cnt += 1

}

def dfs(u, pre): # u为当前节点,pre当前节点的父节点

i = head[u]

while i != -1:

if edgeList[i].to != pre:

v = edgeList[i].to

dfs(v, u)

# 前向星存边

for i in range(m): # m为边的数量

# 假设读入编号为a， b的两个节点

a = int(input())

b = int(input())

add(a, b)

add(b, a)

dfs(r, 0); # r为根节点的序号，从根节点执行深度优先搜索