struct BiNode{
char data;
BiNode *lchild;
BiNode *rchild;
};
类的声明
class Bitree{
public:
Bitree(){root=creat(root);}
~Bitree(){Release(root);}
void Preorder(){Preorder(root);}
void inorder(){inorder(root);}
void Postorder(){Postorder(root);}
void Leverorder(){Leverorder(root);}
private:
BiNode* creat(BiNode *bt);
void Release(BiNode *bt);
void Preorder(BiNode* bt);
void inorder(BiNode* bt);
void Postorder(BiNode* bt);
void Leverorder(BiNode* bt);
BiNode *root;
};
类的实现
构造函数
使用对象时，调用构造函数，进入creat函数。
Bitree(){root=creat(root);}
运行时，输入前序遍历序列建树，键盘缓冲区会存储输入的字串。
BiNode* Bitree::creat(BiNode *bt){
char ch;
cin>>ch;
if(ch=='#') bt=NULL;
else{
bt=new BiNode;
bt->data=ch;
bt->lchild=creat(bt->lchild);
bt->rchild=creat(bt->lchild);
}
return bt;
}
遍历
二叉树的基本操作都基于遍历。因此，遍历是二叉树的重点！
前中后序都应检查传入的节点是否为空，若已空，返回；若非空，按照顺序递归输出。
前序void Bitree::Preorder(BiNode* bt){ //DLR
if(bt==NULL) return;
else {
cout<data;
Preorder(bt->lchild);
Preorder(bt->rchild);
}
}
中序
void Bitree::inorder(BiNode* bt){ //LDR
if(bt==NULL) return;
else {
inorder(bt->lchild);
cout<data;
inorder(bt->rchild);
}
}
后序
void Bitree::Postorder(BiNode* bt){ //LRD
if(bt==NULL) return;
else {
Postorder(bt->lchild);
Postorder(bt->rchild);
cout<data;
}
}
层序
使用队列暂存结点并实现输出。
void Bitree::Leverorder(BiNode* bt){ //层序遍历：一层一层输出（使用队列对父节点和孩子操作）
BiNode *Q[100],*q=NULL;
int front=-1,rear=-1;
if(root==NULL) return ; //空树，跳出创建
Q[++rear]=root; //当前结点先入队
while(front != rear){ //队空时，front=rear。
//队列非空进行下列操作，直到队列为空为止 ：1.队首出队；2.当前结点左右孩子入队
q=Q[++front]; //当前结点出队
cout<data<<" ";
if(q->lchild != NULL) Q[++rear]=q->lchild;
if(q->rchild != NULL) Q[++rear]=q->rchild;
}
}
析构函数
思路：依次释放左右孩子，最后释放根节点
void Bitree::Release(BiNode *bt){
if(bt==NULL) return;
else{
Release(bt->lchild);
Release(bt->rchild);
delete bt;
}
}
完整源码
#includeusing namespace std; struct BiNode{ char data; BiNode *lchild; BiNode *rchild; }; class Bitree{ public: Bitree(){root=creat(root);} ~Bitree(){Release(root);} void Preorder(){Preorder(root);} void inorder(){inorder(root);} void Postorder(){Postorder(root);} void Leverorder(){Leverorder(root);} private: BiNode* creat(BiNode *bt); void Release(BiNode *bt); void Preorder(BiNode* bt); void inorder(BiNode* bt); void Postorder(BiNode* bt); void Leverorder(BiNode* bt); BiNode *root; }; BiNode* Bitree::creat(BiNode *bt){ //输入前序遍历序列建树 char ch; cin>>ch; if(ch=='#') bt=NULL; else{ bt=new BiNode; bt->data=ch; bt->lchild=creat(bt->lchild); bt->rchild=creat(bt->lchild); } return bt; } //前中后序遍历：检查传入的节点是否为空，若已空，返回；若非空，按照顺序递归输出 void Bitree::Preorder(BiNode* bt){ //DLR if(bt==NULL) return; else { cout< data; Preorder(bt->lchild); Preorder(bt->rchild); } } void Bitree::inorder(BiNode* bt){ //LDR if(bt==NULL) return; else { inorder(bt->lchild); cout< data; inorder(bt->rchild); } } void Bitree::Postorder(BiNode* bt){ //LRD if(bt==NULL) return; else { Postorder(bt->lchild); Postorder(bt->rchild); cout< data; } } void Bitree::Leverorder(BiNode* bt){ //层序遍历：一层一层输出（使用队列对父节点和孩子操作） BiNode *Q[100],*q=NULL; int front=-1,rear=-1; if(root==NULL) return ; //空树，跳出创建 Q[++rear]=root; //当前结点先入队 while(front != rear){ //队空时，front=rear。 //队列非空进行下列操作，直到队列为空为止 ：1.队首出队；2.当前结点左右孩子入队 q=Q[++front]; //当前结点出队 cout< data<<" "; if(q->lchild != NULL) Q[++rear]=q->lchild; if(q->rchild != NULL) Q[++rear]=q->rchild; } } void Bitree::Release(BiNode *bt){ //顺序与后序遍历相同：依次释放左右孩子，最后释放根节点 if(bt==NULL) return; else{ Release(bt->lchild); Release(bt->rchild); delete bt; } } int main(){ Bitree t; cout<<"前序遍历："; t.Preorder();cout<
