数据结构和算法（六）

今天药忘吃喽~ 2022-12-13 12:54 183阅读 0赞

二叉树的四种遍历以及代码实现(重点)  
===========================  
     1. 遍历的规则  
              前序遍历：根左右      注意：根最开始从整棵树的根节点开始  
              中序遍历：左根右      注意：起始位置的左，从最左下角的那个节点开始  
              后序遍历:  左右根      注意：起始位置的左，从最左下角的那个节点开始  
              层序遍历：一层层从上到下，从左到右遍历  
     2. 封装函数实现各种遍历  
            定义一个结构体来表示二叉树中的节点  
           struct  btree  //链式的  
           \{  
                char  data; //真实的数据  
                struct  btree  \*lchild;  //指向左孩子的指针  
                struct  btree  \*rchild;  //指向右孩子的指针  
           \}；  
   要求用户按照层序遍历去输入节点的数据  
          空格表示没有左孩子或者右孩子

BST树(二叉搜索树)  
=======================  
    1. 作用：  
              提高搜索，查询的速度     100个不同的数据 ---》从中找到45在哪里??  
                                                   最好的结果：找一次就找到  
                                                   最坏的结果：找100次才找到  
       原理：二叉搜索树的节点在存放的时候，按照左根右，依次小中大的顺序存放  
       特殊情况：构建二叉搜索树的时候有数据相等，如何处理？  
                         方式一：你规定的，相等的全部放在右边  
                         方式二：你规定的，相等的全部放在左边

2.插入和删除  
                 插入： 通过比较，比根节点小的往左边插入，比根节点大的往右边插入  
                 删除： 保证删除完毕以后，剩余的节点依然满足小中大的规则

作业：  
   1.  思考二叉树初始化构建的方法？？  有没有更好的

## 二叉树的遍历     ##

#include "myhead.h"
    
    //定义一个结构体来表示二叉树中的节点
    struct btree  //链式结构
    {
    	char data; //真实的数据
    	struct btree *lchild;  //指向左孩子的指针
    	struct btree *rchild;  //指向右孩子的指针
    };
    
    //初始化二叉树
    /*
    	思路一：初始化的函数只初始化一个根节点，其它节点键盘输入再存放
    	思路二：初始化的时候把整个二叉树全部搞定
    */
    struct btree *init_tree()
    {
    	//定义根节点
    	struct btree *root=malloc(sizeof(struct btree));
    	root->data='A';
    	root->lchild=NULL;
    	root->rchild=NULL;
    	
    	struct btree *node1=malloc(sizeof(struct btree));
    	node1->data='B';
    	node1->lchild=NULL;
    	node1->rchild=NULL;
    	
    	struct btree *node2=malloc(sizeof(struct btree));
    	node2->data='C';
    	node2->lchild=NULL;
    	node2->rchild=NULL;
    	
    	struct btree *node3=malloc(sizeof(struct btree));
    	node3->data='D';
    	node3->lchild=NULL;
    	node3->rchild=NULL;
    	
    	struct btree *node4=malloc(sizeof(struct btree));
    	node4->data='E';
    	node4->lchild=NULL;
    	node4->rchild=NULL;
    	
    	//把节点之间的逻辑关系表示出来
    	root->lchild=node1;
    	root->rchild=node2;
    	node1->lchild=node3;
    	node1->rchild=node4;
    	
    	return root;
    } 
    
    /* struct btree *init_tree()
    {
    	//定义根节点,初始化  
    	struct btree *root=malloc(sizeof(struct btree));
    	root->lchild=NULL;
    	root->rchild=NULL;
    	return root;
    } */
    
    //前序遍历的函数    根左右
    int pre_raversal(struct btree *root)
    {
    	//判断root是否为NULL
    	if(root==NULL)
    		return -1;
    	else
    	{
    		printf("%c",root->data);    //根
    		//递归调用自己
    		pre_raversal(root->lchild); //左 
    		pre_raversal(root->rchild); //右
    	}
    	return 0;
    }
    
    //中序遍历的函数    左根右
    int mid_raversal(struct btree *root)
    {
    	//判断root是否为NULL
    	if(root==NULL)
    		return -1;
    	else
    	{
    		//递归调用自己
    		mid_raversal(root->lchild); //左
    		printf("%c",root->data);    //根
    		mid_raversal(root->rchild); //右
    	}
    	return 0;
    }
    
    //后序遍历的函数    左右根
    int tail_raversal(struct btree *root)
    {
    	//判断root是否为NULL
    	if(root==NULL)
    		return -1;
    	else
    	{
    		//递归调用自己
    		tail_raversal(root->lchild); //左
    		tail_raversal(root->rchild); //右
    		printf("%c",root->data);    //根
    	}
    	return 0;
    }
    
    int main()
    {
    	char buf[20]={0};
    	//初始化一个二叉树
    	struct btree *mytree=init_tree();
    /* 	
    	//读取你键盘输入的数据保存到二叉树中，构建二叉树
    	printf("请依照我们规定的层序输入节点中的数据，没有的节点用空格代替!\n");
    	scanf("%s",buf);  //ABCDE空空
    	mytree->data=buf[0];
    	mytree->lchild->data=buf[1];
    	mytree->rchild->data=buf[2]; */
    	
    	
    	
    	
    	//前序遍历这棵树
    	pre_raversal(mytree);
    	printf("\n");
    	
    	//中序遍历这棵树
    	mid_raversal(mytree);
    	printf("\n");
    	
    	//后序遍历这棵树
    	tail_raversal(mytree);
    	printf("\n");
    }

## 链式队列 ##

#include "myhead.h"
    
    //定义结构体表示链式队列
    struct linkqueue
    {
    	int data;
    	struct linkqueue *tail; //指向队尾的指针
    	struct linkqueue *front; //指向队首的指针
    	struct linkqueue *next; //指向下一个节点的指针
    };
    
    //初始化
    struct linkqueue *init_queue()
    {
    	struct linkqueue *head=malloc(sizeof(struct linkqueue));
    	head->tail=head;
    	head->front=head->next;
    	head->next=NULL;
    	return head;
    }
    
    //入队
    int in_queue(int newdata,struct linkqueue *queue)
    {
    	//准备好新的节点
    	struct linkqueue *newnode=malloc(sizeof(struct linkqueue));
    	newnode->data=newdata;
    	newnode->tail=NULL;
    	newnode->front=NULL;
    	newnode->next=NULL;
    	
    	//在队尾位置入队
    	queue->tail->next=newnode;
    	
    	//更新队尾
    	queue->tail=newnode;
    	//更新队首
    	queue->front=queue->next;
    	return 0;
    }
    
    //出队
    int out_queue(struct linkqueue *queue)
    {
    	//先保存队首的数据
    	int num=queue->next->data; 
    	//删除队首的节点
    	queue->next=queue->next->next;
    	queue->front->next=NULL;
    	free(queue->front);
    	//更新一下
    	queue->front=queue->next;
    	return num;
    }
    
    int main()
    {
    	//初始化队列
    	struct linkqueue *myqueue=init_queue();
    	
    	//入队几个数据
    	in_queue(13,myqueue);
    	in_queue(23,myqueue);
    	in_queue(33,myqueue);
    	in_queue(43,myqueue);
    	in_queue(53,myqueue);
    	
    	//出队
    
    	printf("出队:%d\n",out_queue(myqueue));
    	printf("出队:%d\n",out_queue(myqueue));
    	printf("出队:%d\n",out_queue(myqueue));
    	printf("出队:%d\n",out_queue(myqueue));
    	printf("出队:%d\n",out_queue(myqueue)); 
    	
    }