删除子树实验报告总结

删除子树实验报告总结（共1篇）

篇1：删除子树实验报告总结

一 实验目的和要求

理解二叉树的基本概念，熟练使用多种表示法构造二叉树，掌握采用二叉链表存储结构实现二叉树的构造、遍历、插入、删除等操作算法；理解线索二叉树的作用，掌握获得线索二叉树节点在指定遍历次序下的前驱或后继结点的方法；理解哈弗曼编码和哈弗曼树的作用，掌握由指定文本求得哈弗曼编码的方法。

理解树的基本概念，熟悉树的多种存储结构，掌握采用孩子兄弟链表存储结构实现树的遍历、插入、删除等操作算法。

通过研究树和二叉树，深刻理解链式存储结构用于表达非线性结构的作用，掌握采用递归算法实现递归数据结构基本操作的设计方法。二 题目及题意分析

题目：删除以P的第I个孩子为根的子树。

分析：用孩子兄弟链表构造一棵树，将树转化成二叉树，由根的sibling链将若干棵树连接成一棵二叉树，构造removechild（TreeNode*p,int i）函数实现操作，若p指针为空或者是i超出范围怎溢出错，否则，当删除第一个孩子为根的子树时，p的孩子指针指向原孩子指针的兄弟结点删除p的原孩子子树。若删除的为中间或最后子树，用循环语句找到要删除的子树，并使用指针temp记住该子树的前一个结点，将temp的兄弟指针指向要删除子树的兄弟结点，删除子树。三 设计方案和功能说明

源程序如下： Treenode.h

template class TreeNode

结点类 { public:

T data;

TreeNode*child,* sibling;

TreeNode(T data)

{

this->data=data;

this->child=this->sibling=NULL;

} };Tree.h #include #include“TreeNode.h” template class Tree { public:

TreeNode*root;

Tree();

TreeNode*insertchild(TreeNode*p,T value);

friend ostream&operator<<(ostream&out,Tree&tree);

输出流

void removechild(TreeNode*p,int i);

删除子树函数

private:

void preOrder(TreeNode*p,int i);

void destroy(TreeNode*p);

释放

};template Tree::Tree(){ root=NULL;} template TreeNode*Tree::insertchild(TreeNode*p,T value)

{ TreeNode*q=NULL;if(p!=NULL){

q=new TreeNode(value);

if(p->child==NULL)

p->child=q;

else

{

p=p->child;

while(p->sibling!=NULL)

p=p->sibling;

p->sibling=q;

} }

return q;} template ostream&operator<<(ostream&out,Tree&tree){ tree.preOrder(tree.root,0);return out;} template void Tree::preOrder(TreeNode*p,int i)

输出 { if(p!=NULL)

插入结点

{

for(int j=0;j

cout<<“t”;

cout<

data<

preOrder(p->child,i+1);

preOrder(p->sibling,i);

}

} template void Tree::destroy(TreeNode*p){ if(p!=NULL){

destroy(p->child);

destroy(p->sibling);

delete p;} } template

void Tree::removechild(TreeNode*p,int i)

{ if(p==NULL||i==0)

cout<<“参数错误”<

溢出错

else { TreeNode*temp=p;

头子树删除

if(i==1)

{

temp=p->child;

p->child=p->child->sibling;

destroy(temp->child);

delete temp;

}

else

{

p=p->child;

for(int j=1;j

{

temp=p;

记住前一个结点

p=p->sibling;

}

destroy(p->child);

temp->sibling=temp->sibling->sibling;

删除子树

链接

delete p;

}

} } 主函数

#include“Tree.h”

int main(){ Tree tree;TreeNode *q=NULL;tree.root=new TreeNode(“中国”);

tree.insertchild(tree.root,“北京”);tree.insertchild(tree.root,“上海”);TreeNode *js=tree.insertchild(tree.root,“江苏省”);tree.insertchild(js,“南京市”);tree.insertchild(js,“苏州市”);TreeNode*zj=tree.insertchild(tree.root,“浙江省”);tree.insertchild(zj,“杭州市”);tree.insertchild(zj,“宁波市”);

TreeNode *hn=tree.insertchild(tree.root,“河南省”);tree.insertchild(hn,“郑州市”);tree.insertchild(hn,“新乡市”);

cout<

调用

cout<

} 四 运行结果及分析

1删除第一个子树 中国

北京

上海

江苏省

南京市

苏州市

浙江省

杭州市

宁波市

河南省

郑州市

构造一棵树

新乡市

中国

上海

江苏省

南京市

苏州市

浙江省

杭州市

宁波市

河南省

郑州市

新乡市 Press any key to continue 2 删除中间子树 中国

北京

上海

江苏省

南京市

苏州市

浙江省

杭州市

宁波市

河南省

郑州市

新乡市 中国

北京

上海

江苏省

南京市

苏州市

河南省

郑州市

新乡市 Press any key to continue 3 p为空时 中国

北京

上海

江苏省

南京市

苏州市

浙江省

杭州市

宁波市

河南省

郑州市

新乡市 参数错误

Press any key to continue 结果分析：构造一棵树，调用函数removechild，给定不同的指针及i值运行结果正确，删除成功，考虑p为空及i超出范围，溢出错。

五 实验总结

通过实验理解了树及二叉树的存储结构熟悉掌握了孩子兄弟链表的存储结构实现，以及遍历、查找、删除等操作，深刻理解实现链式存储结构表达非线性的树存储结构。