Python实现树的遍历以及恢复_python 遍历树

前言

​  此文主要内容是我很久以前在Typora上做的笔记，现在免费版的Typora没了，所以就把笔记内容转移到这边，同时也是方便自己日后回顾学习和进一步改进。

树的遍历方式

​  树的遍历方式有四种，先序遍历，中序遍历，后序遍历以及层次遍历。其中只需要中序遍历和其他任意一种遍历方式，就能确定一颗树。除了中序遍历的方式，其他方式只能确定根结点的位置，还需要中序遍历区分左右子树。除了层次遍历，其他方式只需要借助递归方法就能实现。

​ ​  下面以这张图为例：

先序遍历

​ ​  先序遍历指的就是优先输出根节点，然后再输出左节点，最后输出右节点。主要代码如下：

def Search(root): # python
    if root == None:
        return 
    print(root.val,end = " ")
    Search(root.left)
    Search(root.right)  # 输出结果为 10 7 3 8 9 11 12
1
2
3
4
5
6

中序遍历

​ ​  中序遍历需要先输出左节点，然后输出根结点，最后输出右节点。所以根据它的输出序列可以划分左右子树节点。

def Search(root):
    if root == None:
        return 
    Search(root.left)
    print(root.val,end = " ")
    Search(root.right)  # 3 7 8 9 10 11 12
1
2
3
4
5
6

后序遍历

​ ​   后序遍历需要先输出左节点，然后输出右节点，最后输出根节点。

def Search(root):
    if root == None:
        return 
    Search(root.left)
    Search(root.right)
    print(root.val,end=" ")  # 输出结果为 3 9 8 7 12 11 10
1
2
3
4
5
6

层次遍历

​ ​   层次遍历就是将一棵树从左到右按层输出，需要使用队列。

q = deque()
q.append(r)
while q:
    now = q.popleft() # 出队首元素
    if now == None:
        continue
    print(now.val,end=" ")
    if now.left != None:
        q.append(now.left)
    if now.right != None:
        q.append(now.right)
# 输出10 7 11 3 8 12 9 
1
2
3
4
5
6
7
8
9
10
11
12

通过图的不同遍历方式恢复树

​ ​   前面已经提到，可以通过中序遍历+其他遍历方式的形式恢复一棵树，这里依旧以前面的树作为例子。

前序+中序

​ ​   前序，先访问根节点，然后再是左节点，再后是右节点。逻辑过程如下图所示：

代码如下：

pre = [10, 7, 3, 8, 9, 11, 12]
mid = [3,7,8,9,10,11,12]
hash_map = {v:k for k,v in enumerate(mid)}  # 获取得到在中序遍历的下标
def reTree(left,right):
    if left > right:
        return None
    val = pre.pop(0)   # 前序遍历是从根节点开始的，所以先取出首个元素
    index = hash_map[val]
    root = Node(val)
    root.left = reTree(left,index-1)  # 紧跟着根节点后面的是左子树的内容，根据前序遍历，先创建左子树
    root.right = reTree(index+1,right)
    return root
r = reTree(0,len(mid)-1)
1
2
3
4
5
6
7
8
9
10
11
12
13

后序+中序

​ ​  逻辑推理类似于上图,代码如下：

last = [3,9,8,7,12,11,10]
mid = [3,7,8,9,10,11,12]
hash_map = {v:k for k,v in enumerate(mid)}
def reTree(left,right):
    if left > right:
        return None
    val = pre.pop()  # 先得到后序遍历的根节点，然后不断往前推
    index = hash_map[val]
    root = Node(val)
    root.right = reTree(index+1,right)  # 根节点之前是右子树的内容，所以先创建右子树
    root.left = reTree(left,index-1)
    return root
r = reTree(0,len(mid)-1)
1
2
3
4
5
6
7
8
9
10
11
12
13

二叉搜索树的创建

​ ​   二叉搜索树需要满足一个规则，左节点的数要比父节点小，右节点的树要比父节点的数大。中序遍历二叉搜索树输出一个降序的有序数列。

def CreateTree(root,i):
    if root.val > i:
        if root.left is None:   # 如果已经是叶子节点了，就直接成为一个叶子结点，否则的话，往下遍历
            root.left = Node(i)
        else:
            CreateTree(root.left,i)
    else:
        if root.right is None:
            root.right = Node(i)
        else:
            CreateTree(root.right,i)
1
2
3
4
5
6
7
8
9
10
11

总结

​  本文遍历方式使用的都是递归遍历，事实上使用栈的话也可以实现对树的遍历方式，但是代码需要更改的地方也比较多，由于本人时间有限，也没有继续去改进。
​  个人觉得比较有意思的地方就是通过中序和其他三种遍历方式就可以恢复一颗树，当时还花了点时间去理解它，现在搞懂了就简单很多了。以上，希望能对你有帮助。