对使用 Python 学习数据结构和算法的资料进行收集并学习.zip

# 树 ## 概念 在计算机科学中，树（tree）是一种抽象数据类型（ADT）或是实现这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>0）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。 ## 生活实例 族谱 ## 特点： - 每个节点都只有有限个子节点或无子节点； - 没有父节点的节点称为根节点； - 每一个非根节点有且只有一个父节点； - 除了根节点外，每个子节点可以分为多个不相交的子树； - 树里面没有环路(cycle) ## 图示  ## 术语 - **节点的度**：一个节点含有的子树的个数称为该节点的度； - **树的度**：一棵树中，最大的节点度称为树的度； - **叶节点**或终端节点：度为零的节点；  - 非终端节点或分支节点：度不为零的节点； - 父亲节点或**父节点**：若一个节点含有子节点，则这个节点称为其子节点的父节点； - 孩子节点或**子节点**：一个节点含有的子树的根节点称为该节点的子节点； - 兄弟节点：具有相同父节点的节点互称为兄弟节点； - 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推； - **深度**：对于任意节点n,n的深度为从根到n的唯一路径长，根的深度为0； - **高度**：对于任意节点n,n的高度为从n到一片树叶的最长路径长，所有树叶的高度为0；  - 堂兄弟节点：父节点在同一层的节点互为堂兄弟； - 节点的祖先：从根到该节点所经分支上的所有节点； - 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。 - 森林：由m（m>=0）棵互不相交的树的集合称为森林； ## 分类 <table cellspacing="0" class="nowraplinks collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit" id="collapsibleTable0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div style="font-size:110%"><a href="https://wikipedia.hk.wjbk.site/baike-%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6" title="计算机科学">计算机科学</a>中的<a href="https://wikipedia.hk.wjbk.site/baike-%E6%A0%91_(%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84)" title="树 (数据结构)">树</a></div></th></tr><tr style="height:2px"><td colspan="3"></td></tr><tr><th scope="row" class="navbox-group"><a href="https://wikipedia.hk.wjbk.site/baike-%E4%BA%8C%E5%8F%89%E6%A0%91" title="二叉树">二叉树</a></th><td class="navbox-list navbox-odd hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px"><div style="padding:0em 0.25em"> <ul><li><a href="https://wikipedia.hk.wjbk.site/baike-%E4%BA%8C%E5%85%83%E6%90%9C%E5%B0%8B%E6%A8%B9" title="二叉搜索树">二叉查找树（BST）</a></li> <li><a href="https://wikipedia.hk.wjbk.site/baike-%E7%AC%9B%E5%8D%A1%E5%B0%94%E6%A0%91" title="笛卡尔树">笛卡尔树</a></li> <li><a href="/w/index.php?title=MVP%E6%A0%91&amp;action=edit&amp;redlink=1" class="new" title="MVP树（页面不存在）">MVP树</a></li> <li><span class="ilh-all" data-orig-title="Top tree" data-lang-code="en" data-lang-name="英语" data-foreign-title="Top tree"><span class="ilh-page"><a href="/w/index.php?title=Top_tree&amp;action=edit&amp;redlink=1" class="new" original-title="Top tree（页面不存在）">Top tree</a></span><span class="noprint ilh-comment">（<span class="ilh-lang">英语</span><span class="ilh-colon">：</span><span class="ilh-link"><a href="https://en.wikipedia.org/wiki/Top_tree" class="extiw" title="en:Top tree"><span lang="en" dir="auto">Top tree</span></a></span>）</span></span></li> <li><a href="/w/index.php?title=T%E6%A0%91&amp;action=edit&amp;redlink=1" class="new" title="T树（页面不存在）">T树</a></li></ul> </div></td></tr><tr style="height:2px"><td colspan="3"></td></tr><tr><th scope="row" class="navbox-group"><a href="https://wikipedia.hk.wjbk.site/baike-%E8%87%AA%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%9F%A5%E6%89%BE%E6%A0%91" class="mw-redirect" title="自平衡二叉查找树">自平衡二叉查找树</a></th><td class="navbox-list navbox-even hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px"><div style="padding:0em 0.25em"> <ul><li><a href="https://wikipedia.hk.wjbk.site/baike-AA%E6%A0%91" title="AA树">AA树</a></li> <li><a href="https://wikipedia.hk.wjbk.site/baike-AVL%E6%A0%91" title="AVL树">AVL树</a></li> <li><a href="https://wikipedia.hk.wjbk.site/baike-%E5%B7%A6%E5%80%BE%E7%BA%A2%E9%BB%91%E6%A0%91" title="左倾红黑树">左倾红黑树</a></li> <li><a class="mw-selflink selflink">红黑树</a></li> <li><a href="https://wikipedia.hk.wjbk.site/baike-%E6%9B%BF%E7%BD%AA%E7%BE%8A%E6%A0%91" title="替罪羊树">替罪羊树</a></li> <li><a href="https://wikipedia.hk.wjbk.site/baike-%E4%BC%B8%E5%B1%95%E6%A0%91" title="伸展树">伸展树</a></li> <li><a href="https://wikipedia.hk.wjbk.site/baike-%E6%A0%91%E5%A0%86" title="树堆">树堆</a></li> <li><a href="https://wikipedia.hk.wjbk.site/baike-%E5%8A%A0%E6%9D%83%E5%B9%B3%E8%A1%A1%E6%A0%91" title="加权平衡树">加权平衡树</a></li></ul> </div></td></tr><tr style="height:2px"><td colspan="3"></td></tr><tr><th scope="row" class="navbox-group"><a href="https://wikipedia.hk.wjbk.site/baike-B%E6%A0%91" title="B树">B树</a></th><td class="navbox-list navbox-odd hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px"><div style="padding:0em 0.25em"> <ul><li><a href="https://wikipedia.hk.wjbk.site/baike-B%2B%E6%A0%91" title="B+树">B+树</a></li> <li><a href="/w/index.php?title=B*%E6%A0%91&amp;action=edit&amp;redlink=1" class="new" title="B*树（页面不存在）">B*树</a></li> <li><a href="/w/index.php?title=Bx%E6%A0%91&amp;action=edit&amp;redlink=1" class="new" title="Bx树（页面不存在）">B<small>^x</small>树</a></li> <li><a href="/w/index.php?title=UB%E6%A0%91&amp;action=edit&amp;redlink=1" class="new" title="UB树（页面不存在）">UB树</a></li> <li><a href="https://wikipedia.hk.wjbk.site/baike-2-3%E6%A0%91" title="2-3树">2-3树</a></li> <li><a href="https://wikipedia.hk.wjbk.site/baike-2-3-4%E6%A0%91" title="2-3-4树">2-3-4树</a></li> <li><a href="/w/index.php?title=(a,b)-%E6%A0%91&amp;action=edit&amp;redlink=1" class="new" title="(a,b)-树（页面不存在）">(a,b)-树</a></li> <li><span class="ilh-all" data-orig-title="Dancing tree" data-lang-code="en" data-lang-name="英语" data-foreign-title="Dancing tree"><span class="ilh-page"><a href="/w/index.php?title=Dancing_tree&amp;action=edit&amp;redlink=1" class="new" original-title="Dancing tree（页面不存在）">Dancing tree</a></span><span class="noprint ilh-comment">（<span class="ilh-lang">英语</span><span class="ilh-colon">：</span><span class="ilh-link"><a href="https://en.wikipedia.org/wiki/Dancing_tree" class="extiw" title="en:Dancing tree"><span lang="en" dir="auto">Dancing tree</span></a></span>）</span></span></li> <li><a href="https://wikipedia.hk.wjbk.site/baike-H%E6%A0%91" title="H树">H树</a></li></ul> </div></td></tr><tr style="height:2px"><td colspan="3"></td></tr><tr><th scope="row" class="navbox-group"><a href="https://wikipedia.hk.wjbk.site/baike-%E5%A0%86_(%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84)" class="mw-redirect" title="堆 (数据结构)">堆</a></th><td class="navbox-list navbox-even hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px"><div style="padding:0em 0.25em"> <ul><li><a href="https://wikipedia.hk.wjbk.site/baike-%E4%BA%8C%E5%8F%89%E5%A0%86" title="二叉堆">二叉堆</a></li> <li><a href="https://wikipedia.hk.wjbk.site/baike-%E4%BA