(六)数据结构--二叉树-创新互联
1、树
网页标题：(六)数据结构--二叉树-创新互联
当前网址：http://mswzjz.cn/article/djjcgi.html
定义：树是n(n≥0)个节点的有限集，当n=0时，称为空数
非空树要满足：
- 有且仅有一个特定的称为根的结点。
- 当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1，T2，…，Tm,其中每个集合本事又是一颗树，并且称为根的子树。
特点：树作为一种逻辑结构，同时也是一种分层结构
- 树的跟结点没有前驱，除根结点外的所有结点有且仅有一个前驱
- 所有结点可以有零个或者多个后继
A是第一层，B/C/D是第二层，E/F/G/H/I/J是第三层，K/L/M第四层
2、二叉树特点：每个树节点最多只有两颗子树(不存在度大于2的结点)，且二叉树的子树有左右之分，次序不能随意颠倒
- 满二叉树每层结点个数:2^(n-1)；
- 如果k结点去掉，就不是完全二叉树了
说明：图中的.表示该点没有内容，个人笔记习惯
顺序存储
一层一层逐一放置，如果该节点不存在用0补齐
| 1 | 2 | 3 | 0 | 4 | 0 | 5 | 0 | 0 | 6 | 0 |
|---|
链式存储
数据结构：
typedef char BiElemType;
typedef struct BiTNode{BiElemType c;
struct BiTNode *lchild;
struct BiTNode *rchild;
}BiTNode, *BiTree;树中任何一个结点都是一个结构体，他的空间是通过malloc申请出来
向二叉树中输入a,b,c,d,e,f,g,h,i,j十个字母
实现效果：如图
- 需要使用的辅助队列
步骤： 1.把`a`放进辅助队列，此时pcur始终指向要放子节点的结点上； 2.把`b`放进辅助队列，判断pcur所指的结点a的左孩子是不是为NULL，如果左孩子为NULL放在左边； 3.把`c`放进辅助队列，判断pcur所指的结点a的右孩子是不是为NULL，如果右孩子为NULL放在右边； 4.当a的左右孩子都不为NULL时，pcur后移一个calloc申请的空间大小是两个想乘，对申请的空间初始化，赋值为0
代码实现：
#ifndef TREE_FUNCTION_H
#define TREE_FUNCTION_H
#include#includetypedef char BiElemType;
// 二叉树结构体
typedef struct BiTNode{BiElemType c;
struct BiTNode *lchild;
struct BiTNode *rchild;
} BiTNode, *BiTree;
// 辅助队列结构体
typedef struct tag{BiTree p; //树的某一个结点的地址值
struct tag *pnext;
} tag_t, *ptag_t;
#endif //TREE_FUNCTION_H #include "function.h"
int main() {//1.用来指向新申请的树节点
BiTree pnew;
BiTree tree=NULL; //tree 指向树根用来代表树
BiElemType c;
// 2.辅助队列
ptag_t phead=NULL,ptail=NULL,list_pnew=NULL,pcur=NULL;
// abcdefghij
while (scanf("%c",&c)){if (c=='\n'){break; //读到换行就结束
}
pnew=(BiTree)calloc(1,sizeof(BiTNode));
pnew->c=c;
// 给队列结点申请空间
list_pnew=(ptag_t)calloc(1,sizeof(tag_t));
list_pnew->p=pnew;
// 判断是否是树的第一个结点
if (tree==NULL) {tree = pnew; // tree指向树的根节点
phead = list_pnew; // 第一个结点即是队列头，也是队列尾
ptail = list_pnew;
pcur = list_pnew; // 指向进入树的父亲元素
continue;
} else {// 先入队列
ptail->pnext=list_pnew;
ptail=list_pnew;
// 把结点放入树中
if(pcur->p->lchild==NULL){pcur->p->lchild=pnew;
} else if(pcur->p->rchild==NULL){pcur->p->rchild=pnew; //当前左右结点都有了，pcur后移一个
pcur=pcur->pnext;
}
}
}
return 0;
}每一个遍历都必须和自己的父亲挨着
前序遍历(preOrder)–深度优先遍历先打印自身，再打印左子树，再打印右子树
前序遍历打印结果：abdhiejcfg
void preOrder(BiTree Tree){if (Tree!=NULL){printf("%c",Tree->c); //打印
preOrder(Tree->lchild);
preOrder(Tree->rchild);
}
}先打印左子树，再打印自身，再打印右子树bacdbeac…
中序遍历打印结果：hdibjeafcg
void inOrder(BiTree Tree){if (Tree!=NULL){inOrder(Tree->lchild);
printf("%c",Tree->c); //打印
inOrder(Tree->rchild);
}
}先打印左子树，再打印右子树，在打印自身
后序遍历打印结果：hidjebfgca
void postOrder(BiTree Tree){if (Tree!=NULL){postOrder(Tree->lchild);
postOrder(Tree->rchild);
printf("%c",Tree->c); //打印
}
}层序遍历打印结果：abcdefghij
// 层序遍历--广度优先遍历
void levelOrder(BiTree Tree){// 定义一个队列
LinkQueue Q;
// 初始化
initQueue(Q);
BiTree p;
// 入队
EnQueue(Q,Tree);
while (!isEmpty(Q)){// 判断队列是否为空
DeQueue(Q,p); // 出队当前结点并打印
putchar(p->c);
if (p->lchild!=NULL){EnQueue(Q,p->lchild); // 入队左孩子
}
if (p->rchild!=NULL){EnQueue(Q,p->rchild); // 入队右孩子
}
}
}结合上一节“(五)数据结构–队列”的代码实现。
结合辅助队列，
新建queue.cpp文件
#include "function.h"
// 队列初始化使用带头结点的链表来标识
void initQueue(LinkQueue &Q){Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode)); //链表头和链表尾指向同一个结点
Q.front->next=NULL; // 头结点的next指针为NULL
}
// 判断队列是否为空
bool isEmpty(LinkQueue Q){if (Q.front==Q.rear){return true;
} else{return false;
}
}
// 入队
void EnQueue(LinkQueue &Q, ElemType value){LinkNode *p=(LinkNode*)malloc(sizeof(LinkNode));
p->data=value;
p->next=NULL; //要让next为NULL
Q.rear->next=p; //尾指针的next指向p,从尾部入队;
Q.rear=p; //rear指向新的尾部
}
// 出队
bool DeQueue(LinkQueue &Q, ElemType &value){if (isEmpty(Q)){return false; //队列为空
}
LinkNode *q=Q.front->next; //拿到第一个结点，存入q
value=q->data;
Q.front->next=q->next;
// 链表只剩余一个结点时，被删除后要改变rear
if (Q.rear==q){Q.rear=Q.front;
}
free(q); // 断链
return true;
}修改function.h中的代码
#ifndef TREE_FUNCTION_H
#define TREE_FUNCTION_H
#include#includetypedef char BiElemType;
// 二叉树结构体
typedef struct BiTNode{BiElemType c;
struct BiTNode *lchild;
struct BiTNode *rchild;
} BiTNode, *BiTree;
// 辅助队列结构体
typedef struct tag{BiTree p; //树的某一个结点的地址值
struct tag *pnext;
} tag_t, *ptag_t;
+ typedef BiTree ElemType;
// 链表结点结构体
+ typedef struct LinkNode{+ ElemType data;
+ struct LinkNode *next;
+ }LinkNode;
+ typedef struct {+ LinkNode *front, *rear; // 链表头和链表尾
+ }LinkQueue;
+ void initQueue(LinkQueue &Q);
+ bool isEmpty(LinkQueue Q);
+ void EnQueue(LinkQueue &Q,ElemType value);
+ bool DeQueue(LinkQueue &Q,ElemType &value);
#endif //TREE_FUNCTION_H main.cpp文件
#include "function.h"
// 前序遍历--深度优先遍历
void preOrder(BiTree Tree){if (Tree!=NULL){printf("%c",Tree->c); //打印
preOrder(Tree->lchild);
preOrder(Tree->rchild);
}
}
// 中序遍历
void inOrder(BiTree Tree){if (Tree!=NULL){inOrder(Tree->lchild);
printf("%c",Tree->c); //打印
inOrder(Tree->rchild);
}
}
// 后序遍历
void postOrder(BiTree Tree){if (Tree!=NULL){postOrder(Tree->lchild);
postOrder(Tree->rchild);
printf("%c",Tree->c); //打印
}
}
// 层序遍历--广度优先遍历
void levelOrder(BiTree Tree){// 定义一个队列
LinkQueue Q;
// 初始化
initQueue(Q);
BiTree p;
// 入队
EnQueue(Q,Tree);
while (!isEmpty(Q)){// 判断队列是否为空
DeQueue(Q,p); // 出队当前结点并打印
putchar(p->c);
if (p->lchild!=NULL){EnQueue(Q,p->lchild); // 入队左孩子
}
if (p->rchild!=NULL){EnQueue(Q,p->rchild); // 入队右孩子
}
}
}
int main() {//1.用来指向新申请的树节点
BiTree pnew;
BiTree tree=NULL; //tree 指向树根用来代表树
BiElemType c;
// 2.辅助队列
ptag_t phead=NULL,ptail=NULL,list_pnew=NULL,pcur=NULL;
// abcdefghij
while (scanf("%c",&c)){if (c=='\n'){break; //读到换行就结束
}
pnew=(BiTree)calloc(1,sizeof(BiTNode));
pnew->c=c;
// 给队列结点申请空间
list_pnew=(ptag_t)calloc(1,sizeof(tag_t));
list_pnew->p=pnew;
// 判断是否是树的第一个结点
if (tree==NULL) {tree = pnew; // tree指向树的根节点
phead = list_pnew; // 第一个结点即是队列头，也是队列尾
ptail = list_pnew;
pcur = list_pnew; // 指向进入树的父亲元素
continue;
} else {// 先入队列
ptail->pnext=list_pnew;
ptail=list_pnew;
// 把结点放入树中
if(pcur->p->lchild==NULL){pcur->p->lchild=pnew;
} else if(pcur->p->rchild==NULL){pcur->p->rchild=pnew; //当前左右结点都有了，pcur后移一个
pcur=pcur->pnext;
}
}
}
printf("----------preOrder----------\n");
preOrder(tree);
printf("\n");
printf("----------inOrder----------\n");
inOrder(tree);
printf("\n");
printf("----------postOrder----------\n");
postOrder(tree);
printf("\n");
printf("----------levelOrder----------\n");
levelOrder(tree);
printf("\n");
return 0;
}
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
网页标题：(六)数据结构--二叉树-创新互联
当前网址：http://mswzjz.cn/article/djjcgi.html