1.树1.1树的概念与结构树是⼀种⾮线性的数据结构它是由 nn0 个有限结点组成⼀个具有层次关系的集合。把它叫做 树是因为它看起来像⼀棵倒挂的树也就是说它是根朝上⽽叶朝下的。有⼀个特殊的结点称为根结点根结点没有前驱结点。每棵⼦树的根结点有且只有⼀个前驱可以 有 0 个或多个后继。因此树是递归定义的。树形结构中⼦树之间不能有交集否则就不是树形结构非树形结构⼦树是不相交的如果存在相交就是图了除了根结点外每个结点有且仅有⼀个⽗结点前驱节点⼀棵N个结点的树有N-1条边1.2树相关术语⽗结点/双亲结点若⼀个结点含有⼦结点则这个结点称为其⼦结点的⽗结点如上图A是B的⽗ 结点⼦结点/孩⼦结点⼀个结点含有的⼦树的根结点称为该结点的⼦结点如上图B是A的孩⼦结点结点的度⼀个结点有⼏个孩⼦他的度就是多少⽐如A的度为6F的度为2K的度为0树的度⼀棵树中最⼤的结点的度称为树的度如上图树的度为 6叶⼦结点/终端结点度为 0的结点称为叶结点如上图 B、C、H、I... 等结点为叶结点分⽀结点/⾮终端结点度不为 0 的结点如上图 D、E、F、G... 等结点为分⽀结点兄弟结点具有相同⽗结点的结点互称为兄弟结点(亲兄弟)如上图 B、C 是兄弟结点结点的层次从根开始定义起根为第 1 层根的⼦结点为第 2 层以此类推 树的⾼度或深度树中结点的最⼤层次如上图树的⾼度为 4结点的祖先从根到该结点所经分⽀上的所有结点如上图 A 是所有结点的祖先 路径⼀条从树中任意节点出发沿⽗节点-⼦节点连接达到任意节点的序列⽐如A到Q的路径为 A-E-J-QH到Q的路径H-D-A-E-J-Q⼦孙以某结点为根的⼦树中任⼀结点都称为该结点的⼦孙。如上图所有结点都是A的⼦孙森林由 mm0 棵互不相交的树的集合称为森林1.3树的表示孩⼦兄弟表⽰法struct TreeNode { struct Node* child; // 左边开始的第⼀个孩⼦结点 struct Node* brother; // 指向其右边的下⼀个兄弟结点 int data; // 结点中的数据域 };2.二叉树2.1概念与结构⼀棵⼆叉树是结点的⼀个有限集合该集合由⼀个根结点 加上两棵别称为左⼦树和右⼦树的⼆叉树组成或者为空。从上图可以看出⼆叉树具备以下特点1. ⼆叉树不存在度⼤于 2的结点2. ⼆叉树的⼦树有左右之分次序不能颠倒因此⼆叉树是有序树2.2特殊的二叉树2.2.1满二叉树⼀个⼆叉树如果每⼀个层的结点数都达到最⼤值则这个⼆叉树就是满⼆叉树。也就是说如果⼀ 个⼆叉树的层数为 K 且结点总数是2的k次方−1 则它就是满⼆叉树。树的总节点数2^02^12^2.......2^(k-1),等比数列求和2^k-12.2.2完全二叉树1.除了最后一层每层节点个数达到最大2.最后一层节点个数不一定最大3.结点从左到右一次最大满⼆叉树是⼀种特殊的完全⼆叉树。二叉树性质2.3二叉树存储结构2.3.1顺序结构顺序结构存储就是使⽤数组来存储⼀般使⽤数组只适合表⽰完全⼆叉树因为不是完全⼆叉树会有 空间的浪费完全⼆叉树更适合使⽤顺序结构存储。2.3.2链式结构⼆叉树的链式存储结构是指⽤链表来表⽰⼀棵⼆叉树即⽤链来指⽰元素的逻辑关系。通常的⽅法 是链表中每个结点由三个域组成数据域和左右指针域左右指针分别⽤来给出该结点左孩⼦和右孩 ⼦所在的链结点的存储地址。链式结构⼜分为⼆叉链和三叉链