数据结构第三次测试

数据结构测试，树部分，水题

一

假设二叉树的数据元素为字符，采用二叉链式存储结构。二叉树ADT实现的大部分代码已经给出，其中采用完全前序序列创建二叉树。请补充写出下列两个操作函数。

注意：答案区只写出两个函数，其他代码不允许修改和重写、提交！

计算以某结点为根的二叉树的高度；
以前序顺序输出各个元素结点为根的子树的高度；

例如：有如右图的二叉树

输入

ABD@@E@@C@F@@

输出

Height(A)=3
Height(B)=2
Height(D)=1
Height(E)=1
Height(C)=2
Height(F)=1

已给出的代码如下：

#include <iostream>
#include <stdlib.h>
using namespace std;
//数据元素类型
typedef char ElemType;
//二叉树结点定义
typedef struct TreeNode
{	ElemType data;
	struct TreeNode *lson, *rson;
} TreeNode;
//二叉树类
class BinaryTree
{  private:
	TreeNode *root;
   public:
	BinaryTree() { root = NULL; };
	~BinaryTree() { MakeEmpty(root); }
	void MakeEmpty(TreeNode *t);
	void create( ) { root = cp_create(root); };  //完全前序建立二叉树，空指针用@表示
	TreeNode *cp_create(TreeNode *t);
	
	//******  要补充的函数height ********
	int height(TreeNode *t) ;    //求二叉树的高度
	void output() { Pro_height(root); };
	//******  要补充的函数 Pro_height **********
	void Pro_height(TreeNode *t);  // 前序顺序输出各个元素结点为根的子树的高度      
};
//二叉树置空
void BinaryTree::MakeEmpty(TreeNode *t)
{	if (t != NULL)
	{	MakeEmpty(t->lson);
		MakeEmpty(t->rson);
		delete t;
	}
}
//完全前序序列创建二叉树，空指针用@表示
TreeNode *BinaryTree::cp_create(TreeNode *t)
{	ElemType v;
	cin >> v;
	if (v != '@')
	{	t = new TreeNode;
		t->data = v;
		t->lson = cp_create(t->lson);
		t->rson = cp_create(t->rson);
	}
	else t = NULL;
	return t;
}
//********************  需要补充写出的两个函数  ****************************
//*******************************************************************************
//主函数
int main()
{	BinaryTree t;
	t.create();
	t.output();	
	return 0;
}

Answer

求树高度，递归。貌似没有必要判断lson和rson是否为空，不过凑合着吧……

int BinaryTree::height(TreeNode* t)
{
    if(t==NULL){
        return 0;
    }
    int l=0,r=0;
    if(t->lson!=NULL){
        l=height(t->lson);
    }
    if(t->rson!=NULL){
        r=height(t->rson);
    }
    return max(l,r)+1;
}
void BinaryTree::Pro_height(TreeNode* t)
{
    if(t==NULL){
        return;
    }
    cout<<"Height("<<t->data<<")="<<height(t)<<endl;
    Pro_height(t->lson);
    Pro_height(t->rson);
}

二

假设二叉树的数据元素为字符，采用二叉链式存储结构。二叉树ADT实现的大部分代码已经给出，其中二叉树采用完全前序序列创建。请补充一个二叉树的输出函数，要求按目录缩进的形式输出一棵二叉树，同时要输出目录的层次。层次占2位、元素占1位，间隔4个位置（即共占7个位置）。

注意：答案区只写指定补充的函数代码，其他给定的代码不允许重写、修改和提交！例如：有如右图的二叉树

输入

ABD@@E@@C@F@@

输出：

给出的代码如下：

#include <iostream>
#include <stdlib.h>
#include<stdio.h>
using namespace std;
//数据元素类型
typedef char ElemType;
//二叉树结点定义
typedef struct TreeNode
{	ElemType data;
	struct TreeNode *lson, *rson;
} TreeNode;
//二叉树类
class BinaryTree
{ private:
	TreeNode *root;
  public:
	BinaryTree() { root = NULL; };
	~BinaryTree() { MakeEmpty(root); }
	void MakeEmpty(TreeNode *t);
	void create( ) { root = cp_create(root); };  //完全前序建立二叉树，空指针用@表示
	TreeNode *cp_create(TreeNode *t);
	void output( ) { Index_print(root,1); };
	//*********** 下面是需要自己完成的函数 ******************   
	void Index_print(TreeNode *t,int l);  //缩进目录形式输出二叉树      
};
//二叉树置空
void BinaryTree::MakeEmpty(TreeNode *t)
{	if (t != NULL)
	{	MakeEmpty(t->lson);
		MakeEmpty(t->rson);
		delete t;
	}
}
//完全前序序列创建二叉树，空指针用@表示
TreeNode *BinaryTree::cp_create(TreeNode *t)
{	ElemType v;
	cin >> v;
	if (v != '@')
	{	t = new TreeNode;
		t->data = v;
		t->lson = cp_create(t->lson);
		t->rson = cp_create(t->rson);
	}
	else t = NULL;
	return t;
}
//*****下面是要补充的函数Index_print  *************
//*************************************************
//主函数
int main()
{	BinaryTree t;
	t.create();      //创建二叉树
	t.output();       //按规定格式输出二叉树
	cout<< endl;
	return 0;
}

Answer

完全前序遍历，递归，注意输出格式。

void BinaryTree::Index_print(TreeNode* t, int l)
{
    if(t==NULL){
        return;
    }
    cout<<' ';
    for(int i=0;i<l-1;i++){
        cout<<"       ";
    }
    cout<<l<<t->data<<endl;
    Index_print(t->lson,l+1);
    Index_print(t->rson,l+1);
}

最后修改于 2019-06-01