数据结构第四节——二叉树

作者：不正经 | 2024-04-20 07:36:07

踩

数据结构第四节——二叉树

今天开启美妙的二叉树的学习~~~

“树”是我们第一次见到的”非线性”的数据结构。

二叉树：是树上每个节点都只有两个子节点的简单的树。

知识点小汇：

完全二叉树：除了最后一层外全满的二叉树，最后一层从左到右依次排满。（中间不空）
满二叉树：全满的二叉树。（不存在某个节点没有子节点）
满二叉树的节点个数：

$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 );
}
1
2
3
4
5
6
7

用struct 方式储存信息：

用指针储存二叉树：

struct TreeNode {
	int value;
	TreeNode *l,*r,*fa;
};

TreeNode *root; //根
1
2
3
4
5
6

此方式中的基本操作有如下：

新建节点

此处定义了”新建节点函数“ 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
1
2
3
4
5
6
7

根节点初始化

TreeNode *root;
root = new TreeNode(v); // v是根节点
1
2

插入节点

此处定义了一个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后成为其子节点
1
2
3
4
5
6
7
8
9
10
11
12

二叉树的遍历顺序

先序遍历（根左右）
中序遍历（左根右）
后续遍历（左右根）
层级遍历（ 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); //从根开始遍历
1
2
3
4
5
6

2.中序遍历（LDR）

void InOrder ( TreeNode *p ){
    if ( p -> l ) InOrder( p -> l );
    cout << p -> value << endl;
    if ( p -> r ) InOrder( p -> r );
}
InOrder(root);
1
2
3
4
5
6

3.后序遍历（LRD）

void PostOrder ( TreeNode *p ){
    if ( p -> l ) PostOrder( p -> l );
    if ( p -> r ) PostOrder( p -> r );
    cout << p -> value << endl;
}
PostOrder(root);
1
2
3
4
5
6

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（）函数对此二叉树进行层级遍历
1
2
3
4
5
6
7
8
9
10
11
12
13

求每个节点的深度

此处以层级遍历为例（且先序遍历、中序遍历和后序遍历都可以通过类似的方法求得）

在结构体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就得到了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

上述操作可以在遍历后将二叉树中每一个节点的深度（deepth）求得。

由于某些原因，课程进度赶不上了，最近得赶课了。

所以先把例题放放叭，之后再回头来敲，先看课T_T

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/不正经/article/detail/456148