class Node:def __init__(self,data,l_child = None,r_child=None):self.data = dataself.l_child = l_childself.r_child = r_childclass Tree:def __init__(self,root = None):self.root = rootself.index = 0def tree_create(self,data_str,length):if self.index>length:return Nonedata = data_str[self.index]self.index += 1if data == "#":return Nonenode = Node(data)node.l_child = self.tree_create(data_str,length)node.r_child = self.tree_create(data_str,length)return nodedef pir_show(self,node):if node is not None:print(node.data,end = " ")self.pir_show(node.l_child)self.pir_show(node.r_child)def mid_show(self,node):if node is not None:self.mid_show(node.l_child)print(node.data, end=" ")self.mid_show(node.r_child)def last_show(self,node):if node is not None:self.last_show(node.l_child)self.last_show(node.r_child)print(node.data, end=" ")if __name__ == "__main__":tree = Tree()s = input("输入字符串创建二叉树")l = len(s)-1tree.root = tree.tree_create(s,l)tree.pir_show(tree.root)print()tree.mid_show(tree.root)print()tree.last_show(tree.root)
脑图
一、树形结构（层次结构）
1.1 基本概念
树形结构：数据元素之间存在一对多的关系
树：树是由根结点和若干个子结点组成的树形结构
结点：树的基本单位
根结点：没有父结点的节点称为根结点
父结点：当前结点的直接上级节点称为该节点的父结点
孩子结点：当前结点的直接下级节点称为该节点的孩子节点
兄弟节点：拥有相同父结点的结点互为兄弟节点
堂兄弟结点：其父结点在同一层次的结点互为堂兄弟结点
祖先结点：当前结点的直接或间接上级节点
子孙节点：当前结点的直接或间接下级节点
叶子节点：度为0的节点，或者说是没有孩子节点的节点
节点的度：就是该节点的子节点的个数
树的度：当前树中的节点的度的最大值就是树的度
节点的层次：从根结点出发，到该节点处所经历的层次称为该节点的层次
树的层次（深度）：节点层次的最大值就是树的层次
森林：由m（m>=0）个不相交的树构成的树形结构叫做森林
1.2 二叉树
每个节点最多拥有两个子结点，且严格区分左子树和右子树的树形结构。
1.3 二叉树相关概念
1】左子树：以当前节点的左孩子为根节点的子树称为该节点的左子树
2】右子树：以当前节点的右孩子为根节点的子树称为该节点的右子树
3】左斜树：该树上的每个节点都只有左孩子节点，没有右孩子节点的树
4】右斜树：该树上的每个节点都只有右孩子节点，没有左孩子节点的树
5】满二叉树：在不增加层次的基础上，不能再向树上增加节点
6】完全二叉树：在满二叉树的基础上，从左往右依次增加节点的二叉树叫完全二叉树
1.4 二叉树的形态
空树 只有根 根和左子树 根和右子树 根和左子树右子树
1.5二叉树的性质
1.二叉树的第i层上，最多又有2^(i-1)个结点
2.前k层最多拥有2^k-1个节点
3.任意一个二叉树上的叶子节点的数目比度为2的节点的数目多1
1.6二叉树的顺序存储
对于普通二叉树来说，创建顺序存储会造成大量的空间浪费，因此我们暂时不讨论，我们使用链式存储实现二叉树
1.7二叉树的链式存储
如图
1.8二叉树的封装
从上图我们可以看出一个二叉树的节点包含左孩子链接域，右孩子链接域，以及数据域。
class node:def __init__(self,data,l_child = None,r_child=None):self.data = dataself.l_child = l_childself.r_child = r_child除了节点外我们还需要头结点，帮我们找到根的位置，记录二叉树的节点，通过字符串创建二叉树，以及先序，中序，后序方法遍历二叉树。
对于头结点来说，我们不仅需要指向二叉树根的位置，还需要由成员变量index记录输入字符串的大小，默认为0
class Tree:def __init__(self,root = None):self.root = rootself.index = 0创建二叉树的实例方法，通过成员变量遍历啊字符串的数据，并通过递归传入子节点数据，返回字节的位置。此外我们还需要判断子节点是否存在根据实例变量index和标识符（这里以#作为空节点的标识符）
def tree_create(self,data_str,length):if self.index>length:return Nonedata = data_str[self.index]self.index += 1if data == "#":return Nonenode = Node(data)node.l_child = self.tree_create(data_str)node.r_child = self.tree_create(data_str)return node我们这里以先序遍历为例，展示存储结果
def pir_show(self,node):if node is not None:print(node.data,end = " ")self.pir_show(node.l_child)self.pir_show(node.r_child)def mid_show(self,node):if node is not None:self.mid_show(node.l_child)print(node.data, end=" ")self.mid_show(node.r_child)def last_show(self,node):if node is not None:self.last_show(node.l_child)self.last_show(node.r_child)print(node.data, end=" ")执行结果
if __name__ == "__main__":tree = Tree()s = input("输入字符串创建二叉树")l = len(s)-1tree.root = tree.tree_create(s,l)tree.pir_show(tree.root)print()tree.mid_show(tree.root)print()tree.last_show(tree.root)