域名备案怎么关闭网站,怎么一键打开wordpress,北京住房建设部网站首页,学习网站建设的书一、⼆叉树的定义
⼆叉树是⼀种特殊的树型结构#xff0c;它的特点是每个结点⾄多只有2棵⼦树#xff08;即⼆叉树中不存在度⼤于2的结点#xff09;#xff0c;并且⼆叉树的⼦树有左右之分#xff0c;其次序不能任意颠倒。 ⼆叉的意思是这种树的每⼀个结点最多只有两个孩…一、⼆叉树的定义
⼆叉树是⼀种特殊的树型结构它的特点是每个结点⾄多只有2棵⼦树即⼆叉树中不存在度⼤于2的结点并且⼆叉树的⼦树有左右之分其次序不能任意颠倒。 ⼆叉的意思是这种树的每⼀个结点最多只有两个孩⼦结点。注意这⾥是最多有两个孩⼦也可能没有孩⼦或者是只有⼀个孩⼦。 注意⼆叉树结点的两个孩⼦⼀个被称为左孩⼦⼀个被称为右孩⼦。其顺序是固定的就像⼈的左⼿和右⼿不能颠倒混淆。
满⼆叉树 ⼀棵⼆叉树的所有⾮叶⼦节点都存在左右孩⼦并且所有叶⼦节点都在同⼀层上那么这棵树就称为满⼆叉树。 完全⼆叉树 对⼀棵树有n 个结点的⼆叉树按层序编号所有的结点的编号从1 ∼ n。如果这棵树所有结点和同 样深度的满⼆叉树的编号为从1 ∼ n 的结点位置相同则这棵⼆叉树为完全⼆叉树。说⽩了就是在满⼆叉树的基础上在最后⼀层的叶⼦结点上从右往左依次删除若⼲个结点剩下的就是⼀棵完全⼆叉树。 二、⼆叉树的存储 在《树》的章节中已经学过树的存储⼆叉树也是树也是可以⽤vector数组或者链式前向星来存储。仅需在存储的过程中标记谁是左孩⼦谁是右孩⼦即可。 • ⽐如⽤vector数组存储时可以先尾插左孩⼦再尾插右孩⼦ • ⽤链式前向星存储时可以先头插左孩⼦再头插右孩⼦。只不过这样存储下来遍历孩⼦的时候先遇到的是右孩⼦这点需要注意。 但是由于⼆叉树结构的特殊性我们除了⽤上述两种⽅式来存储还可以⽤符合⼆叉树结构特性的⽅式分别是顺序存储和链式存储。
主要讲一下链式存储
因此我们可以创建两个数组l[N]r[N] 其中l[i] 表⽰结点号为 的结点的左孩⼦编号 r[i] 表⽰结点号为 的结点的右孩⼦编号。这样就可以把⼆叉树存储起来。
#include iostream
using namespace std;
const int N 1e6 10;
int n;
int l[N], r[N];
int main()
{cin n;for(int i 1; i n; i){// 存下 i 号结点的左右孩⼦ cin l[i] r[i];}return 0;
}
三、⼆叉树的遍历
深度优先遍历
不同于常规树的深度优先遍历⼆叉树因其独特的性质可以划分成三种深度优先遍历先序遍历中 序遍历和后序遍历。其中三种遍历⽅式的不同在于处理根节点的时机。 对于⼀棵⼆叉树⽽⾔整体可以划分成三部分根节点左⼦树右⼦树 • 先序遍历的顺序为根左右 • 中序遍历的顺序为左根右 • 后序遍历的顺序为左右根。
#include iostream
using namespace std;
const int N 1e6 10;
int n;
int l[N], r[N];
void dfs1(int p)
{if(p 0) return;// 先处理根节点 cout p ;// 左⼦树 dfs1(l[p]);// 右⼦树 dfs1(r[p]);
}
void dfs2(int p)
{if(p 0) return;dfs2(l[p]);cout p ;dfs2(r[p]);
}
void dfs3(int p)
{if(p 0) return;dfs3(l[p]);dfs3(r[p]);cout p ;
}
int main()
{cin n;for(int i 1; i n; i){cin l[i] r[i];}dfs1(1); // 先序遍历 cout endl;dfs2(1); // 中序遍历 cout endl;dfs3(1); // 后序遍历 cout endl;return 0;
}
宽度优先遍历
#include iostream
#include queue
using namespace std;
const int N 300;
int n;
int l[N], r[N];
void bfs()
{queueint q;q.push(1);while(q.size()){auto p q.front(); q.pop();cout p ;// 左右孩⼦⼊队 if(l[p]) q.push(l[p]);if(r[p]) q.push(r[p]);}cout endl;
}
int main()
{cin n;for(int i 1; i n; i){cin l[i] r[i];}bfs();return 0;
}
