Loading... <h1>二叉树的存储结构</h1> <p>二叉树可使用顺序结构和链表结构两种存储结构</p> <h2>顺序结构</h2> <p>顺序结构实现二叉树时,采用一个一维数组来存储所有结点,需要将所有结点按照在树中的位置安排成一个恰当的序列,使其能反应结点之间相互的逻辑关系,通常使用编号的方法;</p> <h5>具体方法:</h5> <p>将二叉树中所有结点<span style="color:red;font-weight:bold">按照完全二叉树进行编号</span>,然后使用一维数组存储,同时使结点编号与数组下标相同,如编号为1的节点存储在数组下标为1的位置;该方法称为<span style="color:red;font-weight:bold">以编号为地址</span>的策略</p> <h5>案例1(完全二叉树):</h5> <img src="https://img2020.cnblogs.com/blog/1440878/202005/1440878-20200521021019045-1104316012.png" class="aligncenter"> <p>若二叉树为完全二叉树则上述方法,可以很好的利用存储空间,基本没有浪费,且对于结点的查找是很方便的;</p> <h5>案例2(一般二叉树):</h5> <img src="https://img2020.cnblogs.com/blog/1440878/202005/1440878-20200521021052476-1901895843.png" class="aligncenter"> <p>当二叉树为一般二叉树时,如想要使用顺序结构存储则必须增加虚拟结点,使其变为完全二叉树,像下面这样:</p> <img src="https://img2020.cnblogs.com/blog/1440878/202005/1440878-20200521021112391-1311921418.png" class="aligncenter"> <p>这样一来则需要浪费一部分存储空间,极端情况下,若二叉树是一分叉的(每个节点只有一个子节点),将造成极大的空间浪费</p> <img src="https://img2020.cnblogs.com/blog/1440878/202005/1440878-20200521021130378-534458747.png" class="aligncenter"> <h2>链式存储结构</h2> <p>链式存储结构,分为两种二叉链表和三叉链表</p> <h3>二叉链表</h3> <p>每个结点由一个数据域和两个指针域组成,共三个部分,如下图所示</p> <img src="https://img2020.cnblogs.com/blog/1440878/202005/1440878-20200521021345400-1774419674.png" class="aligncenter"> <h5>数据结构定义:</h5> <pre><code>typedef struct btnode { DataType data; struct btnode *lchild,*rchild; }*BinTree; </code></pre> <h5>案例:</h5> <img src="https://img2020.cnblogs.com/blog/1440878/202005/1440878-20200521021418002-1218007227.png" class="aligncenter"> <p>由于使用了链式存储结构,在插入或删除结点时效率比顺序结构更好;并且不会造成较大的空间浪费;</p> <h5>特性:</h5> <ul> <li>n个结点组成的二叉树<span style="color:red;font-weight:bold">共有2n个指针域</span>,其中有<span style="color:red;font-weight:bold">n-1个指向左右子结点</span>的非空指针域,(两个节点关联需要一个指针域,以此类推3个结点关联需要2个指针域)和<span style="color:red;font-weight:bold">n+1个空指针域</span></li> <li>已知某结点地址求其子结点方便,求其父节点则需要从头开始遍历</li> </ul> <h3>三叉链表</h3> <p>由于二叉链表查找父结点需要遍历所有结点,效率较低,若对于经常需要查询父结点的二叉树,则可以使用三叉链表来提高效率,三叉链表在二叉链表的基础上增加了一个parent指针域,如下图所示:</p> <img src="https://img2020.cnblogs.com/blog/1440878/202005/1440878-20200521021457600-371315523.png" class="aligncenter"> <h5>案例:</h5> <img src="https://img2020.cnblogs.com/blog/1440878/202005/1440878-20200521021529530-943799562.png" class="aligncenter"> 可以看出三叉链表与二叉链表没有太大区别,牺牲一些空间换来了查询父结点的效率;<hr class="content-copyright" style="margin-top:50px" /><blockquote class="content-copyright" style="font-style:normal"><p class="content-copyright">版权属于：撩人的无眠兔</p><p class="content-copyright">本文链接：<a class="content-copyright" href="https://www.wumiantu.com/technology/MK8CeN.html">https://www.wumiantu.com/technology/MK8CeN.html</a></p><p class="content-copyright">转载时须注明出处及本声明</p></blockquote> © 允许规范转载 赞赏 看了文章不打款？ ×Close 赞赏作者 扫一扫支付 支付宝支付 微信支付