数据结构练习题:假设二叉树的数据元素为字符 采用二叉链式存储结构。二叉树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 <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;}

补充函数：

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 ;}

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