一、实验目的

1、熟练理解树和二叉树的相关概念，掌握的存储结构和相关操作实现；

2、掌握树的顺序结构的实现；

3、学会运用树的知识解决实际问题

二、实验内容

1、自己确定一个二叉树（树结点类型、数目和结构自定）利用链式存储结构方法存储。实现树的构造，并完成：

1）用前序遍历、中序遍历、后序遍历输出结点数据；

2）以合理的格式，输出各个结点和双亲、孩子结点信息；

3）输出所有的叶子结点信息；

2、试设计一个程序，将输入的字符串转化为对应的哈夫曼编码，然后再将这个哈夫曼编码序列进行解码，也就是恢复原来的字符串序列。（*）

三、实验步骤

1、依据实验内容，先确定具体的二叉树，并说明结点的数据类型；

2、设计具体的算法；

3、写出完整程序；

4、总结、运行结果和分析算法效率。

5、总体收获和不足，疑问等。

四、实验要求

1、按照数据结构实验任务书，提前做好实验预习与准备工作。

2、在个人主页上发文章提交作业。

3、实验课会抽查3-5人，希望你可以被查到！

五、源代码

#include
     
     
      
      
using namespace std;

typedef struct node
{
	struct node *leftChild;
	struct node *rightChild;
	char data;
}BiTreeNode, *BiTree;


BiTreeNode *createnode(char c)
{
	BiTreeNode *q=new BiTreeNode;
	q->leftChild=NULL;
	q->rightChild=NULL;
	q->data=c;
	return q;
}

void createBiTree(BiTree &T)
{
	char c;
	cin >> c;
	if(c == '#')
		T = NULL;
	else
	{
		T = new BiTreeNode;
		T->data = c;
		createBiTree(T->leftChild);
		createBiTree(T->rightChild);
	}
}


int max(int a, int b )
{
	return a < b ? b : a;
}


int Depth(BiTree T)
{
	if ( T== NULL)
		return 0;
 
	int leftDepth = Depth(T->leftChild);
	int rightDepth = Depth(T->rightChild);

	return 1+ max(leftDepth, rightDepth);
}


void PrintNodeatlevel(BiTree T,int level)
{
	if(T==NULL || level<1)
		return;
	if(level==1)
	{
		cout<
      
      
       
       data<<" ";
		return;
	}
	PrintNodeatlevel(T->leftChild,level-1);
	PrintNodeatlevel(T->rightChild,level-1);
}


void LevelTraverse(BiTree T)
{
	if(T==NULL)
		return;
	int depth=Depth(T);
	for(int i=1;i<=depth;i++)
	{
		PrintNodeatlevel(T,i);
		cout<
       
       
        
        leftChild==NULL && T->rightChild==NULL)
		{
			cout<
        
        
         
         data<<" ";
		}
		LeavesTraverse(T->leftChild);
		LeavesTraverse(T->rightChild);
}


int getleafnode(BiTree T)
{
	if(T==NULL)
		return 0;
	if(T->leftChild==NULL && T->rightChild==NULL)
		return 1;
	return getleafnode(T->leftChild)+getleafnode(T->rightChild);
}


int getallnode(BiTree T)
{
	if(T==NULL)
		return 0;
	return 1+getallnode(T->leftChild)+getallnode(T->rightChild);
}

	
BiTreeNode *parent(BiTreeNode *T,char c)
{
	if(T==NULL)
		return NULL;
	if(T->leftChild!=NULL && T->leftChild->data==c)
	{
		return T;
	}
	if(T->rightChild!=NULL && T->rightChild->data==c)
	{
		return T;
	}
	BiTreeNode *p=parent(T->leftChild,c);
	if(p!=NULL)
	{
		return p;
	}
	p=parent(T->rightChild,c);
	return p;
}


BiTreeNode *children(BiTreeNode *T,char c)
{
	if(T==NULL)
		return NULL;
	if(T->data==c)
	{
		if(T->leftChild!=NULL && T->rightChild!=NULL)
			cout<<"左孩子:"<
         
         
           leftChild->data< 
          
            <<"右孩子:"< 
           
             rightChild->data< 
            
              leftChild==NULL && T->rightChild!=NULL) cout<<"左孩子为空！"< 
             
               <<"右孩子:"< 
              
                rightChild->data< 
               
                 leftChild!=NULL && T->rightChild==NULL) cout<<"左孩子:"< 
                
                  leftChild->data< 
                 
                   <<"右孩子为空！"< 
                  
                    leftChild==NULL && T->rightChild==NULL) cout<<"没有孩子!"< 
                   
                     leftChild,c); if(p!=NULL) { return p; } p=children(T->rightChild,c); return p; } void preorder(BiTree T) { if(T==NULL)return; if(T!=NULL) { cout< 
                    
                      data<<" "; preorder(T->leftChild); preorder(T->rightChild); } } void inorder(BiTree T) { if(T==NULL)return; if(T!=NULL) { inorder(T->leftChild); cout< 
                     
                       data<<" "; inorder(T->rightChild); } } void postorder(BiTree T) { if(T==NULL)return; if(T!=NULL) { postorder(T->leftChild); postorder(T->rightChild); cout< 
                      
                        data<<" "; } } // ----------------------------------------------------------------------------------------------- int main() { BiTree T; char x; BiTreeNode *p; cout<<"输入一棵树:"; createBiTree(T); cout< 
                       
                         >x; p=parent(T,x); if(p!=NULL) { cout<<"双亲:"< 
                        
                          data; } else cout<<"找不到双亲!"; cout< 
                         
                           < 
                          
                            >x; p=children(T,x); cout<


输入如图所示二叉树


六、运行结果


七、心得
在二叉树的顺序结构的实现中，我用了一维数组来存储实现，根据双亲与孩子之间的关系来求得双亲信息或者孩子信息，在二叉树的链式存储中，定义了左孩子和右孩子两个结点指针，在层序输出二叉树时，用了我在网上看到的一个方法，就是用递归的方法，根据二叉树的层级来输出二叉树，将根结点定为第一层，左子树与右子树的层级依次增加，从而使二叉树层序输出；在求双亲与孩子时，一开始由于对条件判定的不完全而导致频频出错，差点想要放弃，后来经过不断的调试，最终使程序成功运行，很开心。

原文链接：https://blog.csdn.net/weixin_40132866/article/details/78451010

一、实验目的

二、 实验内容

四、实验要求

二、实验内容