树数据结构：树的定义、特点和二叉树

带双亲的孩子链表 本节课件主要讲解了树这种非线性数据结构的概念和特点，并对树的定义、基本术语和二叉树进行了详细的介绍。 树的定义：树是一类重要的非线性数据结构，是以分支关系定义的层次结构。它由n(n>0)个结点的有限集T组成，其中有且仅有一个特定的结点，称为树的根(root)；当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree)。 树的特点： * 树中至少有一个结点——根 * 树中各子树是互不相交的集合 基本术语： * 结点(node)——表示树中的元素，包括数据项及若干指向其子树的分支 * 结点的度(degree)——结点拥有的子树数 * 叶子(leaf)——度为0的结点 * 孩子(child)——结点子树的根称为该结点的孩子 * 双亲(parents)——孩子结点的上层结点叫该结点的双亲 * 兄弟(sibling)——同一双亲的孩子 * 树的度——一棵树中最大的结点度数 * 结点的层次(level)——从根结点算起，根为第一层，它的孩子为第二层…… * 深度(depth)——树中结点的最大层次数 * 森林(forest)——m(m≥0)棵互不相交的树的集合 二叉树的定义：二叉树是n(n≥0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成。 二叉树的特点： * 每个结点至多有二棵子树(即不存在度大于2的结点) * 二叉树的子树有左、右之分，且其次序不能任意颠倒 二叉树的基本形态： * 只有根结点的二叉树 * 空二叉树 * 右子树为空的二叉树 * 左子树为空的二叉树 * 左、右子树均非空的二叉树 二叉树的性质： * 性质1：在二叉树的第i层上至多有2^(i-1)个结点。 本节课件对树的概念和特点进行了详细的介绍，对树的定义、基本术语和二叉树进行了详细的介绍，为后续学习树和二叉树的算法和应用奠定了基础。