【数据结构】有序树和无序树的区别

你的名字 2022-06-12 09:18 289阅读 0赞

这个问题想了好久才弄清楚，现在总结一下。

概念是这样的：

<table style=""> 
 <tbody> 
  <tr> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:100%"> 
    <div>
      有序树 
    </div> 
    <div>
      树中任意节点的 
     <span style="color:rgb(255,0,0)">子结点之间有顺序关系</span>，这种树称为有序树 
    </div> 
    <div> 
     <br> 
    </div> 
    <div>
      无序树 
    </div> 
    <div>
      树中任意节点的 
     <span style="color:rgb(255,70,53)">子结点之间没有顺序关系</span>，这种树称为无序树,也称为自由树 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

换而言之，兄弟结点有顺序的树，称为有序树，兄弟之间无顺序的树称为无序树。

那么，3个结点到底能组成多少种有序树，多少种无序树呢？

先看无序树，兄弟无序，但是父子还是有序的

<table style=""> 
 <tbody> 
  <tr> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:100%"> 
    <div>
      假设有A、B、C三个结点，总共可以组成 
     <span style="color:rgb(255,0,0)">9</span> 种无序树，分别是： 
    </div> 
    <ul> 
     <li>1个父节点，2个子结点的情况有 3 种</li> 
     <li>链式结构有 6 种（因为链式结构相互之间都是父子关系，所以有 6 种不同的组合）</li> 
    </ul> </td> 
  </tr> 
 </tbody> 
</table>

理解了无序树，有序树也更好理解了

<table style=""> 
 <tbody> 
  <tr> 
   <td style="border-style:solid; border-width:1px; border-color:rgb(211,211,211); padding:10px; margin:0px; width:100%"> 
    <div>
      有A、B、C三个结点，总共有 
     <span style="color:rgb(255,0,0)">12</span> 种有序树，分别是： 
    </div> 
    <ul> 
     <li>1个父节点，2个子结点的情况有 6 种</li> 
     <li>链式结构有 6 种</li> 
    </ul> </td> 
  </tr> 
 </tbody> 
</table>

三个结点组成的二叉树，种类就更多了，有 30 种

下面的类型，每一个都有6种

![SouthEast][] ![SouthEast 1][] ![SouthEast 2][] ![SouthEast 3][] ![SouthEast 4][]

[SouthEast]: https://img-blog.csdn.net/20170720163933469?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvcXFfMzA1OTQzNDk=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 1]: https://img-blog.csdn.net/20170720164015648?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvcXFfMzA1OTQzNDk=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 2]: https://img-blog.csdn.net/20170720164038931?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvcXFfMzA1OTQzNDk=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 3]: https://img-blog.csdn.net/20170720164050206?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvcXFfMzA1OTQzNDk=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 4]: /images/20220612/6d26a0a3e3424f35ba94264e1f572082.png