一、队列。
1、什么是队列？
在一条储存的结构中，插入节点与删除节点分别在两端进行的，例如：插入数据在队尾处理、删除数据在队头处理，那么这种逻辑就叫做队列。
其特点是先进先出、后进后出。
插入数据-入队。
删除数据-出队。
2、设计队列结构体。
1）设计队列节点结构体。
structnode{
intdata;
structnode*next;
};
2）设计管理队列的结构体。
structqueue{
structnode*head;//指向队头节点的指针
structnode*tail;//指向队尾节点的指针
intsize;
}
二、实现队列的出队与入队的步骤。
#includestdio.h
#includestdlib.h
structnode{
intdata;
structnode*next;
};
structqueue{
structnode*head;//指向队头-出队
structnode*tail;//指向队尾-入队
intsize;//统计当前队列中的节点个数
};
structqueue*init_queue()
{
//1.为管理结构体申请空间。
structqueue*q=malloc(sizeof(structqueue));
if(q==NULL)
printf("mallocqueueerror!\n");
//2.为结构体赋值。
q-head=NULL;
q-tail=NULL;
q-size=0;
returnq;
}
intin_queue(structqueue*q,intnum)
{
//1.为新节点申请空间。
structnode*new=malloc(sizeof(structnode));
if(new==NULL)
printf("mallocerror!\n");
//2.为新节点赋值。
new-data=num;
new-next=NULL;
//3.将节点插入到队列中。
if(q-size==0)//如果插入的节点是第一个节点，则需要特殊处理。
{
//如果队列只有你一个人，那么队头队尾都是你
q-head=new;
q-tail=new;
}
else{
q-tail-next=new;//原来的那个队尾的指针域指向这个新节点。
q-tail=new;//队尾就指向新节点。
}
q-size++;
return0;
}
intshow_queue(structqueue*q)
{
//1.先判断是不是空队。
if(q-size==0)
return-1;
//2.遍历队列。
structnode*tmp=NULL;
for(tmp=q-head;tmp!=NULL;tmp=tmp-next)
{
printf("%d-",tmp-data);
}
printf("\n");
return0;
}
intout_queue(structqueue*q,int*p)
{
//1.出队之前先判断一下队列是否为空。
if(q-size==0)
return-1;
//2.不为空，正常出队。
structnode*tmp=q-head;//这个tmp就是等会需要出队的那个人。
//3.分情况讨论。
if(q-size==1)//整个队列中就剩一个节点
{
q-head=NULL;
q-tail=NULL;
}
else{
q-head=q-head-next;
}
*p=tmp-data;//其实就是给a赋值。
//4.释放出队的节点的空间。
free(tmp);
q-size--;
return0;
}
intdestroy_queue(structqueue*q)
{
free(q);
}
intmain(intargc,char*argv[])
{
//1.初始化一条空队。
structqueue*q=NULL;
q=init_queue();
//2.入队
in_queue(q,10);
in_queue(q,20);
in_queue(q,30);
in_queue(q,40);
//3.遍历队列。
show_queue(q);
//4.出队。
inta;
while(q-size!=0)
{
out_queue(q,a);
printf("a=%d\n",a);
}
//5.销毁
destroy_queue(q);
return0;
}
练习：写一个程序，处于一个不断输入整数状态。
如果输入是正整数，则将该整数入队。---客户取号。
如果输入是一个负数，则输出队列中头节点的值。---柜台工作人员按下按键、排在最开头的那个人就可以办理业务。
如果输入是一个0，则结束程序。---今天收工。
三、二叉树。
1、为什么要学习二叉树？
前面我们都已经学习过链表了，大家都知道，如果我们需要检索出一个数据出来，有可能检索一次，就可以找到数据，有可能检索到最后一个节点才能找到节点，这就是链表的特点，也就是说，寻找一条长度为N个节点的链表，搜索次数处于1~N-1(头节点无效)，二叉树的出现，就是为了减少检索数据时的次数。
2、什么是二叉树？
二叉树也是一种储存结构，也就是说跟链表一样，都是来储存数据的，但是链表是线性规则的结构，而二叉树是非线性的储存结构。二叉树有一个根节点作为起始点，这个根节点也是可以存放数据的。二叉树结构就是把小于根节点的数据储存到根节点的左边，把大于根节点的数据储存到根节点的右边。这样就实现了检索时，不需要更加多次数。
例如：根是20，根左边是18，根的右边是23，当我们寻找一个节点数据为23时，就不需要考虑去根的左边寻找，只需要考虑去根的右边寻找即可。二叉树，就是为了提高效率。
3、介绍二叉树基本概念。
1）双亲与孩子A就是B与C的双亲，B与C就是A的孩子。
2）兄弟：拥有共同双亲的两个节点称之为兄弟J与K就是兄弟，D与E就是兄弟。
3）度：形容一个节点孩子的个数A的度是2D的度是0L的度是1
4）层：A的层是1B/C的层是2
4、二叉树的种类。
1）只有根节点的二叉树
跟是一棵树的基本，哪怕是只有一个根节点，也可以形成一棵树。
2）普通二叉树。
树上面任意的一个节点的度都是小于或者等于2(任意一个节点小孩不得超过2个，可以0个，可以1个，可以2个，但是不可以3个或者以上)
3）满二叉树。
树上面任意的一个节点的度都是等于2，也就是说，假设一棵树有N层，其树的节点达到了2的N次方-1个，那么这颗树就是满二叉树。
4）非二叉树。
只要树上面有任意一个点其度超过2，那么这棵树就是非二叉树。
四、二叉树的增删改查？
1、设计节点。
通过分析，任意一个节点的度都是小于等于2，所以节点模型：
structnode{
intdata;
structnode*lchild;
structnode*rchild;
};
2、初始化一棵二叉树的根节点。
structnode*init_new_node(intnum)
{
//1.为节点申请空间。
structnode*root=malloc(sizeof(structnode));
if(root==NULL)
printf("mallocerror!\n");
//2.为节点赋值。
root-data=num;
root-lchild=NULL;
root-rchild=NULL;
returnroot;
}
3、插入节点到二叉树中。
structnode*insert_node(structnode*new,structnode*root)
{
//1.先判断树的根节点存不存在，如果不存在，则插入的数据就作为根节点。
if(root==NULL)
{
returnnew;//那么新节点就作为根节点。
}
//2.如果树有根节点，则正常插入节点。
if(new-dataroot-data)//该节点应该放在根节点的右边。
{
root-rchild=insert_node(new,root-rchild);
}
elseif(new-dataroot-data)//该节点应该放在根节点的左边。
{
root-lchild=insert_node(new,root-lchild);
}
else{
printf("%dnodealreadyexists!\n",new-data);
}
returnroot;
}
4、搜索二叉树中的节点。
structnode*find_node(structnode*root,intnum)
{
if(root==NULL)//找到底都没有找到你啊
{
returnNULL;
}
if(numroot-data)//如果这个数字比root数字要小，则去root的左边寻找。
{
returnfind_node(root-lchild,num);
}
elseif(numroot-data)//如果这个数字比root数字要大，则去root的右边寻找。
{
returnfind_node(root-rchild,num);
}
else{//如果这个num与root-data一样，则这个root就是我想找的东西。
returnroot;
}
}
5、遍历二叉树。
1）先序遍历。
顺序：根-左-右
voidshow_node_first(structnode*root)
{
if(root==NULL)
return;
printf("%d\n",root-data);//根
show_node_first(root-lchild);//左
show_node_first(root-rchild);//右
return;
}
2）中序遍历。
顺序：左-根-右
voidshow_node_middle(structnode*root)
{
if(root==NULL)
return;
show_node_middle(root-lchild);//左
printf("%d\n",root-data);//根
show_node_middle(root-rchild);//右
return;
}
3）后序遍历。
顺序：左-右-根
voidshow_node_last(structnode*root)
{
if(root==NULL)
return;
show_node_last(root-lchild);//左
show_node_last(root-rchild);//右
printf("%d\n",root-data);//根
return;
}
4）按层遍历。
步骤如下：
1.初始化一条空的队列。
2.将根节点入队。
3.出队，如果出队失败，则结束程序，如果成功，则打印该节点。
4.找到出队的那个节点。
5.判断刚刚出队的那个节点有没有左孩子，如果有则将左孩子入队。
6.判断刚刚出队的那个节点有没有右孩子，如果有则将右孩子入队。
7.重复第3步。
intshow_node_level(structnode*root)
{
if(root==NULL)
return-1;
//1.初始化一条空队列。
structqueue*q=NULL;
q=init_queue();
//2.将根节点入队。
in_queue(q,root-data);
//3.出队，如果出队失败，则结束程序，如果成功，则打印该节点。
inta;
structnode*tmp=NULL;
while(1)
{
if(out_queue(q,a)==-1)//出队失败
break;
printf("%d\n",a);
//4.找到出队的那个节点。
tmp=find_node(root,a);
//5.判断刚刚出队的那个节点有没有左孩子，如果有则将左孩子入队。
if(tmp-lchild!=NULL)//不为NULL，则说明有左孩子。
in_queue(q,tmp-lchild-data);
//6.判断刚刚出队的那个节点有没有右孩子，如果有则将右孩子入队。
if(tmp-rchild!=NULL)//不为NULL，则说明有右孩子。
in_queue(q,tmp-rchild-data);
}
free(q);
return0;
}
6、删除节点。
1）如果需要删除的节点有左子树（不管有没有右子树），其方法是将左子树中最大值替换掉该节点。
第一步：通过递归寻找到需要删除的节点。
第二步：找到删除的那个节点的左子树的最大值。
第三步：将这个最大值替换需要删除的节点。
第四步：通过调用删除函数，递归地去删除这个最大值。（不能直接删除，需要递归删除，因为这个节点虽然肯定没有右子树（因为如果有右，该节点就不是最大），但是有可能有左子树。）
2）如果需要删除的节点只有右子树，其方法就把右子树中最小值替换该节点。
第一步：通过递归寻找到需要删除的节点。
第二步：找到删除的那个节点的右子树的最小值。
第三步：将这个最小值替换需要删除的节点。
第四步：通过调用删除函数，递归地去删除这个最小值。（不能直接删除，需要递归删除，因为这个节点虽然肯定没有左子树（因为如果有左，该节点就不是最小），但是有可能有右子树。）
3）如果需要删除的节点的度为0，则直接删除。
第一步：通过递归寻找到需要删除的节点。
第二步：直接调用free()释放该节点的空间。
structnode*delete_node(structnode*root,intnum)
{
//1.找到底都没有找到该节点，直接返回NULL。
if(root==NULL)
returnNULL;
//2.寻找需要删除的节点。
if(numroot-data)//应该去左边找
{
root-lchild=delete_node(root-lchild,num);
}
elseif(numroot-data)
{
root-rchild=delete_node(root-rchild,num);
}
else{//找到你想删除的节点了，这个节点就是root
//3.判断需要删除的节点有没有左子树
structnode*tmp=NULL;
if(root-lchild!=NULL)//不为NULL,说明有左子树
{
//4.寻找该节点左子树中的最大值。
for(tmp=root-lchild;tmp-rchild!=NULL;tmp=tmp-rchild);
//从循环中出来时，tmp就是左子树中的最大值。
//5.将tmp指向数据赋值给需要删除的节点的数据域，
root-data=tmp-data;
//6.递归删除这个tmp
root-lchild=delete_node(root-lchild,tmp-data);
}
elseif(root-rchild!=NULL)//不为NULL，说明有右子树
{
//4.寻找该节点右子树中的最小值。
for(tmp=root-rchild;tmp-lchild!=NULL;tmp=tmp-lchild);
//从循环中出来时，tmp就是右子树中的最小值。
//5.将tmp指向数据赋值给需要删除的节点的数据域，
root-data=tmp-data;
//6.递归删除这个tmp
root-rchild=delete_node(root-rchild,tmp-data);
}
else{
free(root);
returnNULL;//最后的节点释放了，需要返回一个NULL，给指向这个最后的节点的左/右指针。
}
}
returnroot;
}
=============================================
例程1：
#includestdio.h
#includestdlib.h
//二叉树的节点
structnode{
intdata;
structnode*lchild;
structnode*rchild;
};
//队列的节点
structq_node{
intdata;
structq_node*next;
};
//管理队列的结构体
structqueue{
structq_node*head;//指向队头-出队
structq_node*tail;//指向队尾-入队
intsize;//统计当前队列中的节点个数
};
structqueue*init_queue()
{
//1.为管理结构体申请空间。
structqueue*q=malloc(sizeof(structqueue));
if(q==NULL)
printf("mallocqueueerror!\n");
//2.为结构体赋值。
q-head=NULL;
q-tail=NULL;
q-size=0;
returnq;
}
intin_queue(structqueue*q,intnum)
{
//1.为新节点申请空间。
structq_node*new=malloc(sizeof(structq_node));
if(new==NULL)
printf("mallocerror!\n");
//2.为新节点赋值。
new-data=num;
new-next=NULL;
//3.将节点插入到队列中。
if(q-size==0)//如果插入的节点是第一个节点，则需要特殊处理。
{
//如果队列只有你一个人，那么队头队尾都是你
q-head=new;
q-tail=new;
}
else{
q-tail-next=new;//原来的那个队尾的指针域指向这个新节点。
q-tail=new;//队尾就指向新节点。
}
q-size++;
return0;
}
intout_queue(structqueue*q,int*p)
{
//1.出队之前先判断一下队列是否为空。
if(q-size==0)
return-1;
//2.不为空，正常出队。
structq_node*tmp=q-head;//这个tmp就是等会需要出队的那个人。
//3.分情况讨论。
if(q-size==1)//整个队列中就剩一个节点
{
q-head=NULL;
q-tail=NULL;
}
else{
q-head=q-head-next;
}
*p=tmp-data;//其实就是给a赋值。
//4.释放出队的节点的空间。
free(tmp);
q-size--;
return0;
}
structnode*init_new_node(intnum)
{
//1.为节点申请空间。
structnode*root=malloc(sizeof(structnode));
if(root==NULL)
printf("mallocerror!\n");
//2.为节点赋值。
root-data=num;
root-lchild=NULL;
root-rchild=NULL;
returnroot;
}
structnode*insert_node(structnode*new,structnode*root)
{
//1.先判断树的根节点存不存在，如果不存在，则插入的数据就作为根节点。
if(root==NULL)
{
returnnew;//那么新节点就作为根节点。
}
//2.如果树有根节点，则正常插入节点。
if(new-dataroot-data)//该节点应该放在根节点的右边。
{
root-rchild=insert_node(new,root-rchild);
}
elseif(new-dataroot-data)//该节点应该放在根节点的左边。
{
root-lchild=insert_node(new,root-lchild);
}
else{
printf("%dnodealreadyexists!\n",new-data);
}
returnroot;
}
structnode*find_node(structnode*root,intnum)
{
if(root==NULL)//找到底都没有找到你啊
{
returnNULL;
}
if(numroot-data)//如果这个数字比root数字要小，则去root的左边寻找。
{
returnfind_node(root-lchild,num);
}
elseif(numroot-data)//如果这个数字比root数字要大，则去root的右边寻找。
{
returnfind_node(root-rchild,num);
}
else{//如果这个num与root-data一样，则这个root就是我想找的东西。
returnroot;
}
}
voidshow_node_first(structnode*root)
{
if(root==NULL)
return;
printf("%d\n",root-data);//根
show_node_first(root-lchild);//左
show_node_first(root-rchild);//右
return;
}
voidshow_node_middle(structnode*root)
{
if(root==NULL)
return;
show_node_middle(root-lchild);//左
printf("%d\n",root-data);//根
show_node_middle(root-rchild);//右
return;
}
voidshow_node_last(structnode*root)
{
if(root==NULL)
return;
show_node_last(root-lchild);//左
show_node_last(root-rchild);//右
printf("%d\n",root-data);//根
return;
}
intshow_node_level(structnode*root)
{
if(root==NULL)
return-1;
//1.初始化一条空队列。
structqueue*q=NULL;
q=init_queue();
//2.将根节点入队。
in_queue(q,root-data);
//3.出队，如果出队失败，则结束程序，如果成功，则打印该节点。
inta;
structnode*tmp=NULL;
while(1)
{
if(out_queue(q,a)==-1)//出队失败
break;
printf("%d\n",a);
//4.找到出队的那个节点。
tmp=find_node(root,a);
//5.判断刚刚出队的那个节点有没有左孩子，如果有则将左孩子入队。
if(tmp-lchild!=NULL)//不为NULL，则说明有左孩子。
in_queue(q,tmp-lchild-data);
//6.判断刚刚出队的那个节点有没有右孩子，如果有则将右孩子入队。
if(tmp-rchild!=NULL)//不为NULL，则说明有右孩子。
in_queue(q,tmp-rchild-data);
}
free(q);
return0;
}
structnode*delete_node(structnode*root,intnum)
{
//1.找到底都没有找到该节点，直接返回NULL。
if(root==NULL)
returnNULL;
//2.寻找需要删除的节点。
if(numroot-data)//应该去左边找
{
root-lchild=delete_node(root-lchild,num);
}
elseif(numroot-data)
{
root-rchild=delete_node(root-rchild,num);
}
else{//找到你想删除的节点了，这个节点就是root
//3.判断需要删除的节点有没有左子树
structnode*tmp=NULL;
if(root-lchild!=NULL)//不为NULL,说明有左子树
{
//4.寻找该节点左子树中的最大值。
for(tmp=root-lchild;tmp-rchild!=NULL;tmp=tmp-rchild);
//从循环中出来时，tmp就是左子树中的最大值。
//5.将tmp指向数据赋值给需要删除的节点的数据域，
root-data=tmp-data;
//6.递归删除这个tmp
root-lchild=delete_node(root-lchild,tmp-data);
}
elseif(root-rchild!=NULL)//不为NULL，说明有右子树
{
//4.寻找该节点右子树中的最小值。
for(tmp=root-rchild;tmp-lchild!=NULL;tmp=tmp-lchild);
//从循环中出来时，tmp就是右子树中的最小值。
//5.将tmp指向数据赋值给需要删除的节点的数据域，
root-data=tmp-data;
//6.递归删除这个tmp
root-rchild=delete_node(root-rchild,tmp-data);
}
else{
free(root);
returnNULL;//最后的节点释放了，需要返回一个NULL，给指向这个最后的节点的左/右指针。
}
}
returnroot;
}
intmain(intargc,char*argv[])
{
//1.初始化二叉树的根节点。
structnode*root=NULL;
root=init_new_node(20);
//2.插入节点
structnode*new=NULL;
new=init_new_node(35);
insert_node(new,root);
new=init_new_node(25);
insert_node(new,root);
new=init_new_node(40);
insert_node(new,root);
new=init_new_node(33);
insert_node(new,root);
new=init_new_node(30);
insert_node(new,root);
new=init_new_node(34);
insert_node(new,root);
new=init_new_node(29);
insert_node(new,root);
new=init_new_node(31);
insert_node(new,root);
new=init_new_node(32);
insert_node(new,root);
//3.搜索节点。
structnode*tmp=NULL;
tmp=find_node(root,15);
if(tmp!=NULL)
{
printf("tmp-data:%d\n",tmp-data);
}
//4.先序遍历二叉树。
//show_node_first(root);
//5.中序遍历二叉树。
//show_node_middle(root);
//6.后序遍历二叉树。
//show_node_last(root);
//7.按层遍历。
show_node_level(root);
printf("===============\n");
delete_node(root,33);
show_node_level(root);
return0;
}
=============================================
例程2：
#includestdio.h
#includestdlib.h
structnode{
intdata;
structnode*next;
};
structqueue{
structnode*head;//指向队头-出队
structnode*tail;//指向队尾-入队
intsize;//统计当前队列中的节点个数
};
structqueue*init_queue()
{
//1.为管理结构体申请空间。
structqueue*q=malloc(sizeof(structqueue));
if(q==NULL)
printf("mallocqueueerror!\n");
//2.为结构体赋值。
q-head=NULL;
q-tail=NULL;
q-size=0;
returnq;
}
intin_queue(structqueue*q,intnum)
{
//1.为新节点申请空间。
structnode*new=malloc(sizeof(structnode));
if(new==NULL)
printf("mallocerror!\n");
//2.为新节点赋值。
new-data=num;
new-next=NULL;
//3.将节点插入到队列中。
if(q-size==0)//如果插入的节点是第一个节点，则需要特殊处理。
{
//如果队列只有你一个人，那么队头队尾都是你
q-head=new;
q-tail=new;
}
else{
q-tail-next=new;//原来的那个队尾的指针域指向这个新节点。
q-tail=new;//队尾就指向新节点。
}
q-size++;
return0;
}
intshow_queue(structqueue*q)
{
//1.先判断是不是空队。
if(q-size==0)
return-1;
//2.遍历队列。
structnode*tmp=NULL;
for(tmp=q-head;tmp!=NULL;tmp=tmp-next)
{
printf("%d-",tmp-data);
}
printf("\n");
return0;
}
intout_queue(structqueue*q,int*p)
{
//1.出队之前先判断一下队列是否为空。
if(q-size==0)
return-1;
//2.不为空，正常出队。
structnode*tmp=q-head;//这个tmp就是等会需要出队的那个人。
//3.分情况讨论。
if(q-size==1)//整个队列中就剩一个节点
{
q-head=NULL;
q-tail=NULL;
}
else{
q-head=q-head-next;
}
*p=tmp-data;//其实就是给a赋值。
//4.释放出队的节点的空间。
free(tmp);
q-size--;
return0;
}
intdestroy_queue(structqueue*q)
{
free(q);
}
intmain(intargc,char*argv[])
{
//1.初始化一条空队。
structqueue*q=NULL;
q=init_queue();
//2.入队
in_queue(q,10);
in_queue(q,20);
in_queue(q,30);
in_queue(q,40);
//3.遍历队列。
show_queue(q);
//4.出队。
inta;
while(q-size!=0)
{
out_queue(q,a);
printf("a=%d\n",a);
}
//5.销毁
destroy_queue(q);
return0;
}
善解人意是特么什么东西?委屈我自己让你开心吗?
该用户名已注册
你我轻松一赞，金钱或多或少。
