二叉树的遍历及基本运算

逃离我推掉我的手 2022-11-25 13:23 130阅读 0赞

## 二叉树的遍历及基本运算 ##

一、实验目的：

1.深入理解二叉树的基本概念和递归程序设计方法。  
2.熟练掌握二叉树在二叉链表存储结构中的常用遍历方法：先序、中序、后序递归遍历，了解先序、中序和后序非递归遍历及层序遍历。  
3.用二叉树解决实际问题，如掌握构造哈夫曼树及其编码和译码的方法。

二、实验内容：

1.建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果；  
2.建立一棵二叉树，求二叉数的树的深度、统计叶子结点的个数、统计总的结点个数、进行层序遍历、交换左右子树等；  
3.哈夫曼编码译码系统。

三、实验要求

1.在本题下面提交源程序和实验运行结果截图。  
2.建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果；

#include<stdio.h>
    #include<stdlib.h>
    #include<malloc.h>    
        typedef struct Node//结构体  
        {
        
        	char data;
        	struct Node *LChild;
        	struct Node *RChild;
        } BiTNode,*BiTree;
        
        void InitList(BiTree *l)//初始化
        {
        
        *l= (BiTree)malloc(sizeof(BiTNode));
        (*l)->LChild = NULL;
        (*l)->RChild = NULL;
        }    
        void CreateBiTree(BiTree *bt) //先序创建二叉树 
        {
        
        	char ch;
        	ch = getchar();
        	if (ch == ' ') *bt = NULL;
        	else
        	{
        
        		*bt = (BiTree)malloc(sizeof(BiTNode));
        		(*bt)->data = ch;
        		CreateBiTree(&((*bt)->LChild));
        		CreateBiTree(&((*bt)->RChild));
        	}
        }    
        void PreOrder(BiTree root)//先序遍历 
        {
        
        	if (root != NULL)
        	{
        
        		printf("%c", root->data);
        		PreOrder(root->LChild);
        		PreOrder(root->RChild);
        	}
            
        void InOrder(BiTree root)//中序遍历 
        {
        
        	if (root != NULL)
        	{
        
        		InOrder(root->LChild);
        		printf("%c", root->data);
        		InOrder(root->RChild);
        	}
        }    
        void PostOrder(BiTree root)//后序遍历 
        {
        
        	if (root != NULL)
        	{
        
        		PostOrder(root->LChild);
        		PostOrder(root->RChild);
        		printf("%c", root->data);
        	}
        }    
        int main()
        {
            
        	BiTree bt;
        	InitList(&bt);
        	CreateBiTree(&bt);
        	printf("前序遍历二叉树: ");
    		PreOrder(bt);
        	printf("\n中序遍历二叉树：");
        	InOrder(bt);
        	printf("\n后序遍历二叉树：");
        	PostOrder(bt);
    		printf("\n");    	
        	system("pause");
    }

四，实验结果。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VzY0ZBSg_size_16_color_FFFFFF_t_70]

2.建立一棵二叉树，求二叉数的树的深度、统计叶子结点的个数、统计总的结点个数、进行层序遍历、交换左右子树等；

#include <iostream>
    using namespace std;
    typedef struct Node
    {
        
        char data;
        struct Node *lchild,*rchild;
    }*BiTree,BiTNode;//定义二叉树结构
    
    void CreateBiTree(BiTree &T)
    {
        
        char ch;
        cin>>ch;
        if(ch=='#') T=NULL;
        else{
        
            T=new BiTNode;
            T->data=ch;
            CreateBiTree(T->lchild);
            CreateBiTree(T->rchild);
        }//先序创建二叉树
    }
    void InOrderTraverse(BiTree T)
    {
        
        if(T)
        {
        
            InOrderTraverse(T->lchild);
            cout<<T->data;
            InOrderTraverse(T->rchild);
        }//中序遍历
    }
    void PreOrderTraverse(BiTree T)
    {
        
        if(T)
        {
        
            cout<<T->data;
            PreOrderTraverse(T->lchild);
            PreOrderTraverse(T->rchild);
        }//先序遍历
    }
    void PostOrderTraverse(BiTree T)
    {
        
        if(T)
        {
        
            PostOrderTraverse(T->lchild);
            PostOrderTraverse(T->rchild);
            cout<<T->data;
        }//后序遍历
    }
    void Copy(BiTree T,BiTree &NewT)
    {
        
        if(T==NULL){
        
            NewT=NULL;
            return;
        }else
        {
        
            NewT=new BiTNode;
            NewT->data=T->data;
            Copy(T->lchild,NewT->lchild);
            Copy(T->rchild,NewT->rchild);
        }
    }//二叉树的复制
    int Depth(BiTree T)
    {
        
        if(T==NULL)
            return 0;
        else
        {
        
            int m=Depth(T->lchild);
            int n=Depth(T->rchild);
            if(m>n) return (m+1);
            else return (n+1);
        }
    }//树的深度
    int NodeCount(BiTree T)
    {
        
        if(T==NULL) return 0;
        else return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
    }//统计二叉树中结点的个数
    int LeafCount(BiTree T)//统计二叉树中叶子结点的个数
    {
        
        if(!T) return 0;
        if(!T->lchild &&!T->rchild)
    	{
        
            return 1;
        }else{
        
            return LeafCount(T->lchild)+LeafCount(T->rchild);
        }
    }
    int Node_1_Count(BiTree T)
    {
        
        if(!T) return 0;
        if((!T->lchild)&&(T->rchild)||(T->lchild)&&(!T->rchild))
            return 1;
        else
            return LeafCount(T->lchild)+LeafCount(T->rchild);
    }//统计二叉树的度为1的结点个数
    void PrintAllPath(BiTree T, char path[], int pathlen)
    {
        //二叉树中从每个叶子结点到根结点的路径
      int i;
      if(T != NULL) {
        
        path[pathlen] = T->data; //将当前结点放入路径中
    if(T->lchild == NULL && T->rchild == NULL)
     {
         
            for(i = pathlen; i >= 0; i--)
                cout << path[i] << " " ;
          cout << endl;
        }else{
        
          PrintAllPath(T->lchild, path, pathlen + 1);
          PrintAllPath(T->rchild, path, pathlen + 1);
        }
      }
    }
    void ExChangeTree(BiTree &T)
    {
                                   //构造函数，使用递归算法进行左右结点转换
        BiTree temp;
        if(T!=NULL){
        
            temp=T->lchild;
            T->lchild=T->rchild;  //直接交换节点地址
            T->rchild=temp;
            ExChangeTree(T->lchild);
            ExChangeTree(T->rchild);
        }//判断T是否为空，非空进行转换，否则不转换
    }
    void DblOrderTraverse(BiTree T)
    {
        
        if(T)
        {
        
            cout<<T->data;
            DblOrderTraverse(T->lchild);
            cout<<T->data;             //访问两遍
            DblOrderTraverse(T->rchild);
        }
    }//二叉树的双序遍历
    int main()
    {
        
        BiTree T;
        //测试例子AB#CD##E##F#GH###
        cout<<"先序遍历输入(以#结束):";
        CreateBiTree(T);
        cout<<"中序遍历输出:";
        InOrderTraverse(T);
        cout<<endl<<"先序遍历输出:";
        PreOrderTraverse(T);
        cout<<endl<<"后序遍历输出:";
        PostOrderTraverse(T);
        cout<<endl<<"树的深度:"<<Depth(T);
        cout<<endl<<"结点的个数:"<<NodeCount(T);
        cout<<endl<<"叶结点的个数:"<<LeafCount(T);
        cout<<endl<<"度为1的结点个数:"<<Node_1_Count(T);
        cout<<endl<<"二叉树中从每个叶子结点到根结点的所有路径："<<endl;
        char path[256];
        int pathlen=0;
        PrintAllPath(T,path,pathlen);//
        //交换二叉树每个结点的左孩子和右孩子
        BiTree tem=T;//直接复制一颗树，在不改变原树的前提下，对临时树进行交换。
        ExChangeTree(tem);
        cout<<"先序遍历输出交换后的结果:";
        PreOrderTraverse(tem);
        cout<<endl<<"双序遍历输出:";
        DblOrderTraverse(T);
        return 0;
    }

四，实验结果  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VzY0ZBSg_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VzY0ZBSg_size_16_color_FFFFFF_t_70]: /images/20221124/c797a9f0516e43d0a38af958f6c35f8a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VzY0ZBSg_size_16_color_FFFFFF_t_70 1]: /images/20221124/9de0107e81724ddb820da7d4b26f7a16.png