树树的介绍树的定义基本术语存储结构二叉树一、树Tree的基本概念1. 定义 ---递归式的定义树是nn ≥ 0个结点的有限集合当n 0时称为空树当n 0时满足有且仅有一个根结点Root其余结点可分为mm ≥ 0个互不相交的有限集合 T₁, T₂, ..., Tₘ每个集合本身也是一棵树称为根的子树Subtree。2. 基本术语术语说明结点的度Degree结点拥有的子树个数叶结点Leaf度为 0 的结点也称终端结点分支结点Internal Node度不为 0 的结点也称非终端结点树的度树中所有结点的度的最大值结点的层次Level根结点为第 1 层其子结点为第 2 层依此类推树的深度 / 高度Depth / Height树中结点的最大层次数3. 存储结构顺序存储适用于完全二叉树等结构规则的树常用数组实现链式存储通用方式每个结点包含数据域和指向子结点的指针域。二叉树定义二叉树是nn ≥ 0个结点的有限集合或为空树n 0或由一个根结点和两棵互不相交的子树组成分别称为左子树和右子树且二者有严格顺序。特点每个结点最多有两个子树左、右子树有顺序不可互换即使某结点仅有一个子树也必须明确是左子树还是右子树。特殊二叉树二叉树的遍历深度优先前序遍历根---左---右中序遍历左---根---右后序遍历左---右---根前中后序的组合总结深度优先二叉树的相关代码二叉树序列代码表示方法前序扩展序列 --- 根 左 右ABDH##H###CE#I##F##没有了的部分用#表示创建二叉树前序遍历并打印二叉树中序遍历并打印二叉树后序遍历并打印二叉树广度优先层次遍历层次遍历具体代码应用---结合队列具体思路代码对应的层次遍历二叉树 . h 文件以及队列的 , h 文件的写法