二叉树及其应用-二叉树的遍历及哈夫曼树-数据结构上机实验

深碍√TFBOYSˉ_ 2022-08-10 09:49 97阅读 0赞

1、二叉树的遍历

主要实现：创建二叉树、用先中后序遍历二叉树（中序，先序和后序遍历用非递归实现），并输出树高。

2、哈夫曼树

主要实现：创建一颗哈夫曼树，并输出每个节点的哈夫曼编码。

1.二叉树

#include<stdio.h>
    #include <iostream>
    #include<string.h>
    #include<stack>//采用世界先进，国际一流的栈容器,方便省事不调试 
    #include<algorithm>
    using namespace std;
    typedef struct binode
    {
    	char data;
    	binode *lch,*rch;
    }*bitree;
    typedef struct node1
    {
        binode *btnode;
        bool isFirst;
    }BTNode;
    void CreateBiTree(bitree &T)
    {
    	char ch;
    	ch=getchar();
    	if(ch =='#')
    	{
    		T=NULL;
    	}
    	else
    	{
    		T = (bitree)malloc(sizeof(binode));
    		T->data = ch;
    		CreateBiTree(T->lch);
    		CreateBiTree(T->rch);
    	}
    }
    void xianxu(binode *root)     //非递归前序遍历 
    {
        stack<binode*> s;
        binode *p=root;
        while(p!=NULL||!s.empty())
        {
            while(p!=NULL)
            {
                printf("%c ",p->data);
                s.push(p);
                p=p->lch;
            }
            if(!s.empty())
            {
                p=s.top();
    			s.pop();
    			p=p->rch;
            }
        }
    }
    void zhongxu(binode *T)      //非递归中序遍历
    {
       bitree curr = T;   
        stack<bitree> s;  
        while(curr != NULL || !s.empty())  
        {  
            while(curr != NULL)  
            {  
                s.push(curr);  
                curr = curr->lch;  
            } 
            if(!s.empty())  
            {  
                curr = s.top();  
                s.pop();  
                cout<<curr->data<<" ";  
                curr = curr->rch;  
            }  
        }  
    }
    void houxu(binode *root)    //非递归后序遍历
    {
        stack<BTNode*> s;
        binode *p=root;
        BTNode *temp;
        while(p!=NULL||!s.empty())
        {
            while(p!=NULL)              //沿左子树一直往下搜索，直至出现没有左子树的结点 
            {
                BTNode *btn=new BTNode;
                btn->btnode=p;
                btn->isFirst=true;
                s.push(btn);
                p=p->lch;
            }
            if(!s.empty())
            {
                temp=s.top();
                s.pop();
                if(temp->isFirst==true)     //表示是第一次出现在栈顶 
                 {
                    temp->isFirst=false;
                    s.push(temp);
                    p=temp->btnode->rch;    
                }
                else                        //第二次出现在栈顶 
                 {
                    printf("%c ",temp->btnode->data);
                    p=NULL;
                }
            }
        }    
    }
    int depth(binode *root)
    {
    	int hl,hr;
    	if(!root)
    	return 0;
    	else
    	{
    		hl=depth(root->lch);
    		hr=depth(root->rch);
    		return max(hl,hr)+1;
    	}
    }
    int main()
    {
    	while(1)
    	{
    		binode *T;
    		printf("建造二叉树：");
    		CreateBiTree(T);
    		binode *x1,*x2,*x3;
    		x1=x2=x3=T;
    		printf("\n");
    		printf("树的先序遍历：");//建树的最后递归结束时T自然就是根节点 
    		xianxu(x1); 
    		printf("\n");
    		printf("\n");
    		printf("树的中序遍历：");
    		zhongxu(x2); 
    		printf("\n");
    		printf("\n");
    		printf("树的后序遍历：");
    		houxu(x3); 
    		printf("\n");
    		printf("\n");
    		printf("树的深度为：%d\n",depth(T));
    		printf("\n");
    	}	
    	return 0;
    }

2.哈夫曼树

#include<iostream>
    #include<string.h> 
    #include<stdio.h>
    #include<algorithm>
    using namespace std;
    typedef struct
    {
    	int weight;
    	int parent,lchild,rchild;
    }HTNode,*HuffmanTree;
    typedef char **HuffmanCode;
    void Select(HuffmanTree HT,int len,int &s1,int &s2)//寻找两个最小值 
    {
    	int i,min1=0x3f3f3f3f,min2=0x3f3f3f3f;//先赋予最大值
    	for(i=1;i<=len;i++)
    	{
    		if(HT[i].weight<min1&&HT[i].parent==0)
    		{
    			min1=HT[i].weight;
    			s1=i;
    		}	
    	}
    	int temp=HT[s1].weight;//将原值存放起来，然后先赋予最大值，防止s1被重复选择
    	HT[s1].weight=0x3f3f3f3f;
    	for(i=1;i<=len;i++)
    	{
    		if(HT[i].weight<min2&&HT[i].parent==0)
    		{
    			min2=HT[i].weight;
    			s2=i;
    		}
    	}
    	HT[s1].weight=temp;//恢复原来的值
    }
    void CreatHuffmanTree(HuffmanTree &HT,int n)//构建 HT 
    {
    	int m,s1,s2,i;
    	if(n<=1) return;
    	m=2*n-1;
    	HT=new HTNode[m+1];  		
    	for(i=1;i<=m;++i)       //初始化 	
    	   { HT[i].parent=0;  HT[i].lchild=0;  HT[i].rchild=0; }
    	cout<<"请输入叶子结点的权值：\n";
    	for(i=1;i<=n;++i)     
    		cin>>HT[i].weight;  
    	for(i=n+1;i<=m;++i) //构建 
    	{  	//通过n-1次的选择、删除、合并来创建赫夫曼树
    		Select(HT,i-1,s1,s2);// 并返回它们在HT中的序号s1和s2
    		HT[s1].parent=i; 	
    		HT[s2].parent=i;   
    		//得到新结点i，从森林中删除s1，s2，将s1和s2的双亲域由0改为i
    		HT[i].lchild=s1;   
    		HT[i].rchild=s2 ;							//s1,s2分别作为i的左右孩子
    		HT[i].weight=HT[s1].weight+HT[s2].weight; 	//i 的权值为左右孩子权值之和
    	}												//for
    }	
    void CreatHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int n)//从叶子到根逆向求每个字符的赫夫曼编码，存储在编码表HC中
    {
    	int i,start,c,f;
    	HC=new char*[n+1];         						//分配n个字符编码的头指针矢量
    	char *cd=new char[n];							//分配临时存放编码的动态数组空间
    	cd[n-1]='\0';                            		//编码结束符
    	for(i=1;i<=n;++i)
    	{                      							//逐个字符求赫夫曼编码
    		start=n-1;                          		//start开始时指向最后，即编码结束符位置
    		c=i; 
    		f=HT[i].parent;                 			//f指向结点c的双亲结点
    		while(f!=0)
    		{                          					//从叶子结点开始向上回溯，直到根结点
    			start--;                          		//回溯一次start向前指一个位置
    			if(HT[f].lchild==c)  
    				cd[start]='0';						//结点c是f的左孩子，则生成代码0
    			else 
    				cd[start]='1';                 		//结点c是f的右孩子，则生成代码1
    			c=f; 
    			f=HT[f].parent;             			//继续向上回溯
    		}                                  			//求出第i个字符的编码      
    		HC[i]=new char[n-start];         			// 为第i 个字符编码分配空间
    		strcpy(HC[i], &cd[start]);        			//将求得的编码从临时空间cd复制到HC的当前行中
    	}
    	delete cd;                            			//释放临时空间
    }													// CreatHuffanCode
    void show(HuffmanTree HT,HuffmanCode HC,int n)
    {
    	for(int i=1;i<=n;i++)
    		cout<<HT[i].weight<<"编码为"<<HC[i]<<endl;
    }
    int main()
    {
    	HuffmanTree HT;
    	HuffmanCode HC;
    	int n;
    	cout<<"请输入叶子结点的个数：\n";
    	cin>>n;											//输入赫夫曼树的叶子结点个数
    	CreatHuffmanTree(HT,n);							//在哈夫曼树中因为叶子数正好节点数 
    	CreatHuffmanCode(HT,HC,n);
    	show(HT,HC,n);
    	return 0;
    }