二叉树的种类

<div class="image-package"><img src="https://img.haomeiwen.com/i1648392/46bbdb9f9961b4d4.jpg" img-data="{"format":"jpeg","size":159697,"height":900,"width":1600}" class="uploaded-img" style="min-height:200px;min-width:200px;" width="auto" height="auto"/>
</div><p>
</p><ol>
</ol><h1 id="xdlgj">树的基本说明</h1><h2 id="y02pg">树形结构</h2><h3 id="sp9fm">二叉树</h3><div class="image-package"><img src="https://img.haomeiwen.com/i1648392/af11eb12c385e10f.jpg" img-data="{"format":"jpeg","size":14690,"height":435,"width":491}" class="uploaded-img" style="min-height:200px;min-width:200px;" width="auto" height="auto"/>
</div><h3 id="54t3f">多叉树</h3><div class="image-package"><img src="https://img.haomeiwen.com/i1648392/46bf64b700db0d79.jpg" img-data="{"format":"jpeg","size":16278,"height":364,"width":450}" class="uploaded-img" style="min-height:200px;min-width:200px;" width="auto" height="auto"/>
</div><h2 id="nbdps">树的基本概念</h2><div class="image-package"><img src="https://img.haomeiwen.com/i1648392/53a023d9d49916ff.jpg" img-data="{"format":"jpeg","size":16278,"height":364,"width":450}" class="uploaded-img" style="min-height:200px;min-width:200px;" width="auto" height="auto"/>
</div><p>节点 : 所有的元素都是,1,2,3,4,5,6,7,21...221,222,223

根节点: 1

父节点: 2的父节点是1,21的父节点是2

子节点: 1的子节点是2,3,4,5,6,2的子节点是21,22

兄弟节点: 同一个父节点的节点,都是兄弟节点.2的兄弟节点是:3,4,5,6</p><p>空树: 没有任何节点叫做空树</p><p>子树: 比如1.下面的 2,3,4,5,6 各自都可以成为一个树.都是1的子树

左子树:一般是在二叉树里面. 比如2 的左子树是21

右子树:同左子树.只是是右边的树.比如2的右子树是22</p><p>节点的度:子树的个数 , 比如1的度是:5(2,3,4,5,6) , 2的度是2(21,22),21的度是0

树的度: 所有节点度中最大的值. 1的度是5,其他度都不超过5, 所以整棵树的度是5</p><p>叶子节点: 度为0的节点. 比如4, 21,31,51,52,61,221,222,223

非叶子节点:度不为0的节点</p><p>层数:如果1.为第一层的话.图中有4层.如果1,为第0层的话.图中有3层</p><p>节点的深度: 从根节点到当前节点的路径经过的节点数,比如21的深度.就是1,2,21. 所以深度为3</p><p>节点的高度: 从当前节点到最远叶子节点的路径的节点数, 比如1的高度.要经过1,2,22,221. 所以高度为4</p><p>树的深度:所有节点深度最大的值. 4</p><p>树的高度:所有节点高度中最大的值. 4</p><p>树的深度 = 树的高度</p><h3 id="72tq1">有序树</h3><div class="image-package"><img src="https://img.haomeiwen.com/i1648392/028a53dfe3fae74b.jpg" img-data="{"format":"jpeg","size":16278,"height":364,"width":450}" class="uploaded-img" style="min-height:200px;min-width:200px;" width="auto" height="auto"/>
</div><p>树种的任何节点之间有顺序排序</p><h3 id="qnexl">无序树</h3><p>树中节点之间没有顺序关系</p><p>森林</p><p>多个没有香蕉的树组成的就是森林</p><h2 id="kzwg2">二叉树</h2><div class="image-package"><img src="https://img.haomeiwen.com/i1648392/ede2dfb86d9623c1.jpg" img-data="{"format":"jpeg","size":23252,"height":374,"width":648}" class="uploaded-img" style="min-height:200px;min-width:200px;" width="auto" height="auto"/>
</div><h3 id="hrrzi">特点</h3><ol>
<li> 每个节点的度最大为2(最多拥有2棵子树)</li>
<li> 左子树和右子树是有顺序的</li>
<li> 即使只有一颗子树,也要区分左右子树</li>
<li> 二叉树是有序树</li>
</ol><h3 id="e8u7u">性质</h3><ol>
<li> 非空二叉树的第i层,最多有2^(i-1)个节点(i≥1)</li>
<li> 在高度为h的二叉树上最多有2^h - 1 个节点(h≥1)</li>
<li> 对于任何一颗非空二叉树,如果叶子节点个数为n0,度为2的节点个数为n2, 则:n0 = n2 + 1</li>
<ul>
<li> 假设度为1的节点个数为n1,二叉树的节点总数n = n0 + n1 + n2</li>
<li> 二叉树的边数T = n1 + 2 * n2 = n - 1 = n0 + n1 + n2 -1</li>
</ul>
</ol><h1 id="4p44i">二叉树的种类</h1><h2 id="puaom">真二叉树<b>(Proper Binary Tree , </b>完满二叉树<b>(Full Binary Tree))</b></h2><p>所有节点的度都要嘛是0,要么是2</p><div class="image-package"><img src="https://img.haomeiwen.com/i1648392/ed005c33d2623b3c.jpg" img-data="{"format":"jpeg","size":15283,"height":359,"width":322}" class="uploaded-img" style="min-height:200px;min-width:200px;" width="auto" height="auto"/>
</div><h2 id="ncy4t">满二叉树<b>(Full Binary Tree , </b>完美二叉树<b>(Perfect Binary Tree))</b></h2><div class="image-package"><img src="https://img.haomeiwen.com/i1648392/7bfb9ac6794a65b1.jpg" img-data="{"format":"jpeg","size":35116,"height":364,"width":849}" class="uploaded-img" style="min-height:200px;min-width:200px;" width="auto" height="auto"/>
</div><ol>
<li> 所有节点的度要么为0,要么为2.且所有的叶子节点都在最后一层</li>
<li> 在同样高度的二叉树中,满二叉树的叶子节点数量最多,总结点数量最多</li>
<li> 满二叉树一定是真二叉树,真二叉树不一定是满二叉树</li>
</ol><h3 id="kw5nq">性质</h3><ol>
<li> 假设满二叉树的高度为h(h > 0)</li>
<ul>
<li> 第i层的节点数量:2^(i-1)</li>
<li> 叶子节点数量: 2^(h-1)</li>
<li> 总结点数量n = 2^h - 1 = 2^0 + 2^1 + 2^2 + ... + 2 ^(h-1)</li>
<li> h = log2(n+1)</li>
</ul>
</ol><h2 id="3an06">完全二叉树<b>(Complete Binary Tree)</b></h2><div class="image-package"><img src="https://img.haomeiwen.com/i1648392/0246cdcefe6f38f0.jpg" img-data="{"format":"jpeg","size":16680,"height":428,"width":585}" class="uploaded-img" style="min-height:200px;min-width:200px;" width="auto" height="auto"/>
</div><ol>
<li> 叶子节点只会出现最后2层,且最后1层的叶子节点都靠左对齐</li>
<li> 完全二叉树从根节点至倒数第二层是一颗满二叉树</li>
<li> 满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树</li>
</ol><h3 id="44ryc">性质</h3><ol>
<li> 度为1的节点只有左子树</li>
<li> 度为1的节点要么是1个,要么是0个</li>
<li> 同样节点数量的二叉树,完全二叉树的高度最小</li>
<li> 假设完全二叉树的高度为h(h>0),</li>
<ul>
<li> 至少有2^(h-1) 个节点 (2^0 + 2^1 + 2^2 + ... + 2^(h-2) + 1)</li>
<li> 最多有2^h - 1个节点(满二叉树)</li>
<li> 总节点数量是n , h = floor(log2n) + 1</li>
</ul>
</ol><div class="image-package"><img src="https://img.haomeiwen.com/i1648392/dcf1aa70fa6b81cc.jpg" img-data="{"format":"jpeg","size":16680,"height":428,"width":585}" class="uploaded-img" style="min-height:200px;min-width:200px;" width="auto" height="auto"/>
</div><ol>
<li> 一颗有n个节点的完全二叉树(n>0),从上到下,从左到右对节点从1开始编号.对任意第i个节点</li>
<ul>
<li> 如果i = 1 , 他的根节点</li>
<li> 如果i > 1, 他的父节点编号floor(i / 2)</li>
<li> 如果2i ≤ n, 他的左子节点编号为2i</li>
<li> 如果2i > n, 他没有左子节点</li>
<li> 如果2i + 1 ≤ n, 他的右子节点编号2i + 1</li>
<li> 如果2i + 1 > n, 他没有右子节点</li>
</ul>
<li> 一颗有n个节点的完全二叉树(n>0),从上到下,从左到右对节点从0开始编号.对任意第i个节点</li>
<ul>
<li> 如果i = 0 , 他的根节点</li>
<li> 如果i > 0, 他的父节点编号floor((i-1) / 2)</li>
<li> 如果2i + 1 ≤ n - 1, 他的左子节点编号为2i + 1</li>
<li> 如果2i + 1 > n - 1, 他没有左子节点</li>
<li> 如果2i + 2 ≤ n - 1, 他的右子节点编号2i + 2</li>
<li> 如果2i + 2 > n - 1, 他没有右子节点</li><li>
</li>
</ul>
</ol><p>参考</p><p>

</p><p>M了个J : https://www.cnblogs.com/mjios </p>