第5章 树与二叉树
【树的定义】： 1. 有【n个有限结点】。
2. 当（没有结点），称为【空树】。
3.非空树，都有一个【根】结点
用于存放【分层的数据】。
树是一种【逻辑结构】，【根结点】没有前驱，所有结点可以有n一个或者无数多个后继节点。
【关于树的术语】： 孩子的个数叫做【度】
【结点】因为孩子个数而改名【分支节点】是度大于0
【叶子节点】：没有子女
【结点的层次】：从【树根】开始算起 【树根 1层】，【子节点2层】
【有序树】：子树从左到右是【有序的】。
【路径长度】：边的个数
【森林】：不相交的树
【树的性质】： 【结点数】：等于度数+1
【二叉树】：说人话就是【二胎政策】：【只】能有【俩个】【孩子】，并且有【左】孩子，【右】孩子区分
【几个特殊的二叉树】：【满二叉树】：
【完全二叉树】：
chapter2：二叉树的遍历和线索二叉树
【二叉树遍历】：按照 其中一条【搜索路径】遍历完【所有结点】，所有结点仅【仅】可以被【访问一次】。
由于【遍历的提出】，所以我们要找到一种将【非线性结构】转换称为【线性结构】的规则让他具有一个【直接前驱】或【直接后驱】。 我们采用【左子树】，【右子树】访问【序】来达到【线性结构】。
chapter2.1.1先序遍历
Ⅰ.若二叉树是【空】（判断）
Ⅱ.则不做任何操作（操作）。
一.若二叉树不是空的（判断）。
二.访问根节点（操作）。
三.遍历左边的所有结点
四.先序遍历所有右节点
chapter2.1.2中序遍历
Ⅰ.若二叉树是【空】（判断）
Ⅱ.则不做任何操作（操作）。
一.若二叉树不是空的（判断）。
二. 遍历左边的所有结点
三.访问根节点（操作）。
四.先序遍历所有右节点
chapter2.1.3后序遍历
Ⅰ.若二叉树是【空】（判断）
Ⅱ.则不做任何操作（操作）。
一.若二叉树不是空的（判断）。
二. 遍历左边的所有结点
三 .先序遍历所有右节点
四 .访问根节点（操作）。
由于每一个结点有且只访问一次，所示时间复杂度是
其中递归的顺序是：
若为先序遍历：先从根结点开始访问所有左孩子入栈，然后出栈。若根的右孩子不是空的，从根的右孩子进栈然后出栈。
2.2层次遍历
【定义】：按照树的层次一层一层的遍历，达到所有结点访问一次。我们可以借【队列】来达到层次遍历。首先根结点先入队出队，然后下一层从左孩子开始入队出队。直到队列为【空】。
2.3由遍历序列构造二叉树
例： 如果我们知道
先序（A BCDEFGHI） 中序（BC A EDGHFI）
通过对先序顺序排列【先序遍历】确定【根结点】（记住【根】结点只能由【先序】确定，【中序】确定是【左边】还是【右边】）。
找到先序遍历的最中间的那个
2.4线索二叉树
利用【叶节点】的【空指针】来存放【直接前驱】或【后继】，这样就可以像【遍历单链表一样遍历【二叉树】。这样【达到】【引入线索二叉树的目的：加快前后驱结点的查找效率】
【线索二叉树的规定】：该节点没有【左子树】，lchild指向【前驱节点】，引入ltag是标识{ltag=0时指向左孩子，ltag=1时指向前驱节点}
由于二叉树被线索化，要找到其【前驱节点】要【从头开始遍历】
【分类】先序线索树，中序线索树，后续线索树
chapter2.4.1 一般二叉树转换为线索二叉树
首先，根据要求转换为对应的【先中后序】，然后线索化标记： 【看图】找到结点谁没有【左孩子】，然后根据【前中后序】找到它的【前驱结点】，然后【引虚线】
【总结】：前驱节点指的是【排序左边的那个】...以此类推。
