树与二叉树原理解析
14.3 树与二叉树原理解析
14.3.1 树：
14.3.1.1 树的定义：
14.3.1.2 树的相关概念：
-
树作为一种逻辑结构，同时也是以一种分层结构，具有以下两个特点：
（1）：树的根结点没有前驱，除根结点外的所有结点有且只有一个前驱；
（2）：树中的所有结点可以有零个或多个后继。----与二叉树的区别所在
14.3.1.3 树的结构：
- !!!：深度：代表该树的层数
- !!!：度：代表某个结点的紧跟后继结点的个数
14.3.2 二叉树
14.3.2.1 二叉树的定义：
14.3.2.2 二叉树的结构：
14.3.2.2.1满二叉树：
除了叶子结点，每个结点的度都为2；
14.3.2.2.2完全二叉树：
满二叉树的叶子结点按次序未排满！！！
14.3.2.3 二叉树的存储结构：
14.3.2.3.1 二叉树的顺序存储：
14.3.2.3.2 二叉树的链式存储：
14.3.2.3.2.1 示意图：
14.3.2.3.2.2 树结点数据结构：
typedef char BiElemType;
typedef struct BiTNode{
BiElemType data;
struct BiTNode *lchild;
struct BiTNode *rchild;
}BiTNode, *BiTree;
14.4 二叉树层次建树的实战
14.4.1 流程图
| 指针 | 作用 |
|---|---|
BiTree tree | 唯一的根结点 |
BiTree pnew | 新建的树结点 |
ptag_t phead | 辅助队列的头指针 |
ptag_t ptail | 辅助队列的尾指针 |
ptag_t pcur | 指向要进入树的父亲元素 |
ptag_t listpnew | 新建的队列结点 |
14.4.2 示意图
Step_01：
pcur不动
Step_02：
pcur不动
Step_03：
pcur指向下一个元素
Step_04：
pcur不动
Step_05：
pcur指向下一个元素
14.4.3 代码
!!!calloc()可以直接初始化，赋值为0.
==!!!==一开始的根结点一定要赋值为NULL！！！.
//function.h
//树结点的数据结构
typedef char BiElemType;
typedef struct BiTNode{
BiElemType data;
struct BiTNode *lchild;//左孩子结点
struct BiTNode *rchild;//右孩子结点
}BiTNode, *BiTree;
//辅助队列
typedef struct tag{
BiTree p;//存放树结点的地址
struct tag *pnext;//下一个作为父结点的结点
}tag_t, *ptag_t;
//main.cpp
#include "function.h"
int main() {
char c;
BiTree tree = NULL;//根结点
BiTree pnew;//新的树结点
ptag_t phead = NULL, ptail = NULL, pcur, listpnew;//listpnew新的队列结点
//开始读取元素
while (scanf("%c", &c)){
//如果输入回车，则读取结束
if(c == '\n'){
break;
}
//为新的树结点分配空间
pnew = (BiTree) calloc(1, sizeof(BiTNode));//calloc申请的空间大小是两个参数直接相乘，并且对空间进行初始化，赋值为0
//为新的队列结点分配空间
listpnew = (ptag_t) calloc(1, sizeof(tag_t));
pnew->data = c;
listpnew->p = pnew;
//如果是第一个结点，则为根结点
if(!tree){
tree = pnew;//tree指向根结点
phead = listpnew;//第一个结点即是队列头，也是队列尾
ptail = listpnew;
pcur = listpnew;//要指向要进入树的父亲元素
}else{
//让元素先进入队列
ptail->pnext = listpnew;
ptail = listpnew;
if(!pcur->p->lchild){
pcur->p->lchild = pnew;
}else if(!pcur->p->rchild){
pcur->p->rchild = pnew;
pcur = pcur->pnext;
}
}
}
return 0;
}
14.5 二叉树的前中后序实战
14.5.1 流程图
14.5.2 示意图
14.5.3 代码
//function.h
//定义树结构体
typedef char BiElemType;
typedef struct BiTNode{
BiElemType data;
struct BiTNode *lchild;
struct BiTNode *rchild;
}BiTNode, *BiTree;
//定义辅助队列的结构体
typedef struct tag{
BiTree p;
struct tag *pnext;
}tag_t, *ptag_t;
//main.cpp
#include "function.h"
void InitTree(BiTree &tree){
char c;
BiTree pnew;//新建的树结点
ptag_t phead = NULL, ptail = NULL, pcur, listpnew;
while(scanf("%c", &c)){
//结束标志
if(c == '\n'){
break;
}
pnew = (BiTree) calloc(1, sizeof(BiTNode));
listpnew = (ptag_t) calloc(1, sizeof(tag_t));
pnew->data = c;
listpnew->p = pnew;
if(!tree){
tree = pnew;
phead = listpnew;
ptail = listpnew;
pcur = listpnew;
}else{
//先把元素放入队列中
ptail->pnext = listpnew;
ptail = listpnew;
if(!pcur->p->lchild){
pcur->p->lchild = pnew;
}else if(!pcur->p->rchild){
pcur->p->rchild = pnew;
pcur = pcur->pnext;
}
}
}
}
void PreOrder(BiTree p){
if(p){
printf("%c", p->data);//putchar函数
PreOrder(p->lchild);
PreOrder(p->rchild);
}
}
void InOrder(BiTree p){
if(p){
InOrder(p->lchild);
printf("%c", p->data);
InOrder(p->rchild);
}
}
void PostOrder(BiTree p){
if(p){
PostOrder(p->lchild);
PostOrder(p->rchild);
printf("%c", p->data);
}
}
int main() {
BiTree tree = NULL;
InitTree(tree);
printf("--------------PreOder is-------------\n");
PreOrder(tree);
printf("\n");
printf("--------------InOder is-------------\n");
InOrder(tree);
printf("\n");
printf("--------------PostOder is-------------\n");
PostOrder(tree);
printf("\n");
return 0;
}
14.6 二叉树的层序遍历实战
14.6.1 流程图
14.6.2 示意图
Step_01:
根结点入队
Step_02:
第一次循环:
- 把a出队
- 将b和c入队
Step_03:
第二次循环：
- 把b出队
- 将d和e入队
Step_04:
第三次循环：
- 把c出队
Step_05:
第四次循环：
- 把d出队
Step_06:
第五次循环:
- 把e出队
14.6.3 代码
!!!:cpp文件之间相互调用函数，函数的声明要在头文件中指示出！！！
!!!:==一定要区别于=号呀！！！
//function.h
typedef char BiElemType;
//树结点的结构体
typedef struct BiTNode{
BiElemType data;
struct BiTNode *lchild;
struct BiTNode *rchild;
}BiTNode, *BiTree;
//层次建树时的辅助队列
typedef struct tag{
BiTree p_build;
struct tag *pnext_build;
}tag_t, *ptag_t;
//层次遍历树时的辅助队列
typedef struct LNode{
BiTree p_print;
struct LNode *pnext_print;
}LNode, *LinkList;
typedef struct LinkQueue{
LinkList front, rear;
}LinkQueue;
void InitBiTree(BiTree &p);
void PreOrder(BiTree p);
void InOrder(BiTree p);
void PostOrder(BiTree p);
void LeverOrder(BiTree p);
void InitLinkQueue(LinkQueue &q);
bool IsEmpty(LinkQueue q);
void EnQueue(LinkQueue &q, BiTree c);
void DeQueue(LinkQueue &q, BiTree &c);
//LinkQueue.cpp
#include "function.h"
void InitLinkQueue(LinkQueue &q){
q.front = q.rear = (LinkList) malloc(sizeof (LNode));
q.front->pnext_print = NULL;//防止没有元素
}
bool IsEmpty(LinkQueue q){
if(q.front == q.rear){
return true;
}else{
return false;
}
}
void EnQueue(LinkQueue &q, BiTree c){
LinkList p = (LinkList) malloc(sizeof(LNode));
p->p_print = c;
p->pnext_print = NULL;
q.rear->pnext_print = p;
q.rear = p;
}
void DeQueue(LinkQueue &q, BiTree &c){
if(IsEmpty(q)){
return;
}
LinkList s;
s = q.front->pnext_print;
c = s->p_print;
q.front->pnext_print = s->pnext_print;
//如果恰巧删掉的时最后一个结点
if(q.rear == s){
q.rear = q.front;
}
free(s);
}
//BiTree.cpp
#include "function.h"
void InitBiTree(BiTree &p){
char c;
BiTree pnew;//表示新的树结点
ptag_t listpnew;//队列新的结点
ptag_t phead = NULL, ptail = NULL, pcur;
while(scanf("%c", &c)){
//循环结束条件
if(c == '\n'){
break;
}
pnew = (BiTree) calloc(1, sizeof (BiTNode));
listpnew = (ptag_t) calloc(1, sizeof(tag_t));
pnew->data = c;
listpnew->p_build = pnew;
if(!p){
p = pnew;
phead = listpnew;
ptail = listpnew;
pcur = listpnew;
}else{
//将新的队列放入队列
ptail->pnext_build = listpnew;
ptail = listpnew;
if(!pcur->p_build->lchild){
pcur->p_build->lchild = pnew;
}else if(!pcur->p_build->rchild){
pcur->p_build->rchild = pnew;
pcur = pcur->pnext_build;
}
}
}
}
void PreOrder(BiTree p){
if(p){
printf("%c", p->data);
PreOrder(p->lchild);
PreOrder(p->rchild);
}
}
void InOrder(BiTree p){
if(p){
InOrder(p->lchild);
printf("%c", p->data);
InOrder(p->rchild);
}
}
void PostOrder(BiTree p){
if(p){
PostOrder(p->lchild);
PostOrder(p->rchild);
printf("%c", p->data);
}
}
void LeverOrder(BiTree p){
LinkQueue q;
InitLinkQueue(q);
EnQueue(q, p);
BiTree s;
while(!IsEmpty(q)){
DeQueue(q, s);
printf("%c", s->data);
if(s->lchild){
EnQueue(q, s->lchild);
}
if(s->rchild){
EnQueue(q, s->rchild);
}
}
}
//main.cpp
#include "function.h"
//#include "BiTree.cpp" 要在头文件中声明
int main() {
BiTree tree = NULL;
InitBiTree(tree);
printf("--------------PreOrder is-------------\n");
PreOrder(tree);
printf("\n");
printf("--------------InOrder is-------------\n");
InOrder(tree);
printf("\n");
printf("--------------PostOrder is-------------\n");
PostOrder(tree);
printf("\n");
printf("--------------LeverOrder is-------------\n");
LeverOrder(tree);
printf("\n");
return 0;
}
14.7 2014年41题真题实战
14.7.1 题目简介：
14.7.2 题目解析:
14.7.3 代码：
原文地址：https://blog.csdn.net/m0_58321769/article/details/145269703
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！