四、数据结构第四节——二叉树
今天开启美妙的二叉树的学习~~~
“树”是我们第一次见到的”非线性”的数据结构。
二叉树:是树上每个节点都只有两个子节点的简单的树。
知识点小汇:
-
完全二叉树:除了最后一层外全满的二叉树,最后一层从左到右依次排满。(中间不空)
-
满二叉树:全满的二叉树。(不存在某个节点没有子节点)
-
满二叉树的节点个数:2^h-1
-
完全二叉树节点个数范围:[ 2^h , 2^h - 1 )
-
完全二叉树的储存:
- 在以数组 [ 1 ] 为 “根” 建立的二叉树中
- 对于数组 [ t ] 位置的 “左、右儿子” 对应的位置应为 [ 2t ] 和 [ 2t + 1 ] ,“父亲” 的节点位置为 [ t / 2 ] .
-
完全二叉树的建立:
void Build ( int t ){ //添加数据,可以用不同方式添加数据;( 取决于UpdateDate()函数的自我定义 ) UpdateDate( t ); //如果子节点存在 Build( t + t ); Build( t + t + 1 ); }
-
用struct 方式储存信息:
用指针储存二叉树:
struct TreeNode { int value; TreeNode *l,*r,*fa; }; TreeNode *root; //根
此方式中的基本操作有如下:
-
新建节点
此处定义了”新建节点函数“ TreeNode(),
调用该函数,新建节点p,且将该节点处的value的值赋成x
struct TreeNode { int value; TreeNode *i,*r,*fa; //自动初始化为NULL TreeNode( int x ) { value = x; } //定义了一个函数TreeNode( int x ) //该函数将该节点的value的值设置为x }; TreeNode *p = new TreeNode(x); //新建的节点处valu的值是x
-
根节点初始化
TreeNode *root; root = new TreeNode(v); // v是根节点
-
插入节点
此处定义了一个inser()函数,使用该函数将新节点 p 插到 fa 的左(或右)边,成为左(或右)儿子,fa 就理所当然的成为了新节点p 的爹(fa)
void insert (TreeNode *fa, TreeNode *p, int flag ){ //flag = 0 插入到左边 //flag = 1 插入到右边 if ( !flag ) { fa -> l = p; }else{ fa -> r = p; } p -> fa = fa; //插入的节点的爹(fa)是 fa } TreeNode *p = new TreeNode(v); //新建一个节点p,并将该节点的value赋值为v insert( fa, p, flag ); //将新节点p插入fa后成为其子节点
-
-
二叉树的遍历顺序
- 先序遍历( 根左右 )
- 中序遍历( 左根右 )
- 后续遍历( 左右根 )
- 层级遍历( BFS序列 )
1.先序遍历(DLR)
void PreOrder ( TreeNode *p ){ cout << p -> value << endl; //先输出根值,在递归左、右儿子 if ( p -> l ) PreOrder( p -> l ); //如果左儿子存在,则对左儿子进行先序遍历 if ( p -> r ) PreOrder( p -> r ); //同上 } PreOrder(root); //从根开始遍历
2.中序遍历(LDR)
void InOrder ( TreeNode *p ){ if ( p -> l ) InOrder( p -> l ); cout << p -> value << endl; if ( p -> r ) InOrder( p -> r ); } InOrder(root);
3.后序遍历(LRD)
void PostOrder ( TreeNode *p ){ if ( p -> l ) PostOrder( p -> l ); if ( p -> r ) PostOrder( p -> r ); cout << p -> value << endl; } PostOrder(root);
4.层级遍历( BFS )
用队列的方式进行层级遍历,先对于同深度的节点进行遍历,在逐层向下。
对于root进行层级遍历,即:
- 将根值放入队首
- 输出,并弹出队首元素
- 若根(队首元素)的左、右儿子存在,则依次将其放入队列
- 一次循环完成。
- 对于新的队列(由左、右儿子组成的队列)的队首元素继续层级遍历
通过上述步骤实现对该二叉树实现层级遍历(逐层遍历)
void BFS( TreeNode *root ){
q[1] = root; //将根放入队首
int front = 1, rear = 1; //由于定义根是从 1 开始的,所以rear = 1;
while ( front <= rear ){ //当队列中还存在元素时
TreeNode *p = q[front]; //每次取出队首元素对其进行处理(每次的根)
front++;//取出队首元素后在队列中将其弹出,等待下次操作
cout << p -> value << endl; //输出取出的根值(队首元素)
if ( p -> l ) q[++rear] = p -> l; //将队首元素的左儿子放入队列
if ( p -> r ) q[++rear] = p -> r; //将队首元素的右儿子防入队列
}
}
BFS(root);//利用定义的BFS()函数对此二叉树进行层级遍历
- 求每个节点的深度
此处以层级遍历为例(且先序遍历、中序遍历和后序遍历都可以通过类似的方法求得)
在结构体TreeNode中定义deepth ——
int deepth
且定义根的深度deepth为 1 ——
root -> depth = 1
TreeNode *q[N];
void BFS( TreeNode *root ){
q[1] = root;
int front = 1, rear = 1;
root -> depth = 1; //定义根(左、右儿子的fa)的深度为 1
while ( front <= rear ){
TreeNode *p = q[front];
//将队首元素取出使用(因为通过指针定义,所以要取出通过指针方式使用)
front++;
//将无用的队首元素弹出
if ( p -> l ) { //如果左儿子存在
p -> l -> deepth = p -> deepth + 1;
//对于每个左儿子,其深度为其爹(fa)的深度 + 1
q[++rear] = p->l; //将左儿子放到队尾
}
if (p->r) { //右儿子同理左儿子
p -> r -> deepth = p -> deepth + 1;
q[++rear] = p->r;
}
}
}
BFS(root);//遍历结束后,二叉树中每一个节点的deepth就得到了
上述操作可以在遍历后将二叉树中每一个节点的深度(deepth)求得。
标签:知识点,遍历,TreeNode,fa,二叉树,数据结构,root,节点 From: https://www.cnblogs.com/XTian258/p/17009265.html由于某些原因,课程进度赶不上了,最近得赶课了。
所以先把例题放放叭,之后再回头来敲,先看课T_T