树和二叉树
一.树
树：是N(N≥0)个结点的有限集合，N=0时，称为空树，这是一种特殊情况。在任意一棵非空树中应满足：
- 有且仅有一个特定的称为根的结点。
- 当N>1时，其余结点可分为m(m>0)个互不相交的有限集合T1,T2,…,Tm，其中每一个集合本身又是一棵树，并且称为根结点的子树。
显然树的定义是递归的，是一种递归的数据结构。树作为一种逻辑结构，同时也是一种分层结构，具有以下两个特点：
- 树的根结点没有前驱结点，除根结点之外的所有结点有且仅有一个前驱结点。
- 树中所有结点可以有零个或者多个后继结点。
树适合于表示具有层次结构的数据。
树中的某个结点（除了根结点之外）最多之和上一层的一个结点（其父结点）有直接关系，根结点没有直接上层结点，因此在n个结点的树中最多只有n-1条边。而树中每个结点与其下一层的零个或者多个结点（即其子女结点）有直接关系。
对K来说：根结点A到K的唯一路径上的任意结点，称为K的祖先结点。如结点B是K的祖先节点，K是B的子孙结点。路径上最接近K的结点E称为K的双亲结点，K是E的孩子结点。根A是树中唯一没有双亲的结点。有相同双亲的结点称为兄弟节点，如K和L有相同的双亲结点E，即K和L是兄弟结点。
树中一个结点的子结点个数称为该结点的度，树中结点最大度数称为树的度。如B的度为2，但是D的度为3，所以该树的度为3.
度大于0的结点称为分支结点（又称为非终端结点）；度为0（没有子女结点）的结点称为叶子结点（又称终端结点）。在分支结点中，每个结点的分支数就是该节点的度。
结点的高度，深度和层次。
结点的层次从树根开始定义，根节点为第一层（有些教材将根节点定义为第0层），它的子结点为第2层，以此类推。
结点的深度是从根节点开始自顶向下逐层累加的。
结点的高度是从叶节点开始自底向上逐层累加的。
树的高度
（又称深度）是树中结点的最大层数。
2.有序树和无序树
树中结点的子树从左到右是有次序的，不能交换，这样的树称为有序树。有序树中，一个结点其子结点从左到右顺序出现是有关联的。反之称为无序树。在上图中，如果将子结点的位置互换，则变为一棵不同的树。
路径和路径长度：树中两个结点之间的路径是由这两个节点之间所经过的结点序列构成的，而路径长度是路径上所经过的边的个数。A和K的路径长度为3.路径为B，E。
3.森林
森林是m棵互不相交的树的集合。森林的概念和树的概念十分相近，因为只要把树的根节点删掉之后就变成了森林。反之，只要给n棵独立的树加上一个结点，并且把这n棵树作为该结点的子树，那么森林就变成了树。
4.树的基本性质
- 树中结点数等于所有节点的度数+1.
- 度为m的树中第i层上之多有mi−1个结点(i≥1)
- 高度为h的m叉树至多有mh−1m−1个结点。
- 具有n个结点的m叉树的最小高度为logm(n(m−1)+1)。
二.二叉树的概念
(1)二叉树的编号
UVA679 小球下落 Dropping Balls(二叉树的编号)
1.二叉树和度为2的有序树的区别：
度为2的树至少有3个结点，而二叉树则可以为空；
度为2的有序树的孩子结点的左右次序是相对于另一个孩子结点而言的，如果某个结点只有一个孩子结点，这个孩子结点就无需区别其左右次序，但是二叉树无论孩子数是否为2，均需要确定其左右次序，也就是说二叉树结点次数不是相对于另一个结点而言，而是确定的。
2.满二叉树
树中除了叶子节点，每个节点都有两个子节点
高度为h，由2^h-1个节点构成的二叉树称为满二叉树。
3.完全二叉树：
完全二叉树是由满二叉树而引出来的，若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数(即1~h-1层为一个满二叉树)，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
堆一般都是用完全二叉树来实现的。
4.平衡二叉树：
树的左右子树的高度差不超过1的数，空树也是平衡二叉树的一种。
平衡二叉树，又称AVL树。它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差之差的绝对值不超过1.。
5.二叉树的遍历
先(前)序遍历: 对访问到的每个结点,先访问根结点,然后是左结点,然后是右结点
中序遍历: 对访问到的每个结点,先访问左结点,然后是根结点,然后是右结点
后序遍历: 对访问到的每个结点,先访问左结点,然后是右结点,然后是根结点
先(前)序遍历：1 2 4 5 7 8 3 6
中序遍历：4 2 7 5 8 1 3 6
后序遍历：4 7 8 5 2 6 3 1
层次遍历：1 2 3 4 5 6 7 8
1.先序遍历
(1)递归写法
void PreOrder(BitTree T)
{
if(T!=NULL)
{
cout<<T->val<<" ";
PreOrder(T->l);
PreOrder(T->r);
}
}
(2)先序非递归写法
根据先序遍历的顺序，先访问根结点，然后再访问左子树和右子树。所以，对于任意结点BitTree，第一部分即直接访问根节点，之后在判断左子树是否为空，不为空时即重复上面的步骤，直到其为空。若为空，则需要访问右子树。利用栈的先进后出，每次访问左子树时都把整个节点放到栈里面，左子树访问完了就往上走，判断父节点是否有右子树，有就访问，没有或者访问完毕就继续往上找父节点，直到将树按先序遍历方式全部遍历完毕。
void PreOrder (BitTree T)
{
stack<BitTree>s;
BitTree p = T;
while(p || !s.empty)
{
if(p)
{
cout<<p->val<<" ";
s.push(p);
p = p->l;
}else
{
p = s.top();
p = p->r;
p = p.pop();
}
}
}
中序遍历和后序遍历的非递归方法和先序遍历一样，改一下先后顺序即可
2.中序遍历
void InOrder(BitTree T)
{
if(T!=NULL)
{
InOrder(T->l);
printf("%d\n",T->val);
InOrder(T->r)
}
}
3.后序遍历
void PostOrder(BitTree T)
{
if(T!=NULL)
{
PostOrder(T->l);
PostOrder(T->r);
printf("%d\n",T->val);
}
}
UVA548 树 Tree(通过中序遍历和后续遍历建树)
题意翻译
输入一个二叉树的中序和后序遍历，请你输出一个叶子节点，该叶子节点到根的数值总和最小，且这个叶子是编号最小的那个。 输入： 您的程序将从输入文件中读取两行(直到文件结尾)。第一行是树的中序遍历值序列,第二行是树的后序遍历值序列。所有值将不同，大于零且小于或等于10000.二叉树的节1<=N<=10000。 输出： 对于每个树描述，您应该输出最小值路径的叶节点的值。存在多路径最小的情况下，您应该选择终端叶子节点上具有最小值的那条路径，且输出那个最小值的终端叶子。
输入：
3 2 1 4 5 7 6
3 1 2 5 6 7 4
7 8 11 3 5 16 12 18
8 3 11 7 16 18 12 5
255
255
1
3
255
UVA699 下落的树叶 The Falling Leaves（二叉树的递归遍历建树）
UVA699 下落的树叶 The Falling Leaves（二叉树的递归遍历建树）
UVA839 天平 Not so Mobile(二叉树的递归遍历建树并回答问题）
4.层序遍历
这棵二叉树的层次遍历次序为：A、B、C、D、F、G
每次出队一个元素，就将该元素的子节点加入队列中，直至队列中元素个数为0时，出队的顺序就是该二叉树的层次遍历结果。不懂看这里
void LevelOrder(BitTree T)
{
queue q;
if (T == NULL){return;}
q.push(T);
while (!q.empty())
{
BitTree p=q.front();
cout<<p.val;
q.pop();
if(p.l)
q.push(p.l);
if(p.r)
q.push(p.r);
}
}
以上四种种遍历算法中递归遍历左子树和右子树的顺序都是固定的，只是访问根节点的顺序不同。不管采用何种遍历方法，每个结点都是访问一次，所以时间复杂度就是O(n)。
在递归遍历中，递归工作栈的深度恰巧是树的深度，所以在最坏的情况下，二叉树是有n个结点且深度为n的单支树，递归遍历算法的时间复杂度是O(n)。
UVA122 树的层次遍历 Trees on the level（两种方法详解）
UVA122 树的层次遍历 Trees on the level（两种方法详解）
6.二叉树的五个性质
- ａ＾ｂ—— a的b的次方 （计算机常用，无需多言）
- int_UP（）—— 向上取整（即去掉浮点数的小数部分，然后将整数部分加1）
- int_DOWN（）—— 向下取整（即去掉浮点数的小数部分，只留整数部分）
- log(a,b) —— 表示以a为底取b的对数
性质的内容
二叉树具有以下五个性质：
- 在二叉树的第ｉ（ｉ>=１）层最多有２＾(ｉ - １)个结点。
- 深度为k(k>=0)的二叉树最少有k个结点，最多有２＾ｋ－１个结点。
- 对于任一棵非空二叉树，若其叶结点数为n0，度为2的非叶结点数为n2，则ｎ0 = ｎ2 ＋１。
- 具有n个结点的完全二叉树的深度为int_UP（log(2，ｎ+1)）。
- 如果将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号１，２，３，．．．．．．，ｎ，然后按此结点编号将树中各结点顺序的存放于一个一维数组，并简称编号为i的结点为结点i（ ｉ>=１ && ｉ<=ｎ）,则有以下关系：
（1）若 ｉ= 1，则结点i为根，无父结点；若 ｉ> 1，则结点 i 的父结点为结点int_DOWN（ｉ / ２）;
（2）若 ２＊ｉ <= ｎ，则结点 ｉ 的左子女为结点 ２＊ｉ；
（3）若２＊ｉ＜＝ｎ，则结点ｉ的右子女为结点２＊ｉ＋１；
（4）若结点编号ｉ为奇数，且ｉ！＝１，它处于右兄弟位置，则它的左兄弟为结点ｉ－１；
（5）若结点编号ｉ为偶数，且ｉ！＝ｎ，它处于左兄弟位置，则它的右兄弟为结点ｉ＋１；
（6）结点ｉ所在的层次为 int_DOWN（log（2，ｉ））＋１。
（上述性质来源及证明）
//不管是左子树还是右子树，它们的父节点都是P/2;
三.求树的重心
四.求树的总深度和（BFS遍历整棵树）
牛客 Tree(最小深度总和)（两种方法求重心）难度⭐⭐⭐
题目链接
五.二叉排序树
六.非二叉树—四分树
注：如果您通过本文,有(qi)用(guai)的知识增加了，请您点个赞再离开,如果不嫌弃的话,点个关注再走吧 ! 当然，也欢迎在讨论区指出此文的不足处，作者会及时对文章加以修正 !
京公网安备 11010502036488号