实现二叉树各种基本操作的算法
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<>
using namespace std;
#define maxsize 100
typedef char elemtype;
typedef struct node
{
elemtype data;
struct node* lchild;
struct node* rchild;
}btnode;
void creatbtree(btnode* &b, string str)
{
btnode *st[maxsize], *p;
int top = -1, k, j = 0;
char ch;
b = NULL;//建立二叉树初始为空
ch = str[j];
while (ch != '\0')//栈
{
switch(ch)
{
case '(':top++; st[top] = p; k = 1; break;//处理左子树
case ')':top--; break;//子树处理完毕
case ',':k = 2; break;//处理右子树
default:p = (btnode*)malloc(sizeof(btnode));
p->data = ch;
p->lchild = p->rchild = NULL;
if (b == NULL)
b = p;
else
{
switch (k)
{
case 1:st[top]->lchild = p; break;
case 2:st[top]->rchild = p; break;
}
}
}
j++; ch = str[j];
}
}
void destroybtree(btnode* &b)
{
if (b != NULL)
{
destroybtree(b->lchild);
destroybtree(b->rchild);
}
}
btnode* findnode(btnode *b, elemtype x)//查找值为x的结点
{
btnode *p;
if (b == NULL)
{
return NULL;
}
else if (b->data == x)
return b;
else
{
p = findnode(b->lchild, x);
if (p != NULL)
return p;
else
return findnode(b->rchild, x);
}
}
btnode* lchildnode(btnode *p)
{
return p->lchild;
}
btnode* rchildnode(btnode *p)
{
return p->rchild;
}
void dispbtree(btnode *b)
{
if (b != NULL)
{
printf("%c",b->data);
if (b->lchild != NULL || b->rchild != NULL)
{
printf("(");
dispbtree(b->lchild);
if (b->rchild != NULL)
printf(",");
dispbtree(b->rchild);
printf(")");
}
}
}
int btheight(btnode *b)
{
int lchildh,rchildh;
if(b==NULL)
return 0;
else{
lchildh=btheight(b->lchild);
rchildh=btheight(b->rchild);
return (lchildh>rchildh)?(lchildh+1):(rchildh+1);
}
}
int main()
{
btnode *b, *p, *lp, *rp;
cout << "二叉树的基本运算如下：" << endl;
cout << "创建二叉树：" << endl;
string s="A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))";
creatbtree(b,s);
dispbtree(b);
cout<<endl;
cout<<"H节点"<<endl;
p=findnode(b,'H');
if(p!=NULL)
{
lp=lchildnode(p);
if(lp!=NULL)
cout<<"左孩子："<<lp->data;
else
cout<<"无左孩子"<<endl;
rp=rchildnode(p);
if(rp!=NULL)
{
cout<<"右孩子:"<<rp->data<<endl;
}
else
cout<<"无右孩子"<<endl;
}
cout<<endl;
cout<<"二叉树高度："<<endl;
int h=btheight(b);
cout<<h<<endl;
cout<<"释放二叉树"<<endl;
destroybtree(b);
return 0;
}