python数据结构树和二叉树简介

下面是关于“Python数据结构树和二叉树简介”的详细攻略。

一、树的概念

树（Tree）是一种非常重要的数据结构，它是由n(n>0)个有限节点组成一个具有层次关系的集合。其中一个节点被称作根节点，它没有父节点；除根节点外，其他节点都有且只有一个父节点；每个节点可以有0个或多个子节点。一棵树的深度为树中层次最大的节点层数，根节点层次为1。

二、二叉树的概念

二叉树（Binary Tree）是一种特殊的树结构，它的每个节点最多有两个子节点，分别为左子节点和右子节点。二叉树非常常见，常用于实现算法中的查找和排序等功能。

三、二叉树的遍历方式

二叉树的遍历方式主要有三种：前序遍历、中序遍历和后序遍历。

1. 前序遍历：先访问根节点，再递归地访问左子树和右子树。代码如下：

def preorder(self, root):
    if root:
        print(root.val)
        self.preorder(root.left)
        self.preorder(root.right)

1. 中序遍历：先递归地访问左子树，然后访问根节点，最后递归地访问右子树。代码如下：

def inorder(self, root):
    if root:
        self.inorder(root.left)
        print(root.val)
        self.inorder(root.right)

1. 后序遍历：先递归地访问左子树和右子树，最后访问根节点。代码如下：

def postorder(self, root):
    if root:
        self.postorder(root.left)
        self.postorder(root.right)
        print(root.val)

四、二叉树的示例说明

下面给出两个二叉树的示例。

示例一

    1
   / \
  2   3
 / \
4   5

此二叉树的前序遍历结果为：1 2 4 5 3；中序遍历结果为：4 2 5 1 3；后序遍历结果为：4 5 2 3 1。

实现代码如下：

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

class Solution:
    # 前序遍历
    def preorder(self, root):
        if root:
            print(root.val)
            self.preorder(root.left)
            self.preorder(root.right)

    # 中序遍历
    def inorder(self, root):
        if root:
            self.inorder(root.left)
            print(root.val)
            self.inorder(root.right)

    # 后序遍历
    def postorder(self, root):
        if root:
            self.postorder(root.left)
            self.postorder(root.right)
            print(root.val)

if __name__ == '__main__':
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)

    solution = Solution()
    print("preorder:")
    solution.preorder(root)
    print("inorder:")
    solution.inorder(root)
    print("postorder:")
    solution.postorder(root)

示例二

        5
      /   \
     2     8
   /  \   / \
  1   4  7   9

此二叉树的前序遍历结果为：5 2 1 4 8 7 9；中序遍历结果为：1 2 4 5 7 8 9；后序遍历结果为：1 4 2 7 9 8 5。

实现代码如下：

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

class Solution:
    # 前序遍历
    def preorder(self, root):
        if root:
            print(root.val)
            self.preorder(root.left)
            self.preorder(root.right)

    # 中序遍历
    def inorder(self, root):
        if root:
            self.inorder(root.left)
            print(root.val)
            self.inorder(root.right)

    # 后序遍历
    def postorder(self, root):
        if root:
            self.postorder(root.left)
            self.postorder(root.right)
            print(root.val)

if __name__ == '__main__':
    root = TreeNode(5)
    root.left = TreeNode(2)
    root.right = TreeNode(8)
    root.left.left = TreeNode(1)
    root.left.right = TreeNode(4)
    root.right.left = TreeNode(7)
    root.right.right = TreeNode(9)

    solution = Solution()
    print("preorder:")
    solution.preorder(root)
    print("inorder:")
    solution.inorder(root)
    print("postorder:")
    solution.postorder(root)