树(Tree)是n个结点的有限集。
在任意一棵非空树中：
(1) 有且仅有一个特定的称为跟(Root)的结点
(2) 当n > 1时，其余结点可以分为m(m > 0)个互不相交的有限集T1, T2,…,Tm,其中每一个集合本身又是一棵树，并且称为树的子树(SubTree)
由上可以看出，树的定义本身是递归定义的。
思考: 此处是否意味着树的某些操作可以递归来定义呢？
结点拥有的子树数称为结点的度
度为0的结点称为叶子或终端结点
树的度是树内各结点的度的最大值
树中结点的最大层次称为树的深度或高度
森林是m(m>0)棵互不相交的树的集合。
对树中每个结点而言，其子树的集合为森林。
森林和树相互递归地定义来描述树
一棵N个结点的树有N-1条边(因为除了root，其它结点都经由一条边出去)
任意的树都可以用儿子(一个结点指向第一个儿子)、兄弟(另一个结点指向下一个兄弟)表示法将其转变成二叉树
二叉树，首先它是一棵树，它的特定是每个结点至多只有两颗子树(即二叉树中不存在度大于2的结点)。并且，二叉树的子树有左右之分，其次序不能任意颠倒。
二叉树的性质
性质1. 在二叉树的第i层至多有2i-1个结点(归纳法)
性质2. 深度为k的二叉树至多有2k -1 个结点(公式)
性质3. 对任何一棵二叉树T，如果其终端结点数为n0，度为2的节点数为n2，则n0 = n2 + 1
一棵深度为k且有2k-1个结点的二叉树称为满二叉树
深度为k，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树编号从1至n的结点一一对应时，称之为完全二叉树
满二叉树 VS 完全二叉树
完全二叉树的存储方式
- 顺序存储(根结点为1)
编号为i的左子树为2i, 右子树为2i+1
- 链式存储
lchild data rchild
二叉树遍历
- 先序
- 中序
- 后序
中序遍历非递归遍历
遇到一个结点，将其压入堆栈，并去遍历它的左子树
当左子树遍历结束，从栈顶弹出这个结点并访问它
然后对右子树再进行中序遍历
中序遍历非递归算法1.png
先序遍历非递归遍历
先序遍历非递归算法.png
后序遍历非递归遍历
print语句放在T = T-> Right 之后？
网友评论