数据结构——【二叉树模版】

#思路

 1、二叉树不同于数的构建，在树节点类中，有数据，左子结点，右子节点三个属性，在树类的构造函数中，添加了变量maxNodes，用于后续列表索引的判断

2.GetTreeNode()函数是常用方法，用于获取不同节点的索引

3、Create(）是重点，与树的区别在于，树的索引和节点值是自己设置的，而二叉树构建

树的过程，传入的主要参数是数组a,所以对应索引的节点值，需要根据二叉树索引特点自己构建

4、三种遍历过程，就是按照不同方式访问树的节点，以前序遍历为例，构建函数的过程就是访问当前节点的值（此功能由visit()完成），然后递归的访问左子结点和右子节点，如果深入递归的遍历过程，思维会混乱，不如明确递归函数书写的根本：

①这个函数功能是什么，完成这个功能

②递归的基本要求是，随着遍历的每一次深入，需要回来，因此需要一个判断，便于函数返回

③具备深搜的基本条件：每一个节点都有三个属性

索引作为节点的唯一标识符，在创建时会储存在一个顺序表中。

回到创建树的过程（create()过程），由传入参数可知，根节点的值和索引是确定的，当确定第一个节点值时，会继续对此节点添加左右子节点，而新连接成的节点（索引不同），他们也具有三个属性。所以实际上，这些节点依据索引的不同被访问和划分，每一个节点都有向下的枢纽，完成遍历过程。

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


class Tree:
    def __init__(self, maxNodes):
        self.root = None
        self.nodes = [TreeNode() for i in range(maxNodes)]
        self.nodesSize = maxNodes

    def GetTreeNode(self, id):
        return self.nodes[id]

    def visit(self, node):
        print(node.val, end="")

    def Create(self, a, size, nodeId):
        if nodeId >= size or a[nodeId] == None:
            return None
        nowNode = self.GetTreeNode(nodeId)
        nowNode.val = a[nodeId]
        nowNode.left = self.Create(a, size, nodeId * 2)
        nowNode.right = self.Create(a, size, nodeId * 2 + 1)
        return nowNode

    def CreateTree(self, a):
        self.root = self.Create(a, len(a), 1)

    def preOrder(self, node):
        if node:
            self.visit(node)
            self.preOrder(node.left)
            self.preOrder(node.right)

    def preOrederTraversal(self):
        self.preOrder(self.root)
        print("")

    def inOrder(self, node):
        if node:
            self.inOrder(node.left)
            self.visit(node)
            self.inOrder(node.right)

    def inOrederTraversal(self):
        self.inOrder(self.root)
        print("")

    def postOrder(self, node):
        if node:
            self.visit(node)
            self.postOrder(node.left)
            self.postOrder(node.right)

    def postOrederTraversal(self):
        self.postOrder(self.root)
        print("")


def Test():
    a = [None, "a", "b", "c", "d", None, "e", "f", "g", "h", None, None, None, None, "i"]
    T = Tree(15)
    T.CreateTree(a)
    T.postOrederTraversal()
    T.inOrederTraversal()
    T.postOrederTraversal()


Test()