[二叉树] 二叉树的构造和遍历(基础)

构造二叉树并加入节点

class BiNode():
    def __init__(self,value=None,left=None,right=None):
        self.value=value
        self.left=left
        self.right=right
class BiTree():
    def __init__(self,initial=None):
        #初始化对象BiTee()的时候必然为空
        self.TreeSet=initial
        
    def AddTree(self,TreeValue):
        #声明一个新的节点
        node=BiNode(TreeValue)
        
        if self.TreeSet is None:   #判断这棵树是否为空，是则把新节点加入树根
            self.TreeSet=node
        else:
            
            #通过que队列，把需要遍历的节点和子节点通通入队。每次迭代取出队首元素
            que=[]
            que.append(self.TreeSet) #把根节点装入que
            while que is not None:
                ActNode=que.pop(0) #声明当前节点为队首元素
                
                if ActNode.left is None:
                    #左子树空则把新节点node加入TreeSet
                    ActNode.left=node
                    break
                elif ActNode.right is None:
                    ActNode.right=node
                    break
                else:
                    que.append(ActNode.left)
                    que.append(ActNode.right)
        print("OK")

二叉树的广度遍历

class BiNode():
    def __init__(self,value=None,left=None,right=None):
        pass
class BiTree():
    def __init__(self,initial=None):
        pass
    #广度遍历
    def TraversalTree(self):
        ret=self.TreeSet
        que=[]
        que.append(ret)#入队根节点

        while len(que):
            actNode=que.pop(0)
            print(actNode.value)
            if actNode.left is not None:
                que.append(actNode.left)
            if actNode.right is not None:
                que.append(actNode.right)

二叉树的前序遍历

思路1（栈）：

假设节点P（非叶子节点）是二叉树中的某一个节点。对于这个节点

1.访问根节点

2.前序遍历左子树

3.前序遍历右子树

在while循环之前把head节点入栈了，那么while循环里面关注的就是子节点

class BiNode():
    def __init__(self,value=None,left=None,right=None):
        pass
class BiTree():
    def __init__(self,initial=None):
        self.TreeSet=initial
        
    def AddTree(self,TreeValue):
        pass
    def Pre_Order(self):
        head = self.TreeSet
        if not head:
            return None
        stack = [head]
        while len(stack):
            node = stack.pop()
            print(node.value)
            #先入栈右子树节点
            if node.right:
                stack.append(node.right)
            #在入栈左子树节点
            if node.left:
                stack.append(node.left)
tree=BiTree()
for x in range(11):
    tree.AddTree(x)
print("ok")
tree.Pre_Order()

问题1：按照思路是前序遍历左子树 -> 前序遍历右子树，而代码为什么是入栈右子树 -> 入栈左子树呢？

想想栈的特点，入栈以右子树->左子树的顺序，才能实现出栈时左子树->右子树

思路2（栈）：

1.沿着左子树一直到叶子节点，顺路把该节点的右子树节点入栈

2.左子树到达叶子节点后开始出栈

3.继续1和2

class BiNode():
    def __init__(self,value=None,left=None,right=None):
        pass
class BiTree():
    def __init__(self,initial=None):
        self.TreeSet=initial
        
    def AddTree(self,TreeValue):
        pass
    def pre_Order(self):
        head = self.TreeSet
        stack = []
        node = head
        while len(stack) or node:
            if node:
                print(node.value)
                stack.append(node.right)
                node = node.left
            else:
                #回溯条件：到达叶子节点
                node = stack.pop()
tree=BiTree()
for x in range(11):
    tree.AddTree(x)
print("ok")
tree.pre_Order()

二叉树的中序遍历

思路1（栈）：

1.先遍历左节点直到叶子，因为 node = node.left，所以此时 node is None

2.接着执行 else 分支，开始出栈（也就是回溯），把node指向右节点

3.循环1，2

注意当我们遍历左节点到叶子节点之后，执行else分支，node = node.right是None，不用担心，这时候会继续出栈（回溯），不影响。

def in_Order(self):
    head = self.TreeSet
    stack = []
    node = head
    while len(stack) or node:
        if node:
            stack.append(node)
            node = node.left
        else:
            node = stack.pop()
            print(node.value)
            node = node.right

思路2（递归）：

1.递归到叶子节点

2.回溯过程中打印节点

3.回溯过程中如果有右节点则递归右节点（重复1，2）

def in_order_recursion(self,head):
    if head.left:
        self.in_order_recursion(head.left)
    print(head.value)
    if head.right:
        self.in_order_recursion(head.right)

二叉树的后序遍历

参考：https://blog.csdn.net/u012435142/article/details/89062177