二叉树基础详解和Python代码定义，各种二叉树遍历方式详解和Python实现

二叉树基础详解

二叉树的种类

满二叉树

满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。

完全二叉树

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点。

二叉搜索树

前面介绍的树，都没有数值的，而二叉搜索树是有数值的了，二叉搜索树是一个有序树。

●若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
●若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
●它的左、右子树也分别为二叉排序树

平衡搜索二叉树

平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

二叉树的储存方式

二叉树可以链式存储，也可以顺序存储。
但我们一般都用链式储存

那么链式存储方式就用指针， 顺序存储的方式就是用数组。

顾名思义就是顺序存储的元素在内存是连续分布的，而链式存储则是通过指针把分布在各个地址的节点串联一起。

二叉树的遍历方式

二叉树主要有两种遍历方式：

深度优先遍历：先往深走，遇到叶子节点再往回走。
广度优先遍历：一层一层的去遍历。
这两种遍历是图论中最基本的两种遍历方式，后面在介绍图论的时候 还会介绍到。

那么从深度优先遍历和广度优先遍历进一步拓展，才有如下遍历方式：

深度优先遍历
●前序遍历（递归法，迭代法）
●中序遍历（递归法，迭代法）
●后序遍历（递归法，迭代法）
广度优先遍历
层次遍历（迭代法）
在深度优先遍历中：有三个顺序，前中后序遍历， 有同学总分不清这三个顺序，经常搞混，我这里教大家一个技巧。

这里前中后，其实指的就是中间节点的遍历顺序，只要大家记住 前中后序指的就是中间节点的位置就可以了。

看如下中间节点的顺序，就可以发现，中间节点的顺序就是所谓的遍历方式

●前序遍历：中左右
●中序遍历：左中右
●后序遍历：左右中
大家可以对着如下图，看看自己理解的前后中序有没有问题。

最后再说一说二叉树中深度优先和广度优先遍历实现方式，我们做二叉树相关题目，经常会使用递归的方式来实现深度优先遍历，也就是实现前中后序遍历，使用递归是比较方便的。

二叉树的定义（Python）

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

二叉树的深度优先遍历（递归）：

前序遍历（中左右）

力扣144. 二叉树的前序遍历

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode])-> List[int]:
        result = []                       #保存结果
        def transfer(root):
            if root==None:
                return
            result.append(root.val)        #前序
            transfer(root.left)            #左
            transfer(root.right)           #右
        transfer(root)
        return result

中序遍历（左中右）

力扣94. 二叉树的中序遍历

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []                      #存放结果
        def tranfer(root):
            if root==None:
                return
            tranfer(root.left)           #左
            result.append(root.val)      #中序
            tranfer(root.right)          #右  
        tranfer(root)
        return result

后序遍历（左右中）

力扣145. 二叉树的后序遍历

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []                   #存放结果
        def tranfer(root):
            if root==None:
                return
            tranfer(root.left)         #左
            tranfer(root.right)        #右 
            result.append(root.val)    #后序
        tranfer(root)
        return result

二叉树的深度优先遍历（迭代，非递归）：

前序遍历（中左右）

力扣144. 二叉树的前序遍历

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        # 根结点为空则返回空列表
        if not root:
            return []
        stack = [root]
        result = []
        while stack:
            node = stack.pop()
            # 中结点先处理
            result.append(node.val)
            # 右孩子先入栈
            if node.right:
                stack.append(node.right)
            # 左孩子后入栈
            if node.left:
                stack.append(node.left)
        return result

中序遍历（左中右）

力扣94. 二叉树的中序遍历

使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        stack = []  # 不能提前将root结点加入stack中
        result = []
        cur = root
        while cur or stack:
            # 先迭代访问最底层的左子树结点
            if cur:     
                stack.append(cur)
                cur = cur.left		
            # 到达最左结点后处理栈顶结点    
            else:		
                cur = stack.pop()
                result.append(cur.val)
                # 取栈顶元素右结点
                cur = cur.right	
        return result

后序遍历（左右中）

再来看后序遍历，先序遍历是中左右，后续遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中了，如下图：

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        stack = [root]
        result = []
        while stack:
            node = stack.pop()
            result.append(node.val)
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
        result.reverse()
        return result

二叉树的统一迭代法

我们就将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记。

如何标记呢，就是要处理的节点放入栈之后，紧接着放入一个空指针作为标记。 这种方法也可以叫做标记法

前序统一迭代

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode])-> List[int]:
        if not root:
            return []
        result = []
        stack = [root]
        while stack:
            node = stack.pop()
            if node:
                if node.right:
                    stack.append(node.right)
                if node.left:
                    stack.append(node.left)
                stack.append(node)
                stack.append(None)
            else:
                node = stack.pop()
                result.append(node.val)
        return result

中序统一迭代

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        result = []
        stack = [root]
        while stack:
            node = stack.pop()
            if node:
                if node.right:
                    stack.append(node.right)
                stack.append(node)
                stack.append(None)
                if node.left:
                    stack.append(node.left)
            else:
                node = stack.pop()
                result.append(node.val)
        return result

后序统一迭代

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        stack = [root]
        result = []
        while stack:
            node = stack.pop()
            if node:
                stack.append(node)
                stack.append(None)
                if node.right:
                    stack.append(node.right)
                if node.left:
                    stack.append(node.left)
            else:
                node = stack.pop()
                result.append(node.val)
        return result