数据结构练习题:假设二叉树的数据元素为字符，采用二叉链式存储结构。二叉树ADT实现的大部分代码已经给出，其中二叉树采用完全前序序列创建。请补充一个二叉树的输出函数，要求按目录缩进的形式输出一棵二叉树，

题目描述如下：
假设二叉树的数据元素为字符，采用二叉链式存储结构。二叉树ADT实现的大部分代码已经给出，其中二叉树采用完全前序序列创建。请补充一个二叉树的输出函数，要求按目录缩进的形式输出一棵二叉树，同时要输出目录的层次。层次占2位、元素占1位，间隔4个位置（即共占7个位置）。 注意：答案区只写指定补充的函数代码，其他给定的代码不允许重写、修改和提交！
例如：有如右图的二叉树

输入：ABD@@E@@C@F@@

输出：

	1A2B3D3E2C3F			

或者输出

输出：

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

给出的代码如下：#include #include #includeusing 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;}

补充函数：

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

对于第二问

	//******  要补充的函数height ********int height(TreeNode *t) ;    //求二叉树的高度void output() { Pro_height(root); };//******  要补充的函数 Pro_height **********void Pro_height(TreeNode *t);  // 前序顺序输出各个元素结点为根的子树的高度  

补充函数
1.错误示范 未掌握递归的精神
2.改良

void BinaryTree::Pro_height(TreeNode *t){
//错误示范未考虑到空树，直接根节点就是NULL
//检查无问题  debug一小时最后才想到，缺少思维严谨度cout<<"Height("<<t->data<<")="<<height(t)<<endl;if(t->lson) 	 Pro_height(t->lson);if(t->rson) 	 Pro_height(t->rson);
}
//   ABDPDRQ@@@@@@E@@C@F@YM@U@@@
//@
int BinaryTree::height(TreeNode *t ){if(!t ) return 0;else return  
(height(t->lson) > height(t->rson) ? height(t->lson):height(t->rson))+1;}

改正：

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

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！