Status ListDelete-Sq（SqList &L，int i，ElemType &e）{ if（(i<1）||（i>L.length)） return ERROR;
p=&(L.elem[i-1]);
e=*p;
q=L.elem+L.length-1；
for(++p;p<=q;++p)*(p-1)=*p;
- -L.length;
return OK；
}
第二篇：二叉树的建立、输出、结点、高度、叶结点的输出
7 二叉树的操作
【实验简介】二叉树是树形结构的一种重要类型。通过本次实验，熟悉二叉树结点的结构，掌握二叉树的基本操作以及具体实现，学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。
【实验内容】
编写程序，实现对二叉树的以下操作：
1． 建立二叉树。
2． 按任一种遍历次序输出二叉树中的所有结点。
3． 求二叉树的深度。
4． 求二叉树中的所有节点数。
5． 求二叉树中的所有叶子节点数。
6． 清除二叉树，使之编程一只空树。
【主要代码】#include<iostream>
using namespace std;
template <class T>
struct BinTreeNode //二叉树结点类定义
{ T data; //数据域
BinTreeNode<T> *leftChild, *rightChild; //左子女、右子女链域 BinTreeNode () //构造函数
{ leftChild=NULL;rightChild=NULL; }
BinTreeNode (T x,BinTreeNode<T> *left=NULL,BinTreeNode<T> *right=NULL)
{ data=x; leftChild=left;rightChild=right; }
};
template <class T>
class BinaryTree
{ //二叉树类定义
public:
BinaryTree() {root=NULL;} //构造函数
BinaryTree (T value) //构造函数 {RefValue=value;root=NULL;}
~BinaryTree(){destroy(root);} //析构函数
bool IsEmpty(){ return root==NULL;} //判二叉树空否
int Height(){ return Height(root);} //求树高度
int Size() { return Size(root); } //求结点数
BinTreeNode<T> *getRoot() { return root; }
BinTreeNode<T> *LeftChild (BinTreeNode<T> *cur) //返回左子女 { return (cur!=NULL)?cur->leftChild:NULL; } BinTreeNode<T> *RightChild (BinTreeNode<T> *cur) //返回右子女 { return (cur!=NULL)?cur->rightChild:NULL; }
void Output (BinTreeNode<T> * subtree); //输出结点 void BinaryTreeCount(BinTreeNode<T>* BT,int& m1,int& m2); 输出结点数和叶结点数
1 //
void SetRefValue(T& M){RefValue=M;} //设置数据输入停止标志
void Setroot(BinTreeNode<T>* N){root=N;} //设置根节点 void CreateBinTree (BinTreeNode<T> *& subTree);
protected:
BinTreeNode<T> *root; //二叉树的根指针
T RefValue; //数据输入停止标志
//void CreateBinTree (istream& in, BinTreeNode<T> *& subTree); //从文件读入建树
void destroy (BinTreeNode<T> *& subTree); //删除
int Height (BinTreeNode<T> *subTree)const; //返回树高度
int Size(BinTreeNode<T> *subTree)const; //返回结点数
BinTreeNode<T> *Parent (BinTreeNode<T> * subTree, BinTreeNode<T> *cur); //返回父结点
friend ostream& operator<<(ostream& out,BinaryTree<T>& Tree); };
template<class T>
void BinaryTree<T>::destroy (BinTreeNode<T> *& subTree)
//私有函数: 删除根为subTree的子树
{ if (subTree!=NULL)
{ destroy (subTree->leftChild); //删除左子树
destroy (subTree->rightChild); //删除右子树
delete subTree; //删除根结点
}
};
template <class T>
void BinaryTree<T>::CreateBinTree(BinTreeNode<T> *& subTree) { T item;
cin>>item; //读入根结点的值
if(item!=RefValue)
{ subTree=new BinTreeNode<T>(item); //建立根结点 if (subTree==NULL)
{cerr << "存储分配错!" << endl; exit (1);}
CreateBinTree (subTree->leftChild); //递归建立左子 CreateBinTree (subTree->rightChild);//递归建立右子树 }
else {subTree=NULL;} //封闭指向空子树的指针
};
template <class T>
int BinaryTree<T>::Height(BinTreeNode<T> *subTree)const
{ //私有函数：利用二叉树后序遍历算法计算二叉树的高度或深度； if (subTree==NULL) return 0; //空树高度为0；
else
2
{
int i=Height(subTree->leftChild);
int j=Height(subTree->rightChild);
return (i<j)?j+1:i+1;
}
};
template <class T>
void BinaryTree<T>::BinaryTreeCount(BinTreeNode<T>* BT,int& m1,int& m2)
//分别统计出二叉树中所有结点数和叶子结点数
{
if(BT!=NULL)
{ m1++; //统计所有结点
if(BT->leftChild==NULL&&BT->rightChild==NULL) m2++; //统计叶子结点数
BinaryTreeCount(BT->leftChild,m1,m2);
BinaryTreeCount(BT->rightChild,m1,m2);
}
else return;
return;
};
template <class T>
void BinaryTree<T>::Output (BinTreeNode<T> *subtree)
{//私有函数：利用二叉树后序遍历算法输出二叉树的结点
if (subtree!=NULL)
{
cout<<subtree->data<<'\t'; //输出根节点
Output(subtree->leftChild); //遍历
Output(subtree->rightChild);
}
return;
};
void main()
{
BinaryTree<int> a;
int m=0,n=0,p=0;
BinTreeNode<int> *b;
b=a.getRoot();
a.SetRefValue(p); //设置结束标志
cout<<"请输入要建立的二叉树的整型数,输入0结束，0应比数字多1："; a.CreateBinTree(b); //创建二叉树
cout<<"二叉树的所有结点为：";
a.Output(b);
3
cout<<'\n'; //输出所有结点
a.Setroot(b);
cout<<"二叉树的高度为：";
cout<<a.Height()<<'\n'; //输出二叉树高度 a.BinaryTreeCount(b,m,n); //输出结点数和叶子结点数
cout<<"二叉树结点数为："<<m<<'\n'; //结点和叶结点个数输出
cout<<"二叉树叶结点数为："<<n<<'\n';
a.~BinaryTree(); //删除二叉树
exit(1);
}
//退出 4