【数据结构与算法python】树的遍历

1、定义

对一个数据集中的所有数据项进行访问的操作称为“遍历Traversal”，线性数据结构中， 对其所有数据项的访问比较简单直接，按照顺序依次进行即可。树的非线性特点， 使得遍历操作较为复杂，需要采用一种比较特殊的方式来完成。

2、分类

按照对节点访问次序的不同来区分3种遍历

• 前序遍历（preorder）：先访问根节点，再递归地前序访问左子树、最后前序访问右子树；
• 中序遍历（inorder）：先递归地中序访问左子树，再访问根节点，最后中序访问右子树；
• 后序遍历（postorder）：先递归地后序访问左子树，再后序访问右子树，最后访问根节点。

3、代码实现

class BinaryTree:
    """
    A recursive implementation of Binary Tree
    Using links and Nodes approach.
    """

    # 创建仅有根节点的二叉树
    def __init__(self,rootObj):
        self.key = rootObj
        self.leftChild = None
        self.rightChild = None

    # 将新节点插入树中作为其直接的左子节点
    def insertLeft(self,newNode):
        if self.leftChild == None:
            self.leftChild = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.left = self.leftChild
            self.leftChild = t

    # 将新节点插入树中作为其直接的右子节点
    def insertRight(self,newNode):
        if self.rightChild == None:
            self.rightChild = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.right = self.rightChild
            self.rightChild = t

    # 判断是否为叶节点
    def isLeaf(self):
        return ((not self.leftChild) and (not self.rightChild))

    # 返回右子树
    def getRightChild(self):
        return self.rightChild

    # 返回左子树
    def getLeftChild(self):
        return self.leftChild

    # 设置根节点的值
    def setRootVal(self,obj):
        self.key = obj

    # 取得并返回根节点的值
    def getRootVal(self,):
        return self.key

    # 属性解法-前序遍历
    def preorder(self):
        print(self.key)
        if self.leftChild:
            self.leftChild.preorder()
        if self.rightChild:
            self.rightChild.preorder()

    # 属性解法-中序遍历
    def inorder(self):
        if self.leftChild:
            self.leftChild.inorder()
        print(self.key)
        if self.rightChild:
            self.rightChild.inorder()

    # 属性解法-树的高度
    def height(self):
        if self == None:
            return -1
        else:
            return 1 + max(height(self.leftChild), height(self.rightChild))

    # 属性解法-后序遍历
    def postorder(self):
        if self.leftChild:
            self.leftChild.postorder()
        if self.rightChild:
            self.rightChild.postorder()
        print(self.key)
        
# 函数解法-前序遍历
def preorder(tree):
    if tree != None:
        print(tree.getRootVal())
        preorder(tree.getLeftChild())
        preorder(tree.getRightChild())

# 函数解法-中序遍历
def inorder(tree):
    if tree != None:
        inorder(tree.getLeftChild())
        print(tree.getRootVal())
        inorder(tree.getRightChild())

# 函数解法-后序遍历
def postorder(tree):
    if tree != None:
        postorder(tree.getLeftChild())
        postorder(tree.getRightChild())
        print(tree.getRootVal())

4、测试代码和结果

t = BinaryTree(7)
t.insertLeft(3)
t.insertRight(9)
print("前序遍历-函数解法")
t.preorder()
print("前序遍历-属性解法")
t.preorder()
print("中序遍历-函数解法")
inorder(t)
print("中序遍历-属性解法")
t.inorder()
print("后序遍历-函数解法")
postorder(t)
print("后序遍历-属性解法")
t.postorder()
print("树的高度-函数解法")
print(height(t))
print("树的高度-函数解法")
print(t.height())