树结构多种多样,不过最常用的还是二叉树。顾名思义,二叉树每个节点最多有两个叉,也就是两个子节点,分别是左子节点和右子节点。

树的组成及相关概念

  1. 树的组成

    • 根节点
    • 父节点
    • 子节点
    • 兄弟结点
    • 叶子节点或叶节点
  2. 树的概念

    • 节点的高度:节点到叶子节点最长路径(边数)
    • 节点的深度:根节点到这个节点所经历的边的个数
    • 节点的层数:节点的深度 + 1
    • 树的高度:根节点的高度

树的构建

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
30
31
32
33
34
35
36
37
class Node():
'''
结点类
'''
def __init__(self, value=None, lft=None, rgt = None):
self.value = value
self.lft = lft
self.rgt = rgt

def __str__(self):
return str(self.value)

class Tree():
'''
树类
'''
def __init__(self):
self.root = Node()
self.myqueue = [] # 用来存放子树的三个节点,依次为root, left, right

def add(self, elem):
'''
构建树结构
'''
node = Node(elem)
if self.root.value == None: # 树为空,进行赋值
self.root = node
self.myqueue.append(self.root)
else: # 此树不为空,但子节点还没补齐
treeNode = self.myqueue[0]
if treeNode.lft == None:
treeNode.lft = node
self.myqueue.append(treeNode.lft)
else:
treeNode.rgt = node
self.myqueue.append(treeNode.rgt)
self.myqueue.pop(0) # 该节点如果存在右子树,将此结点丢弃

树的遍历

  1. 递归方式实现深度优先遍历

    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
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    class Node():
    '''
    结点类
    '''
    def __init__(self, value=None, lft=None, rgt = None):
    self.value = value
    self.lft = lft
    self.rgt = rgt

    def __str__(self):
    return str(self.value)

    class Tree():
    '''
    树类
    '''
    def __init__(self):
    self.root = Node()
    self.myqueue = [] # 用来存放子树的三个节点,依次为root, left, right

    def add(self, elem):
    node = Node(elem)
    if self.root.value == None: # 树为空,进行赋值
    self.root = node
    self.myqueue.append(self.root)
    else: # 此树不为空,但子节点还没补齐
    treeNode = self.myqueue[0]
    if treeNode.lft == None:
    treeNode.lft = node
    self.myqueue.append(treeNode.lft)
    else:
    treeNode.rgt = node
    self.myqueue.append(treeNode.rgt)
    self.myqueue.pop(0) # 该节点如果存在右子树,将此结点丢弃

    # 递归方式前中后序遍历
    def preOrder(self, root):
    '''
    前序遍历
    '''
    if root == None:
    return
    else:
    print(root.value)
    self.preOrder(root.lft)
    self.preOrder(root.rgt)

    def inOrder(self, root):
    '''
    中序遍历
    '''
    if root == None:
    return
    self.inOrder(root.lft)
    print(root.value)
    self.inOrder(root.rgt)

    def postOrder(self, root):
    '''
    后序遍历
    '''
    if root == None:
    return
    self.postOrder(root.lft)
    self.postOrder(root.rgt)
    print(root.value)
  2. 利用栈实现非递归方式深度优先遍历

    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
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    class Node():
    '''
    结点类
    '''
    def __init__(self, value=None, lft=None, rgt = None):
    self.value = value
    self.lft = lft
    self.rgt = rgt

    def __str__(self):
    return str(self.value)

    class Tree():
    '''
    树类
    '''
    def __init__(self):
    self.root = Node()
    self.myqueue = [] # 用来存放子树的三个节点,依次为root, left, right

    def add(self, elem):
    node = Node(elem)
    if self.root.value == None: # 树为空,进行赋值
    self.root = node
    self.myqueue.append(self.root)
    else: # 此树不为空,但子节点还没补齐
    treeNode = self.myqueue[0]
    if treeNode.lft == None:
    treeNode.lft = node
    self.myqueue.append(treeNode.lft)
    else:
    treeNode.rgt = node
    self.myqueue.append(treeNode.rgt)
    self.myqueue.pop(0) # 该节点如果存在右子树,将此结点丢弃

    # 非递归方式前中后序遍历,利用栈实现
    def preOrder_stack(self, root):
    '''
    利用栈实现前序遍历
    '''
    if root == None:
    return

    node = root
    mystack = [] # 保存遍历的节点
    while node or mystack:
    while node: # 从根节点开始,先遍历左子树
    print(node.value) # 先打印再入栈
    mystack.append(node)
    node = node.lft
    node = mystack.pop() # 弹出栈顶元素,开始遍历右子树
    node = node.rgt # 每弹出一个结点,紧接着就访问其右子树

    def inOrder_stack(self, root):
    '''
    利用栈实现中序遍历
    '''
    if root == None:
    return

    node = root
    mystack = []
    while node or mystack:
    while node: # 从根节点开始,一直找到左子树到最后一个节点
    mystack.append(node) # 先入栈后打印
    node = node.lft
    node = mystack.pop() # pop顺序: left, root, right
    print(node.value)
    node = node.rgt

    def postOrder_stack(self, root):
    '''
    利用栈实现后序遍历
    '''
    if root == None:
    return

    node = root
    mystack1 = [] # 存放正在访问的节点
    mystack2 = [] # 存放后序遍历的逆序
    mystack1.append(node)
    while mystack1:
    node = mystack1.pop()
    if node.lft:
    mystack1.append(node.lft)
    if node.rgt:
    mystack1.append(node.rgt)
    mystack2.append(node)

    while mystack2:
    print(mystack2.pop().value)
  3. 广度优先遍历

    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
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    class Node():
    '''
    结点类
    '''
    def __init__(self, value=None, lft=None, rgt = None):
    self.value = value
    self.lft = lft
    self.rgt = rgt

    def __str__(self):
    return str(self.value)

    class Tree():
    '''
    树类
    '''
    def __init__(self):
    self.root = Node()
    self.myqueue = [] # 用来存放子树的三个节点,依次为root, left, right

    def add(self, elem):
    node = Node(elem)
    if self.root.value == None: # 树为空,进行赋值
    self.root = node
    self.myqueue.append(self.root)
    else: # 此树不为空,但子节点还没补齐
    treeNode = self.myqueue[0]
    if treeNode.lft == None:
    treeNode.lft = node
    self.myqueue.append(treeNode.lft)
    else:
    treeNode.rgt = node
    self.myqueue.append(treeNode.rgt)
    self.myqueue.pop(0) # 该节点如果存在右子树,将此结点丢弃

    def levelOrder(self, root):
    '''
    层次遍历
    '''
    if root == None:
    return
    myqueue = []
    node = root
    myqueue.append(node)
    while myqueue:
    node = myqueue.pop(0)
    print(node.value)
    if node.lft != None:
    myqueue.append(node.lft)
    if node.rgt != None:
    myqueue.append(node.rgt)

总结:

  1. 二叉树的遍历可以分为两种,即广度优先遍历和深度优先遍历。
  2. 广度优先遍历如层次遍历,按照一度优先、二度优先…的顺序进行逐层遍历。
  3. 深度优先遍历如前序、中序、后序遍历。
  4. 广度优先一般使用队列来实现,而深度优先则使用递归或栈来实现,因为大部分情况下栈可以实现递归。