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

#思路

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

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

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

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

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

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

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

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

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

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

class TreeNode:def __init__(self, val=None, left=None, right=None):self.val = valself.right = rightself.left = leftclass Tree:def __init__(self, maxNodes):self.root = Noneself.nodes = [TreeNode() for i in range(maxNodes)]self.nodesSize = maxNodesdef 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 NonenowNode = 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 nowNodedef 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()