数据结构测试题(树的相关操作) | 您所在的位置:网站首页 › 234树的创建 › 数据结构测试题(树的相关操作) |
假设二叉树的数据元素为字符,采用二叉链式存储结构。二叉树ADT实现的大部分代码已经给出,其中采用完全前序序列创建二叉树。请补充写出下列两个操作函数。 注意: 答案区只写出两个函数,其他代码不允许修改和重写、提交! (1)计算以某结点为根的二叉树的高度; (2)以前序顺序输出各个元素结点为根的子树的高度; 例如:有如右图的二叉树 输入:ABD@@E@@C@F@@ 输出: Height(A)=3 Height(B)=2 Height(D)=1
Height(E)=1 Height(C)=2 Height(F)=1 已给出的代码如下: #include #include 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; } ///答案需要补充的代码,递归求解树的高度, int BinaryTree::height(TreeNode* t) { if(t==NULL) return 0; int a=height(t->lson); int b=height(t->rson); return max(a,b)+1; } ///线序遍历输出树的高度 void BinaryTree::Pro_height(TreeNode* t) { if(t==NULL) return ; cout |
CopyRight 2018-2019 实验室设备网 版权所有 |