二叉树的前序遍历、中序遍历、后序遍历

╰半夏微凉° 2023-03-13 05:54 84阅读 0赞

## Python代码实现二叉树 ##

以下的实现思想是借鉴的尚硅谷-韩顺平数据结构与算法的java实现，[韩顺平老师视频地址-https://www.bilibili.com/video/BV1E4411H73v?p=15][-https_www.bilibili.com_video_BV1E4411H73v_p_15]  
大概的思路是用两个类来实现，一个类是实现结点的，另一个类是操作节点的类。把对二叉树的三种遍历方式放到了结点类种。  
以下是实现代码：

class Node:
        def __init__(self,id,name):
        #假设节点中存储的是id, name, 左子节点, 右子节点四个信息
            self.id = id
            self.name = name
            self.left = None
            self.right = None
    
        def __str__(self):
            return "Node: id-{}, name-{}, height-{}".format(self.id, self.name,self.getheight())
    
        # 前序遍历，先输出，再往左遍历，再往右遍历
        def preOrder(self):
            print(self)
            if self.left:
                self.left.preOrder()
            if self.right:
                self.right.preOrder()
    
        # 中序遍历先左遍历，再输出，再往右遍历
        def infixOrder(self):
            if self.left:
                self.left.infixOrder()
            print(self)
            if self.right:
                self.right.infixOrder()
        #后序遍历，先往左遍历，再往右遍历，后输出
        def postOrder(self):
            if self.left:
                self.left.postOrder()
            if self.right:
                self.right.postOrder()
            print(self)
    
    
    class BinaryTree:
        def __init__(self):
        #二叉树的初始化，创建一个头节点。
            self.root = Node(None, Node)
    
        # 在添加数据的时候实现了二叉排序树
        def add(self,id,name):
            temp = self.root
            while True:
                if temp.id == None:
                    self.root.id = id
                    self.root.name = name
                    return
                else:
                    faid = temp.id
                    if id >= faid:
                        if temp.right:
                            temp = temp.right
                        else:
                            temp.right = Node(id, name)
                            return
                    else:
                        if temp.left:
                            temp = temp.left
                        else:
                            temp.left = Node(id, name)
                            return
    
        def pre(self):
            self.root.preOrder()
    
        def infix(self):
            self.root.infixOrder()
    
        def after(self):
            self.root.postOrder()

## 三种遍历结果 ##

三种遍历方式的不同之处在于print语句的位置，前序遍历是在左遍历和右遍历之前，中序遍历是在中间，后续遍历是在最后。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MzI3MjY2_size_16_color_FFFFFF_t_70]  
前序遍历的结果是：A-B-C-D-E-F-G-H-I  
结合代码来看，先从A开始，然后输出A，遍历左子树，输出B，再遍历左子树，输出C，在遍历左子树，发现左子树为空，然后遍历C的右子树，输出D，然后遍历左子树，发现左子树为空，遍历右子树，发现右子树为空，这时就会回到C，C已经遍历完了，就会回到B，开始遍历B的右子树，输出E，E的左右子树都为空，又会回到B，B遍历完了，回到A，开始遍历A的右子树，相同的步骤，得到最后的结果。

中序遍历的结果是：C-D-B-E-A-F-H-G-I  
还是结合代码来看，print语句再中间，此时从A开始，会一遗址进行左子树的遍历，直到左子树为空时，就会输出第一个左子树为空的结点，也就是C，然后遍历右子树，右子树是D，D的左子树为空，输出D，D的右子树也为空，此时就会回到B，B的左子树已经遍历完了，这时就会输出B,然后继续遍历右子树，E的左子树为空，输出E，E的右子树为空，回到A，遍历A的右子树，同样的方式进行下去，得到最终结果。

后序遍历的结果是：D-C-E-B-H-I-G-F-A  
理解了中序遍历后，结合代码不难理解后序遍历，只不过是调了以下print语句的位置。

[-https_www.bilibili.com_video_BV1E4411H73v_p_15]: https://www.bilibili.com/video/BV1E4411H73v?p=15
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MzI3MjY2_size_16_color_FFFFFF_t_70]: /images/20230312/a67703b5fe2c4ee39e912b1933ef63db.png