第五章 树和二叉树
一、树这一章节主要总结有以下几个知识点,以及一些需要注意的点:
1、树的结构体,一般有数据域,左右孩子域,顺序结构(一般适用于完全二叉树,避免过多空间浪费)
SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。typedef struct
{
TElemType data;
int lch;
int rch;
}BiTNode; //定义顺序存储结构
typedef sttuct BiTNode
{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree; //定义链式存储结构(二叉链表形式)
2、通过输入的信息来建立树,并找出根结点
顺序结构里:所给题目,没有孩子就会用‘-’表示,时
1、输入左右孩子时不能直接
cin>>t[i].lch;
cin>>t[i].rch; //这样是错的,因为lch是int类型,而‘-’是char 类型
而是要先
char x,y;
cin>>x>>y
if(x!='-')
{
t[i].lch = x-'0'; //将char型的数字改为int型的数值
check[t[i].lch] = true;
}
2、记得将x/y等于'-'的t[i].lch/rch元素赋值为-1,方便后面的表示
3、二叉树的遍历:先中后,三种顺序,运用递归的方法;层序,利用队列的知识
#include <queue> queue <int> queue1; //队列创建
//查了一些队列的相关操作
1、弹出队列:queue1.pop();
2、访问队尾元素:queue1.back();
3、判断队列空:queue1.empty();
(当队列空时,返回true)
4、查看队列中的元素个数:queue1.size()
5、返回队首元素:queue1.front()
利用队列实现层序遍历简单说明:
就是在先根结点入队,然后出队,然后其左右孩子入队,再依次出队,其中每个结点每次出队时就将其左右孩子入队。当队列为空时,整棵树层序遍历完毕。
下图为简单演示
(图片摘自博客 https://blog.csdn.net/qq_29542611/article/details/79372678)
层序遍历代码如下:
void level(node t[], int x) //层次遍历 { int p; //等会pop出的元素 queue <int> q; q.push(x); //x是根结点的索引(所在下标) //入队 while(!q.empty()) { p = q.front(); //p赋值为队首元素 q.pop(); //出队 if(p!=-1) //该结点非空 { q.push(t[p].lch); q.push(t[p].rch); } } }
但是刚才重新看代码的时候发现 if(p!=-1){ q.push(t[p].lch); q.push(t[p].rch); } 这一步我好像不太理解,这一步是想要判断其左右孩子是否为空,不是应该如下代码所示吗:
if (t[p].lch != -1) q.push(t[p].lch); if (t[p].rch!= -1) q.push(t[p].rch);
二、下一章将学习图,做出几个小要求:
1、做好提前预习,把书本的内容认真看一遍
2、老师当天讲完编程的内容就当天复习并及时按编程思想自己重新写一次代码

更多精彩