浅析二叉树遍历

一直以来都是写业务代码，和应用的功能设计，感觉自己好像入门了开发。刷了下今日头条的面试题，顿时不安了，什么二叉树 、单向链表、线程安全。一脸懵逼，给自己补补课，结合python学习了下。

二叉树是什么

在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”，左子树和右子树同时也是二叉树。二叉树的子树有左右之分，并且次序不能任意颠倒。

生成一个二叉树

class Node(object):
    def __init__(self,number):
        self.number = number
        self.rchild = None
        self.lchild = None

class Tree(object):

    lis = []
    def __init__(self):
        self.root = None

    def add(self,number):
        node = Node(number)
        if self.root==None:
            self.root = node
            Tree.lis.append(self.root)
        else:
            while True:
                point = Tree.lis[0]
                if point.lchild == None:
                    point.lchild = node
                    Tree.lis.append(point.lchild)
                    return
                elif point.rchild == None:
                    point.rchild = node
                    Tree.lis.append(point.rchild)
                    Tree.lis.pop(0)
                    return

if '__main__' == __name__:
    t = Tree()
    L = [1,2,3,4,5,6,7]
    for x in L:
        t.add(x)
    root = t.root				

上述最终的root就是我们生成的二叉树对象了。
简述过程：
1.开始初始化了Tree，其中root是None的，我们把创建的节点丢进了一个list
2.遍历了L，把第一个作为了根节点，此时它的左右子节点都是None，
3.接着遍历L，list里增加了他的子节点数据
4.当右节点数据也有了后，丢掉父节点，继续从左节点的第一个给他加儿子
5.一层一层来，都有儿子后，丢掉父节点。
完成

排序介绍

前序遍历：父节点，左节点，右节点
↙↘

中序遍历：左节点，父节点，右节点
↗↘

后序遍历：左节点，右节点，父节点
➡↖

遍历排序

结合上述的排序介绍，可以通过以下方式遍历。

def pre(root):
    if root == None:
        return
    print(root.number)
    pre(root.lchild)
    pre(root.rchild)

def mid(root):
    if root == None:
        return
    mid(root.lchild)
    print(root.number)
    mid(root.rchild)

def back(root):
    if root == None:
        return
    back(root.lchild)
    back(root.rchild)
    print(root.number)

不用太多解释了吧，只是打印顺序的问题。

递归排序

除了上述的遍历方式，还有递归方式获取，这里先写个前序排序的递归

def pre_queue(root):
    stack = [root]
    while len(stack):
        p = stack.pop()
        print(p.number)
        if p.rchild:
            stack.append(p.rchild)
        if p.lchild:
            stack.append(p.lchild)

分析：
1.创建了数组放节点
2.根节点被取出打印
3.他的子节点从右到左被丢进数组
4.取出数组最后一个也就是左节点再去递归它的子节点

完整代码

#-*-coding:utf-8-*-

class Node(object):
    def __init__(self,number):
        self.number = number
        self.rchild = None
        self.lchild = None

class Tree(object):

    lis = []
    def __init__(self):
        self.root = None

    def add(self,number):
        node = Node(number)
        if self.root==None:
            self.root = node
            Tree.lis.append(self.root)
        else:
            while True:
                point = Tree.lis[0]
                if point.lchild == None:
                    point.lchild = node
                    Tree.lis.append(point.lchild)
                    return
                elif point.rchild == None:
                    point.rchild = node
                    Tree.lis.append(point.rchild)
                    Tree.lis.pop(0)
                    return

def pre(root):
    if root == None:
        return
    print(root.number)
    pre(root.lchild)
    pre(root.rchild)

def mid(root):
    if root == None:
        return
    mid(root.lchild)
    print(root.number)
    mid(root.rchild)

def back(root):
    if root == None:
        return
    back(root.lchild)
    back(root.rchild)
    print(root.number)

def pre_queue(root):
    stack = [root]
    while len(stack):
        p = stack.pop()
        print(p.number)
        if p.rchild:
            stack.append(p.rchild)
        if p.lchild:
            stack.append(p.lchild)

if '__main__' == __name__:
    t = Tree()
    L = [1,2,3,4,5,6,7]
    for x in L:
        t.add(x)
        print('sucess')

    #pre(t.root) #前序排列
    #mid(t.root) #中序排列
    #back(t.root) #后序排列
    pre_queue(t.root)