二叉树及Python实现

发表于 | 分类于

本文介绍二叉树的基本概念以及使用Python实现二叉树的基本功能，包括遍历、计算深度、查找节点等。

二叉树的实现

1
2
3
4
5
class Node:
    def __init__(self, value=None, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

二叉树的遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def preTraverse(root):
    """
    前序遍历
    """
    if root==None:
        return
    print(root.value)
    preTraverse(root.left)
    preTraverse(root.right)
    
def midTraverse(root):
    """
    中序遍历
    """
    if root==None:
        return
    midTraverse(root.left)
    print(root.value)
    midTraverse(root.right)
    
def afterTraverse(root):
    """
    后序遍历
    """
    if root==None:
        return
    afterTraverse(root.left)
    afterTraverse(root.right)
    print(root.value)
1
root = Node('D',Node('B',Node('A'),Node('C')),Node('E',right=Node('G',Node('F'))))
1
preTraverse(root)
D
B
A
C
E
G
F
1
midTraverse(root)
A
B
C
D
E
F
G
1
afterTraverse(root)
A
C
B
F
G
E
D

根据前序遍历和中序遍历构建二叉树

1
2
3
4
5
6
7
8
9
10
11
def constructTree(preorder, midorder):
    if len(preorder) == 0:
        return
    root_data = preorder[0]
    for i in range(len(midorder)):
        if midorder[i] == root_data:
            break
    left = constructTree(preorder[1:i+1], midorder[:i])
    right = constructTree(preorder[i+1:], midorder[i+1:])
    
    return Node(root_data, left, right)
1
2
3
4
5
6
7
8
preorder = [1, 2, 4, 7, 3, 5, 6, 8]
midorder = [4, 7, 2, 1, 5, 3, 8, 6]
tree = constructTree(preorder, midorder)
print(tree.value)
print(tree.left.value,tree.right.value)
print(tree.left.left.value)
print(tree.left.left.right.value)
print(tree.right.left.value)
1
2 3
4
7
5

二叉树的深度

1
2
3
4
5
6
7
8
9
def treeDepth(tree):
    if tree==None:
        return 0
    leftDepth = treeDepth(tree.left)
    rightDepth = treeDepth(tree.right)
    if leftDepth > rightDepth:
        return leftDepth+1
    if rightDepth >= leftDepth:
        return rightDepth+1
1
treeDepth(root)
4

二叉树查找

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

如果这个结点有右子树，而右子树上有左结点，则一直沿着右子树的左结点出发寻找最左的左结点就是该结点的下一个结点，若右子树上没有左结点则该节点的下一个结点是这个右子树的根结点。

如果这个结点没有右子树，而该结点是其父结点的左结点，则该结点的下一个结点就是其父结点。

若该节点也不是其父结点的左结点，则一直向上寻找，知道找到其父结点是父结点的父结点的左结点，则该父结点的父结点就是该结点的下一个结点。

1
2
3
4
5
6
class TreeLinkNode:
    def __init__(self, value, left=None, right=None, pnext=None):
        self.value = value
        self.left = left
        self.right = right
        self.next = pnext // 父节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def getNext(pNode):
    if pNode is None:
        return
    # 存在右节点，一直往下遍历，直到找到最左节点
    if pNode.right is not None:
        temp = pNode.right
        while temp.left:
            temp = temp.left
        return temp
    # 父节点为空，返回空
    elif pNode.next is None:
        return
    # 左节点的下一个节点为父节点
    elif pNode.next.left == pNode:
        return pNode.next
    # 右节点
    else:
        while pNode.next:
            # 直到该节点为左节点
            if pNode.next.left != pNode:
                pNode = pNode.next
            else:
                return pNode.next
        return