二叉树

二叉树抽象数据类型|二叉树实现代码|二叉树C/C++实现代码!

其广义表为：A(B(C),D(E(F,G),H(,I)))
[cpp]
/*算法参考《数据结构实用》教程第二版*/
/*根据广义表建立二叉树*/
struct BTreeNode
{
ElemType data;
BTreeNode *left;
BTreeNode *right;
};
void InitBTree(BTreeNode *&BT) //初始化二叉树
{
BT=NULL;
}
void CreateBTree(BTreeNode *&BT,char *a) //建立二叉树
{
const int Maxsize=10; //栈数组长度要大于等于二叉树的深度减1
BTreeNode *s[Maxsize]; //s数组作为栈,存储根节点指针
int top=-1; //top为栈顶指针，-1表示空栈
BT=NULL; //空树
BTreeNode *p; //p为指向二叉树结点的指针
int k; //k=1处理左子树,k=2处理右子树
int i; //i扫描数组a中储存的广义表字符串
while(a[i])
{
switch(a[i])
{
case ‘ ‘: break;
case ‘(‘: top++;s[top]=p;k=1;break;
case ‘)’: top–;break;
case ‘,’: k=2;break;
default: p=new BTreeNode;
p->data=a[i];p->left=p->right=NULL;
if(BT=NULL) BT=p;
else{
if(k==1) s[top]->left=p;
else s[top]->right=p;
}
}
i++;
}
}
bool EmptyBTree(BTreeNode *BT) //检查二叉树是否为空
{
return BT==NULL;
}
int DepthBTree(BTreeNode *BT)
{
if(BT==NULL) return 0;
else{
int dep1=DepthBTree(BT->left)+1;
int dep2=DepthBTree(BT->right)+1;
if(dep1>dep2) return dep1+1;
else return dep2+1;
}
}
bool FindBTree(BTreeNode *BT,ElemType &x) //查找元素x
{
if(BT=NULL) return false;
else{
if(BT->data==x)
{
x=BT->data;
return true;
}
else
{
if(FindBTree(BT->left,x)) return true;
if(FindBTree(BT->right,x)) return true;
return false;
}
}
}
void ClearBTree(BTreeNode *&BT) //清空二叉树
{
if(BT!=NULL)
{
ClearBTree(BT->left);
ClearBTree(BT->right);
delete BT;
BT=NULL;
}
}
void PrintBTree(BTreeNode *BT) //递归遍历
{
if(BT!=NULL)
{
cout<<BT->data;
if(BT!=NULL||BT->right!=NULL)
{
cout<<“(“;
PrintBTree(BT->left);
if(BT->right!=NULL)
cout<<‘,’;
PrintBTree(BT->right);
cout<<“)”;
}
}
}
[/cpp]