树形一对多反映的是一种层次结构eg祖宗爷爷叔叔 爸爸 伯伯你班级组织结构企业组织架构家谱等都是树这种结构一、概念1. 递归式的定义树是nn≥0个结点的有限集合·当n0时称为空树·当n0时满足1有且仅有一个根结点Root2其余结点可分为mm≥0个互不相交的有限集合T1T2…,Tm每个集合本身也是一棵树称为根的子树Subtree2. 二叉树Binary Tree1定义二叉树是nn≥0个结点的有限集合·或为空树n0;·或由一个根结点和两棵互不相交的子树组成分别称为左子树和右子树且二者有严格顺序。2特点1.每个结点最多有两个子树2.左、右子树有顺序不可互换;3.即使某结点仅有一个子树也必须明确是左子树还是右子树。所以我们通常定义成这样的结构体来表示二叉树这种类型二、叉树的遍历深度优先前序遍历---根左右中序遍历---左根右后续遍历---左右根广度优先层次遍历1. 前序遍历前序遍历ABDGHCEIF2. 中序遍历中序遍历GDHBAEICF3. 后序遍历后序遍历GHDBIEFCA4. 另1. 每个节点都走了对应访问次序如果是前序则每个节点都走了一下前序的访问过程2. 假设知道前序 和中序前序遍历—根左右 //主要知道谁是根ABDGHCEIF中序遍历—左根右 //主要知道谁左谁右GDHBAEICF4.---------就可以知道这个二叉树的样子同理知道中序和后序也能知道二叉树的样子但只知道前序和后序无法知道二叉树的样子三、代码实现1. 定义节点2. 创建二叉树3. 前序遍历4. 中序遍历5. 后序遍历6. 广度遍历广度遍历按照层次依次输出需要用到在队列时写的函数笔记在前面有