数据结构--二叉树知识讲解

一、树1.**树的概念与结构 **树是一种非线性的数据结构它是由n(n ≥ 0)个有限结点组成的、具有层次关系的集合。当n 0时称为空树。当n 0时有且仅有一个特殊结点称为根结点Root。除根结点外其余结点可分为m(m ≥ 0)个互不相交的有限集合每个集合本身又是一棵树称为根的子树⼦树是不相交的除了根结点外每个结点有且仅有⼀个⽗结点⼀棵N个结点的树有N-1条边2.树的相关术语父节点/双亲结点若一个结点含有子结点则这个结点称为其子结点的父节点如A 是 B、C、D、E、F、G 的父结点子结点/孩子结点一个结点含有子树的根节点称为该结点的子结点如B、C、D、E、F、G 是 A 的孩子结点兄弟结点:具有相同父结点的结点互称为兄弟结点亲兄弟,如B、C、D、E、F、G 互为兄弟父结点都是 A结点的度一个结点拥有的子结点数量就是该结点的度如A 的度 6有 6 个孩子B/C/D/E/F/G树的度一棵树中所有结点的度的最大值就是树的度如A 的度是 6是全树最大的因此这棵树的度 6叶子结点 / 终端结点度为 0 的结点没有子结点的结点如B、C、H、I、K、L、M、N、P、Q共 10 个叶子结点分支结点 / 非终端结点度不为 0 的结点有子结点的结点如A、D、E、F、G、J共 6 个分支结点结点的层次从根结点开始计数根为第 1 层根的子结点为第 2 层以此类推如第 1 层A第 2 层B、C、D、E、F、G第 3 层H、I、J、K、L、M、N第 4 层P、Q树的高度 / 深度树中结点的最大层次数如最大层次是 4P、Q 在第 4 层因此树的高度 4结点的祖先从根结点到该结点路径上经过的所有结点都是该结点的祖先如Q 的祖先A、E、JH 的祖先A、D子孙结点以某结点为根的子树中任意结点都称为该结点的子孙如E 的子孙I、J、P、Q路径从树中任意结点出发沿「父结点→子结点」的连接到达另一结点的结点序列如A 到 Q 的路径A → E → J → Q森林由m(m0)棵互不相交的树组成的集合称为森林简单来说就是把一棵树的根结点删掉剩下的子树集合就是一个森林比如删掉 A剩下 B、C、D 为根的子树就是一个森林3. 树的表示方法3.1 双亲表示法核心思想用数组存储所有节点每个节点只记录自己的值和父节点的下标优点查找父节点极快O (1)缺点查找子节点需要遍历整个数组适用只需要快速找父节点的场景双亲表示法结点结构// 双亲表示法 节点结构typedefstructPTNode{// 节点数据intdata;// 父节点在数组中的下标根节点为 -1intparent;}PTNode;3.2 孩子表示法核心思想用数组存所有节点每个节点带一个链表存储所有子节点的下标优点查找子节点极快缺点查找父节点需要遍历适用文件目录、多叉树孩子链表的节点// 孩子链表的节点存子节点下标typedefstructChildNode{intindex;// 子节点在数组中的下标structChildNode*next;// 下一个子节点}ChildNode;3.3 双亲孩子表示法核心思想孩子表示法和每个节点记录父节点下标优点找父、找子都极快缺点结构稍复杂适用需要双向查找的树双亲孩子表示法的结点typedefstructPCTNode{intdata;intparent;// 父节点下标ChildNode*first;}PCTNode;3.4 孩子兄弟表示法核心思想任意树转化为二叉树每个节点只存两个指针firstChild指向第一个子节点nextSibling指向右边的兄弟节点优点所有树都能转二叉树代码极简缺点理解稍难适用二叉树、红黑树、B 树、文件系统结点结构typedefstructCSNode{intdata;structCSNode*firstChild;// 第一个子节点structCSNode*nextSibling;// 右兄弟节点}CSNode3.5 二叉树专用表示法二叉树是度最多为 2的树结构最简单、用途最广结点结构// 二叉树节点typedefstructBiTNode{intdata;structBiTNode*lchild,*rchild;// 左、右孩子}BiTNode;| | |表示法存储结构优点缺点适用场景双亲表示法数组找父极快找子慢并查集孩子表示法数组 链表找子极快找父慢文件目录双亲孩子数组 链表父子都快结构复杂通用树孩子兄弟纯链表万能转二叉树理解稍难所有树、二叉树、红黑树二、二叉树1.概念与结构定义二叉树是每个节点最多有两个子节点的树形结构两个子节点分别称为左孩子left child右孩子right child特点子树有左右之分顺序不能随意交换可以是空树 ,每个节点度≤ 22. 特殊二叉树2.1 满二叉树每一层节点都达到最大值所有叶子结点都在最底层加粗样式高度h节点总数 2^h -12.2 完全二叉树除最后一层外其他层节点都满最后一层节点靠左连续排列3.二叉树性质根据满⼆叉树的特点可知若规定根结点的层数为1则⼀棵⾮空⼆叉树的第i层上最多有2i−1个结点若规定根结点的层数为1则深度为 h 的⼆叉树的最⼤结点数是2h − 1若规定根结点的层数为1具有 n 个结点的满⼆叉树的深度h log(n1)( log以2为底 n1 为对数)4.二叉树的存储结构⼆叉树⼀般可以使⽤两种结构存储⼀种顺序结构⼀种链式结构4.1 顺序结构二叉树的顺序存储结构是指采用数组对二叉树进行存储。该存储方式仅适用于完全二叉树若用于存储非完全二叉树会因数组中产生大量空闲位置导致存储空间严重浪费因此完全二叉树是最适合采用顺序存储的二叉树类型。在实际应用中堆数据结构中的堆 通常采用数组实现顺序存储。需要明确区分数据结构中的堆是一种特殊的完全二叉树结构与操作系统虚拟进程地址空间中用于动态内存分配的堆区是两个完全不同的概念二者不可混淆。4.2 链式结构二叉树的链式存储结构是通过链表来表示一棵二叉树利用链表指针反映节点之间的逻辑层次关系。通常情况下链表中的每个节点包含三个域一个数据域和两个指针域。其中数据域用于存储节点数据两个指针域分别用于存储指向该节点左孩子和右孩子的节点地址。三、顺序结构二叉树–堆⼀般堆使⽤顺序结构的数组来存储数据堆是⼀种特殊的⼆叉树具有⼆叉树的特性的同时还具备其他的特性1.堆的基本概念堆是一种完全二叉树结构的优先队列不是内存里的堆内存2.堆必须同时满足两个条件结构条件是一棵完全二叉树堆序性质父节点与子节点满足大小关系大根堆 / 小根堆3.堆的两种类型3.1 大根堆最大堆 Max Heap根节点值最大任意父节点 ≥ 左右孩子节点从上到下递减3.2 小根堆最小堆 Min Heap根节点值最小任意父节点 ≤ 左右孩子节点从上到下递增注意堆不要求左右子树有序只要求父子有序4.二叉树的性质对于具有n个结点的完全⼆叉树如果按照从上⾄下从左⾄右的数组顺序对所有结点从0开始编号则对于序号为i的结点有若i0i位置结点的双亲序号(i-1)/2i0i为根结点编号⽆双亲结点若2i1n左孩⼦序号2i12i1n否则⽆左孩⼦若2i2n右孩⼦序号2i22i2n否则⽆右孩⼦5.堆的实现堆四、链式二叉树的实现链式二叉树