(六)数据结构--二叉树-创新互联
1、树
当前文章:(六)数据结构--二叉树-创新互联
标题路径:http://scyanting.com/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
main.cpp文件#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;
}
5、二叉树的前序中序后序遍历
每一个遍历都必须和自己的父亲挨着
前序遍历(preOrder)–深度优先遍历先打印自身,再打印左子树,再打印右子树
前序遍历打印结果:abdhiejcfg
void preOrder(BiTree Tree){if (Tree!=NULL){printf("%c",Tree->c); //打印
preOrder(Tree->lchild);
preOrder(Tree->rchild);
}
}
中序遍历(inOrder)先打印左子树,再打印自身,再打印右子树bac
dbeac
…
中序遍历打印结果:hdibjeafcg
void inOrder(BiTree Tree){if (Tree!=NULL){inOrder(Tree->lchild);
printf("%c",Tree->c); //打印
inOrder(Tree->rchild);
}
}
后序遍历(PostOrder)先打印左子树,再打印右子树,在打印自身
后序遍历打印结果:hidjebfgca
void postOrder(BiTree Tree){if (Tree!=NULL){postOrder(Tree->lchild);
postOrder(Tree->rchild);
printf("%c",Tree->c); //打印
}
}
层序遍历(LevelOrder)–广度优先遍历层序遍历打印结果: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://scyanting.com/article/djjcgi.html