树的术语、二叉树的性质、二叉树的基本操作总结

傷城~ 2022-06-09 04:06 237阅读 0赞

**一、树的术语**

<table style=""> 
 <tbody> 
  <tr> 
   <td style="border:1px solid rgb(211,211,211); padding:10px; margin:0px; width:4.003021148036254%"> 序号</td> 
   <td style="border:1px solid rgb(211,211,211); padding:10px; margin:0px; width:11.10271903323263%"> 术语</td> 
   <td style="border:1px solid rgb(211,211,211); padding:10px; margin:0px; width:84.81873111782477%"> 概念</td> 
  </tr> 
  <tr> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:25%"> 1</td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:25%"> 结点</td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:50%"> 包含一个数据元素及若干指向其子树的分支。在树的图形表示中为一个圆圈。</td> 
  </tr> 
  <tr> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:25%"> 2</td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:25%"> 孩子(Child）</td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:50%"> 结点的子树的根，称为该结点的孩子</td> 
  </tr> 
  <tr> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:25%"> 3</td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:25%"> 兄弟(Sibling)</td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:50%"> 同一个双亲的孩子之间互称为兄弟。</td> 
  </tr> 
  <tr> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:25%"> 4</td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:25%"> 堂兄弟</td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:50%"> 其双亲在同一层的结点互为堂兄弟。</td> 
  </tr> 
  <tr> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:25%"> 5</td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:25%"> 树的度</td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:50%"> 结点拥有的子树数量。</td> 
  </tr> 
  <tr> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:25%"> 6</td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:25%"> 结点度(Degree)</td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:50%"> 树内各结点的度的最大值。</td> 
  </tr> 
  <tr> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:25%"> 7</td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:25%"> 节点层次</td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:50%"> 从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第k层，则其子树的就在第k+1 层。</td> 
  </tr> 
  <tr> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:25%"> 8</td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:25%"> 深度（高度）(Depth)</td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:50%"> 树中结点的最大层次。</td> 
  </tr> 
  <tr> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:25%"> 9</td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:25%"> 边</td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:50%"> 指结点连接孩子的边。</td> 
  </tr> 
  <tr> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:25%"> 10</td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:25%"> 树的边数</td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:50%"> 是指结点连接孩子的边的总和(结点数-1)</td> 
  </tr> 
  <tr> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:25%"> 11</td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:25%"> 路径和路径长度</td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:50%"> 从结点n1到nk的路径为一个结点序列n1，n2，...，nk。ni是ni+1的父结点。路径所包含边的个数为路径的长度。</td> 
  </tr> 
  <tr> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:25%"> 12</td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:25%"> 有序无序</td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:50%"> 有序树有序树树中任意节点的子结点之间有顺序关系，这种树称为有序树有序树无序树树中任意节点的子结点之间没有顺序关系，这种树称为无序树,也称为自由树</td> 
  </tr> 
  <tr> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:25%"> 13</td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:25%"> 森林</td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:50%"> 是m (m&gt;=0) 棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林</td> 
  </tr> 
  <tr> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:25%"> 14</td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:25%"> 叶子</td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:50%"> 度为0的结点。即没有子树的结点。</td> 
  </tr> 
 </tbody> 
</table>

**二、二叉树的性质**

性质1： 二叉树第i层上的结点数目最多为2i-1(i≥1)。

性质2 ：深度为k的二叉树至多有2k-1个结点(k≥1)。

性质3： 在任意-棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，no=n2+1。

满二叉树和完全二叉树是二叉树的两种特殊情形。

1、满二叉树(FullBinaryTree)

一棵深度为k且有2k-1个结点的二又树称为满二叉树。

满二叉树的特点：

（1）每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。

（2）满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上。

2、完全二叉树(Complete BinaryTree)

若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。

特点：

（1）    满二叉树是完全二叉树，完全二叉树不一定是满二叉树。

（2）    在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。

（3）    在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。

性质4 ：具有n个结点的完全二叉树的深度为

![Image 1][]

**三、二叉树的操作**

<table style="border-collapse:collapse; margin-left:0px; table-layout:fixed; width:25.377643504531722%"> 
 <tbody> 
  <tr> 
   <td style="border:1px solid rgb(211,211,211); padding:10px; margin:0px; width:17.857142857142858%"> 序号</td> 
   <td style="border:1px solid rgb(211,211,211); padding:10px; margin:0px; width:81.84523809523809%"> 操作</td> 
  </tr> 
  <tr> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:50%"> 1</td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:50%"> 求二叉树中的节点个数</td> 
  </tr> 
  <tr> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:50%"> 2</td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:50%"> 求二叉树中叶子节点的个数</td> 
  </tr> 
  <tr> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:50%"> 3</td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:50%"> 求二叉树的深度</td> 
  </tr> 
  <tr> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:50%"> 4</td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:50%"> 求二叉树第K层的节点个数</td> 
  </tr> 
  <tr> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:50%"> 5</td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:50%"> 递归遍历前序中序后序</td> 
  </tr> 
  <tr> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:50%"> 6</td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:50%"> 
    <div>
      非递归遍历前序中序后序层序 
    </div> 
    <div>
      1 前序遍历 
    </div> 
    <div>
      2 中序遍历 
    </div> 
    <div>
      3 后序遍历 
    </div> 
    <div>
      4 层序遍历 
    </div> </td> 
  </tr> 
  <tr> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:50%"> 7</td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:50%"> 将二叉查找树变为有序的双向链表</td> 
  </tr> 
  <tr> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:50%"> 8</td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:50%"> 求二叉树的镜像</td> 
  </tr> 
  <tr> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:50%"> 9</td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:50%"> 判断两棵二叉树是否结构相同</td> 
  </tr> 
  <tr> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:50%"> 10</td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:50%"> 判断二叉树是不是平衡二叉树</td> 
  </tr> 
  <tr> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:50%"> 11</td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:50%"> 判断二叉树是否是搜索二叉树</td> 
  </tr> 
  <tr> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:50%"> 12</td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:50%"> 判断二叉树是不是完全二叉树</td> 
  </tr> 
  <tr> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:50%"> 13</td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:50%"> 求二叉树中两个节点的最低公共祖先节点</td> 
  </tr> 
  <tr> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:50%"> 14</td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:50%"> 求二叉树中节点的最大距离</td> 
  </tr> 
  <tr> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:50%"> 15</td> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:50%"> 由前序遍历序列和中序遍历序列重建二叉树</td> 
  </tr> 
 </tbody> 
</table>

[Image 1]: