文章目录Tree 树Definition 定义Some Important Terminology 一些重要的概念Some Important 一些重要的性质Binary Tree 二叉树Definition 定义Properties 性质二叉树的顺序存储二叉树的链式存储Tree 树Definition 定义树是n ( n ≥ 0 ) n(n\ge0)n(n≥0)个结点的有限集合当n 0 n0n0时称为空树。对于任意一棵树都有有且仅有一个根结点root从根节点到其他结点有且只有一条路径这是图论中对于树的定义事实上树是有向图的一种这是一种非递归的定义而显然树是一种递归的结构我们可以用递归的方式对树进行定义当n ≥ 1 n\ge1n≥1时其余结点可以分为m gt; 0 mgt;0m0个互不相交的有限集合T 1 , T 2 , T 3 , … , T m T_{1},T_{2},T_{3},\dots,T_{m}T1,T2,T3,…,Tm这些集合本身都是一棵树并且称为根结点的子树这样的递归结构具有以下的特点除了根结点之外的所有结点有且只有一个前驱结点每个结点都有零个或者多个结点Some Important Terminology 一些重要的概念关于结点关系TerminologyExplanation父结点(parent node)该结点的前驱结点称为该结点的父结点子结点(children node)该结点的后继结点成为该结点的子结点兄弟结点(sibling node)具有相同父结点的结点互为兄弟结点关于结点的一些概念TerminologyExplanation结点的度一个结点的子结点的度结点的最大度数是树的度数分支结点非终端结点度数不为0的点叶子结点终端结点度数为0的结点即只有前驱结点但是没有后继结点从图论的角度来说这样的结点入度in degree为1出度out degree为0关于树的一些概念TerminologyExplanation结点的层次从根结点开始是第一层或者是第零层取决于具体要求结点的深度从根结点开始逐层累加结点的高度从最后一层开始逐层累加树的高度同时也是树的深度树的最大层数从树的结点次序来看还可以分为有序树和无序树Some Important 一些重要的性质树具有一下基本的性质如果树的结点度数是k kk则树的结点数量为n k 1 nk1nk1考虑一个无环图那么这个图的结点数量肯定是边数量加1 11而一个结点的一个度数对应一条边所以结点数量就是总度数加1 11度为m mm的树种第i ii层上至少有m i − 1 m^{i-1}mi−1个结点高度为h hh度为m mm的树至多有n 1 m m 2 ⋯ m h − 1 ( m h − 1 ) / ( m − 1 ) n1 m m^{2} \dots m^{h-1}(m^{h}-1)/(m-1)n1mm2⋯mh−1(mh−1)/(m−1)个结点例如我们熟悉的二叉树的结点总数为( 2 h − 1 ) / ( 2 − 1 ) 2 h − 1 (2^{h}-1)/(2-1)2^{h}-1(2h−1)/(2−1)2h−1个有n nn个结点的m mm叉树的高度至少为log m ( n ( m − 1 ) 1 ) \log_{m}(n(m-1)1)logm(n(m−1)1)Binary Tree 二叉树Definition 定义二叉树即树的度数为2有左右子树之分不能任意颠倒通常类似一棵度为2 22的有序树区别在于二叉树可以为∅ \varnothing∅但是度为2 22的有序树至少有3 33个结点当一个结点只有一个孩子的时候对于有序树的结点来说无需区分左右而对于二叉树来说这个子结点必须区分左右结点次序是确定的一些特殊的二叉树满二叉树树的每一层的结点数量都是该层的最大结点数量完全二叉树满二叉树一定是完全二叉树但是完全二叉树不一定是满二叉树。完全二叉树是根节点和分支结点的度都为2 22的树Properties 性质二叉树的性质非空二叉树的叶子结点数n 0 n_{0}n0等于度为2 22的结点数n 2 n_{2}n2加一即n 0 n 2 1 n_{0}n_{2}1n0n21证 明 由 树 的 性 质 有 结 点 总 数 N 1 ⋅ n 1 ⋯ m ⋅ n m 其 中 m 是 树 的 度 即 结 点 最 大 度 数 又 ∵ N n 1 ⋯ n m ∴ 对 于 二 叉 树 有 { N n 0 n 1 n 2 N 0 ⋅ n 0 1 ⋅ n 1 2 ⋅ n 2 1 n 1 2 ⋅ n 2 1 ∴ n 0 n 2 1 \footnotesize \begin{aligned} amp;证明\\ amp;由树的性质有结点总数 N1\cdot n_{1}\cdotsm\cdot n_{m}其中 m 是树的度即结点最大度数\\ amp;又\because Nn_{1}\cdotsn_{m}\\ amp;\therefore 对于二叉树有 \begin{cases} amp;Nn_{0}n_{1}n_{2}\\ amp;N0\cdot n_{0}1\cdot n_{1}2\cdot n_{2}1n_{1}2\cdot n_{2}1 \end{cases}\\ amp;\therefore n_{0}n_{2}1 \end{aligned}证明由树的性质有结点总数N1⋅n1⋯m⋅nm其中m是树的度即结点最大度数又∵Nn1⋯nm∴对于二叉树有{Nn0n1n2N0⋅n01⋅n12⋅n21n12⋅n21∴n0n21第i ii层最多有2 i − 1 2^{i-1}2i−1个结点高度为h hh的二叉树至多有2 h − 1 2^{h} - 12h−1个结点二叉树的顺序存储存储结点的顺序自上而下从左到右即一层一层的存储先存储第一层也就是树根在数组的第一个位置然后从左到右存储下一层以此类推这样存储则有结点a [ i ] a[i]a[i]的两个子结点的位置为a [ 2 i 1 ] , a [ 2 i 2 ] a[2i1],a[2i2]a[2i1],a[2i2]结点a [ i ] a[i]a[i]如果i不等于0 00的父结点为a [ ( i − 1 ) / 2 ] a[(i-1)/2]a[(i−1)/2]当然你也可以从数组下标为1的位置开始存储这样在下标计算的时候可以更加简单采用顺序存储结构在存储满二叉树和完全二叉树的时候空间利用率较高既可以直接访问又可以通过下标确定相关结点但是最坏的情况下一棵高度为h hh包含h hh个结点的二叉树需要占据2 H − 1 2^{H}-12H−1个存储单元。并且顺序存储的二叉树不适合进行插入删除操作二叉树的链式存储typedefstructNode{ElementType value;Node*left;Node*right;Node(ElementType value_,left_NULL,right_NULL):value(value_),left(left_),right(right_){}}Node;
