// 二叉樹.cpp : 定義控制臺應用程序的入口點。
//
/*
*二叉樹作業(yè)
*2012.12.1 13:55
*Made By Karld Vorn Doenitz
*/
#include "stdafx.h"
#include<iostream>
#include<string>
using namespace std;
class TreeNode{//建立節(jié)點類
public:
char num;
TreeNode *leftchild,*rightchild;
};
class Queue{//建立隊列類
public:
int front,rear;
TreeNode *elem;
};
void cmd();
void initQueue(Queue *q);
bool isEmpty(Queue *q);
void enQueue(Queue *q,TreeNode *e);
void outQueue(Queue *q,TreeNode *e);
void createBiTree(TreeNode * &T);
TreeNode* PreFind(TreeNode *T,char da);
void order(TreeNode *T);
void midOrder(TreeNode * T);
void addChild(TreeNode *T,char clue,char add,string side);
void deleteNode(TreeNode *T,char delchar);
int main(){//主函數
cmd();
return 0;
}
void cmd(){//命令函數
/*
*以下為命令行指令
*共有六種命令
*/
char commands;
TreeNode *T=NULL;
cout<<"*"<<"___________命令如下_______________"<<endl;
cout<<"*"<<"1、按下c鍵先序創(chuàng)建二叉樹； "<<"*"<<endl;
cout<<"*"<<"2、按下m鍵中序遞歸遍歷二叉樹； "<<"*"<<endl;
cout<<"*"<<"3、按下o鍵層次遍歷二叉樹； "<<"*"<<endl;
cout<<"*"<<"4、按下s鍵給定元素查找節(jié)點； "<<"*"<<endl;
cout<<"*"<<"5、按下i鍵指定位置插入節(jié)點； "<<"*"<<endl;
cout<<"*"<<"6、按下d鍵刪除指定的節(jié)點； "<<"*"<<endl;
cout<<"*"<<"請輸入你的選擇： "<<"*"<<endl;
cout<<"*"<<"__________________________________"<<endl;
cin>>commands;
while(commands){
/*
*采用switch語句
*while循環(huán)
*/
switch (commands){
case 'c':
{
cout<<"輸入要創(chuàng)建的二叉樹，以#為空節(jié)點。"<<endl;
createBiTree(T);
}break;
case 'm':
{ if(T==NULL)cout<<"此二叉樹為空，請先創(chuàng)建二叉樹!!!"<<endl;
else{
cout<<"中序遍歷二叉樹的結果為：";
midOrder(T);
cout<<endl;}
}break;
case 'o':{
if(T==NULL)cout<<"此二叉樹為空，請先創(chuàng)建二叉樹!!!"<<endl;
else{cout<<"層次遍歷二叉樹的結果為：";
order(T);
cout<<endl;
} }break;
case 's':{char ch;
cout<<"輸入要查找的元素："<<endl;
cin>>ch;
cout<<"要找的節(jié)點的左孩子是：";
TreeNode *bt=PreFind(T,ch);
if(bt->leftchild!=NULL)
cout<<bt->leftchild->num<<endl;
else cout<<"此節(jié)點是葉子，無左孩子!!!"<<endl;
cout<<"要找的節(jié)點的右孩子是：";
if(bt->rightchild!=NULL)
cout<<bt->rightchild->num<<endl;
else cout<<"此節(jié)點是葉子，無右孩子!!!"<<endl;
}break;
case 'i':{char clue,add;
string side;
cout<<"輸入插入位置：";
cin>>clue;
cout<<"輸入插入的元素:";
cin>>add;
cout<<"選擇要插入的是左子樹(請輸入left)還是右子樹(請輸入right)";
cin>>side;
addChild(T,clue,add,side);
}break;
case 'd':{
char del;
cout<<"輸入要刪除的節(jié)點的元素值："<<endl;
cin>>del;
deleteNode(T,del);
}break;
default:cout<<"輸入選擇非法";break;
}
cout<<"輸入你的選擇："<<endl;
cin>>commands;
}
}
void initQueue(Queue *q){//初始化隊列
q->elem=new TreeNode;
q->front=q->rear=0;
}
bool isEmpty(Queue *q){//檢查隊列是否為空
if(q->front==q->rear)
return true;//隊為空
else return false;//隊不為空
}
void enQueue(Queue *q,TreeNode *e){//入隊
q->elem[q->rear]=*e;
q->rear++;
}
void outQueue(Queue *q,TreeNode *e){//出隊
if(q->front==q->rear)return;
*e=q->elem[q->front];
q->front++;
}
void createBiTree(TreeNode * &T){//創(chuàng)建二叉樹
char ch;
cin>>ch;
if(ch=='#') T=NULL;
else {//采用遞歸先序創(chuàng)建二叉樹
T=new TreeNode;
T->num=ch;
createBiTree(T->leftchild);
createBiTree(T->rightchild);
}
}
TreeNode* PreFind(TreeNode *T,char da){//給定元素值查找結點指針位置并返回其指針，此方法采用的先序遍歷
TreeNode *temp;
TreeNode *tree[20];
int top=0;
while(T!=NULL||top!=0){
while(T!=NULL){
if(T->num==da)
temp=T;
top++;
tree[top]=T;
T=T->leftchild;
}
if(top!=0){
T=tree[top]->rightchild;
top--;
}
}
return temp;
}
void order(TreeNode *T){//層序遍歷二叉樹
Queue *q=new Queue;
TreeNode *p=new TreeNode;
if(T!=NULL) {
initQueue(q);
enQueue(q,T);
while(!isEmpty(q)){//將根節(jié)點的左右兩個子節(jié)點推入隊內
outQueue(q,p);
cout<<p->num<<" ";
if(p->leftchild!=NULL)
enQueue(q,p->leftchild);
if(p->rightchild!=NULL)
enQueue(q,p->rightchild);
}
}else
cout<<"此二叉樹為空!!!";
}
void midOrder(TreeNode * T){//二叉樹中序遞歸遍歷
if(T!=NULL){
midOrder(T->leftchild);//中序遍歷T的左子樹
cout<<T->num<<" "; //訪問根節(jié)點
midOrder(T->rightchild);//中序遍歷T的右子樹
}
}
void addChild(TreeNode *T,char clue,char add,string side){//插入左右孩子操作,根據clue查找節(jié)點,由side決定插入左孩子還是右孩子
TreeNode *&late=new TreeNode;
late->num=add;
late->leftchild=NULL;
late->rightchild=NULL;
TreeNode *original=PreFind(T,clue);//查找指定的節(jié)點
if(side=="left"){
if(original->leftchild==NULL){//根結點的左孩子結點為空
original->leftchild=late;
}
}else{
if(original->rightchild==NULL){//根結點的右孩子結點為空
original->rightchild=late;
}
}
}
void deleteNode(TreeNode *T,char delchar){ //刪除節(jié)點及其子節(jié)點
if (T!=NULL){//如果根節(jié)點不為空
if (T->num==delchar){//如果根節(jié)點為要刪除的節(jié)點
delete T->leftchild;//刪除左孩子節(jié)點
T->leftchild=NULL;//左指針指向NULL
delete T->rightchild;//刪除右孩子節(jié)點
T->rightchild=NULL;//右指針指向NULL
delete T;//刪除節(jié)點T
}else if (T->leftchild!=NULL&&T->leftchild->num==delchar){//如果左孩子為要刪除的節(jié)點
delete T->leftchild->leftchild;//先刪除左孩子的左孩子
delete T->leftchild->rightchild;//再刪除左孩子的右孩子
delete T->leftchild;//最后刪除左孩子
T->leftchild=NULL;//左指針為空
}else if (T->rightchild!=NULL&&T->rightchild->num==delchar){//如果右孩子為要刪除的節(jié)點
delete T->rightchild->leftchild;//先刪除右孩子的左孩子
delete T->rightchild->rightchild;//再刪除右孩子的右孩子
delete T->rightchild;//最后刪除右孩子
T->rightchild=NULL;//右指針為空
}else {
if(T->leftchild!=NULL){ //如果左孩子不為空
deleteNode(T->leftchild,delchar);//刪除左孩子結點
}if(T->rightchild!=NULL){ //如果右孩子不為空
deleteNode(T->rightchild,delchar);//刪除右孩子節(jié)點
}
}
}
}