机试练习Day3-二叉树题目

Dear 丶 2024-03-26 14:52 123阅读 0赞

#### 目录 ####

*   *  哈夫曼树
     *   *  基础知识
         *  简单图解
         *  代码展示
     *  二叉排序树
     *   *  基础知识
         *  代码展示

### 哈夫曼树 ###

第一行输入一个数n，表示叶结点的个数，需要用这些叶结点生成哈夫曼树。题目需要输出所有结点的值与权值的乘积之和的最小值。

#### 基础知识 ####

*  哈夫曼树的构成过程。
 *  sort()函数的参数。

#### 简单图解 ####

![在这里插入图片描述][4d770c1fe298401ca9927ca089945597.png_pic_center]  
自己手动计算的过程其实很简单：每次选择两个最小的数，相加之后存入数组，但之前的两个数就没用了，然后把这个计算结果加到最后的值里面，而最后输出的结果就是这些和的和【哈夫曼树的带权路径长度 = 非叶子结点的权值之和】。但是问题是如何做到废除相加的两个数、如何把新的结果存起来。

*  解决思路：考虑到每次得出结果之后都需要更新数组重新排序，所以想到了循环，再利用循环每次+1的特点废除第一个因子，并把结果存到第二个因子的位置以此废除第二个因子。

#### 代码展示 ####

#include<bits/stdc++.h>
    using namespace std;
    
    int main()
    {
        
    	int n,weight;
    	int number[1000];
    	while(cin>>n)
    	{
        
    		weight=0;
    		for(int i=0;i<n;i++)
    			cin>>number[i];
    		//因为涉及到加法次数，所以j的上限很重要
    		for(int j=0;j<n-1;j++)
    		{
        
    			//每次循环j++后，从新的j开始刚好是一个新的数组
    			//注意：number数组中一直是5个数，所以第二个参数不能改
    			sort(number+j,number+n);
    			//这里仅仅是改变了number[j+1]的值
    			//至于number[j]的值就没那么重要了，因为下次排序不会用
    			number[j+1]=number[j]+number[j+1];
    			weight=weight+number[j+1];
    		}
    		cout<<weight<<endl;
    	}
    }

### 二叉排序树 ###

输入一系列整数，建立二叉排序树，并进行前序，中序，后序遍历。但是，重复的数据不参与建树。

#### 基础知识 ####

*  二叉排序树的定义、构建。
 *  树的遍历。

#### 代码展示 ####

#include<bits/stdc++.h>
    using namespace std;
    
    typedef struct tree
    {
        
    	int data;
    	tree *lchild;
    	tree *rchild;
    }tree;
    
    tree* buildtree(tree* root,int a)
    {
        
    	if(root==NULL)
    	{
        
    		//给根节点申请一个空间
    		root=(tree*)malloc(sizeof(tree));
    		root->lchild=NULL;
    		root->rchild=NULL;
    		root->data=a;
    		return root;
    	}
    	//直接不考虑相等的情况是不行的，因为要考虑函数的返回值
    	if(root->data==a)
    		return root;
    	if(root->data>a)
    		root->lchild=buildtree(root->lchild,a);
    	if(root->data<a)
    		root->rchild=buildtree(root->rchild,a);
    	return root;
    }
    //前序遍历
    void pre(tree* root)
    {
        
    	if(root!=NULL)
    	{
        
    		cout<<root->data<<" ";
    		pre(root->lchild);
    		pre(root->rchild);
    	}
    }
    //中序遍历，如果是复制的前序遍历的代码，不要忘记改函数体里面的名字
    void mid(tree* root)
    {
        
    	if(root!=NULL)
    	{
        
    		mid(root->lchild);
    		cout<<root->data<<" ";
    		mid(root->rchild);
    	}
    }
    //后序遍历，如果是复制的前序遍历的代码，不要忘记改函数体里面的名字
    void pro(tree* root)
    {
        
    	if(root!=NULL)
    	{
        
    		pro(root->lchild);
    		pro(root->rchild);
    		cout<<root->data<<" ";
    	}
    }
    	
    int main()
    {
        
    	int x;
    	while(cin>>x)
    	{
        
    		//每次置空的时间看好，位置不要搞错了
    		tree *root=NULL;
    		while(x--)
    		{
        
    			int a;
    			//不要忘记cin>>a
    			cin>>a;
    			//buildtree函数返回值要接收的
    			root=buildtree(root,a);
    		}
    		pre(root);
    		cout<<endl;
    		mid(root);
    		cout<<endl;
    		pro(root);
    		cout<<endl;		
    	}
    }

[4d770c1fe298401ca9927ca089945597.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/ef097d8c154c4b4c896efb19b22f3f31.png