个数为0，则我们称该树为空树；否则称为非空树。

        一棵树是 n (n≥0) 个结点的有限集 T（可为空），T 非空时满足：

​

​

         如下图所示：是先从左到右访问子树，最后再访问根节点。

        这棵树的后序遍历结果为：KLEFBGCMHIJDA

 4.3 层次遍历：

        这个很简单了，就是从上到下，从左到右

        所以这棵树层次遍历的结果是：ABCDEFGHIJKLM

（二）二叉树

1. 二叉树的定义：

2. 满二叉树与完全二叉树：

3. 二叉树的存储

 3.1 顺序存储：

        顺序存储即按照层次遍历的顺序存储，但会造成空间的浪费，因此只适用于完全二叉树或者满二叉树的存储。

        具体步骤如下：

• 针对完全二叉树（包括了满二叉树）：用一组地址连续的存储单元从根结点开始依次自上而下，并按层次从左到右存储完全二叉树上的各结点元素，即将完全二叉树编号为i的结点元素存储在下标为i数组元素中。
• 针对非完全二叉树： 先在树中增加一些并不存在的虚结点并使其成为一 棵完全二叉树，然后用与完全二叉树相同的方法对结 进行编号，再将编号为i的结点的值存放到数组下 标为i的数组单元中，虚结点不存放任何值。

   

3.2 链式存储：

 4.1.3 后序遍历：

和树的后序遍历一样，先左子树，再右子树，最后再访问根节点。如下图所示：该树后序遍历的结果是：DCBHKGFEA

4.1.4 层次遍历：

        这个就很简单了，如下图所示：该树层次遍历的结果是：ABECFDGHK

 def PreOrderNonRecursive(self,Root):
    StackTreeNode=[]    # 用来存放当前被访问节点的右孩子节点的栈
    tTreeNode=Root    # 给定一棵二叉树的根节点

# ===========================================================================
    while len(StackTreeNode) > 0 or tTreeNode is not None:
        
# 这个循环用来访问节点的值，根节点的访问完了以后默认是从左孩子节点开始的
        while tTreeNode is not None:
             self.VisitBinaryTreeNode(tTreeNode)
             StackTreeNode.append(tTreeNode)
             tTreeNode=tTreeNode.LeftChild    # 可以看到访问的都是左孩子节点

# 在上面的循环结束以后，栈里已经存了很多右孩子节点，下面的判断语句就是把根节点换成
# 后孩子节点，然后再回到上面的循环去打印右孩子节点的信息
# ============================================================================
 
# ============================================================================       
# 一旦左孩子节点是叶子结点，就来到下面这个判断语句，把根节点换成栈里的后孩子节点  
        if len(StackTreeNode)>0:
            tTreeNode=StackTreeNode.pop()
            tTreeNode=tTreeNode.RightChild

 def VisitBinaryTreeNode(self,BinaryTreeNode):
    """用于打印节点信息"""
     if BinaryTreeNode.data is not '#':
         print(BinaryTreeNode.data)

 def InOrderNonRecursive(self,Root):
     StackTreeNode=[]    # 存放根节点的栈
     tTreeNode=Root        # 任意一棵二叉树的根节点

# ========================================================================
     while len(StackTreeNode)>0 or tTreeNode is not None:
         while tTreeNode is not None:
             StackTreeNode.append(tTreeNode)    # 把根节点压入栈里面
             tTreeNode=tTreeNode.LeftChild        # 左孩子节点成为新的根节点

# 上面的循环只有当遇到叶子结点并把它压入栈中才会停止，所以下面就是针对遇见叶子结
# 点也被压入栈中情况的判断语句
# =========================================================================

         if len(StackTreeNode)>0:
            # 第一次是取出叶子结点，然后就是路径上的所有根节点
             tTreeNode=StackTreeNode.pop()
             self.VisitBinaryTreeNode(tTreeNode)
             tTreeNode=tTreeNode.RightChild

 def VisitBinaryTreeNode(self,BinaryTreeNode):
    """访问节点信息的函数"""
     if BinaryTreeNode.data is not '#':
         print (BinaryTreeNode.data)

 def LevelOrder(self,Root):
    
     tSequenceQueue=CircularSequenceQueue()    # 创建队列
     tSequenceQueue.InitQueue(100)
     tSequenceQueue.EnQueue(Root)    # 将根节点入队
     tTreeNode=None    # 指向每个被操作的节点的指针

# 将在这个循环完成层次遍历，条件就是队列不为空，为空的话说明遍历完了
     while tSequenceQueue.IsEmptyQueue()==False:
         tTreeNode=tSequenceQueue.DeQueue()    # 节点出队
         self.VisitBinaryTreeNode(tTreeNode)    # 打印出队节点信息
        
         # 两个判断语句分被将出队节点的左右孩子节点按从左到右的顺序放入栈中 
         if tTreeNode.LeftChild is not None:
             tSequenceQueue.EnQueue(tTreeNode.LeftChild)
         if tTreeNode.RightChild is not None:
             tSequenceQueue.EnQueue(tTreeNode.RightChild)
 
 def VisitBinaryTreeNode(self,BinaryTreeNode):
     """访问节点信息"""
     if BinaryTreeNode.data is not '#':
         print (BinaryTreeNode.data)

​

​

​