实现二叉树各种基本操作的算法

时间:2025-03-14 08:07:54
#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; }