//CPP: defines the entry point for the console application.
//

#include "stdafx.h"
#include<iostream>
#include<string>
using namespace std;
class TreeNode{//Create node class
public:
char num;
TreeNode *leftchild,*rightchild;
};
class Queue{//Create queue class
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(){//The main function
cmd();
return 0;
}
void cmd(){//Command function

char commands;
TreeNode *T=NULL;
cout<<"*"<<"___________ The command is _______________"<<endl;
cout<<"*"<<"1 , press the c Create binary tree with key first;  "<<"*"<<endl;
cout<<"*"<<"2 , press the m Recursive traversal of binary tree in the key sequence;  "<<"*"<<endl;
cout<<"*"<<"3 , press the o Key hierarchy traverses binary tree;  "<<"*"<<endl;
cout<<"*"<<"4 , press the s Key given element to find the node;  "<<"*"<<endl;
cout<<"*"<<"5 , press the i Key to specify the position of the insert node;  "<<"*"<<endl;
cout<<"*"<<"6 , press the d Key deletes the specified node;  "<<"*"<<endl;
cout<<"*"<<" Please enter your choice:  "<<"*"<<endl;
cout<<"*"<<"__________________________________"<<endl;
cin>>commands;
while(commands){

switch (commands){
case 'c':
{
cout<<" Enter the binary tree to create to # Is an empty node. "<<endl;
createBiTree(T);
}break;
case 'm':
{ if(T==NULL)cout<<" The binary tree is empty. Create the binary tree first !!!"<<endl;
else{
cout<<" The result of middle order traversal binary tree is: ";
midOrder(T);
cout<<endl;}
}break;
case 'o':{
if(T==NULL)cout<<" The binary tree is empty. Create the binary tree first !!!"<<endl;
else{cout<<" The result of hierarchical traversal binary tree is: ";
order(T);
cout<<endl;
} }break;
case 's':{char ch;
cout<<" Enter the element to look for: "<<endl;
cin>>ch;
cout<<" The left child of the node to find is: ";
TreeNode *bt=PreFind(T,ch);
if(bt->leftchild!=NULL)
cout<<bt->leftchild->num<<endl;
else cout<<" This node is a leaf without a left child !!!"<<endl;
cout<<" The right child of the node to be found is: ";
if(bt->rightchild!=NULL)
cout<<bt->rightchild->num<<endl;
else cout<<" This node is a leaf without right child !!!"<<endl;
}break;
case 'i':{char clue,add;
string side;
cout<<" Input insertion position: ";
cin>>clue;
cout<<" Enter the inserted element :";
cin>>add;
cout<<" Select the left subtree to insert ( Please enter the left) Right subtree again ( Please enter the right)";
cin>>side;
addChild(T,clue,add,side);
}break;
case 'd':{
char del;
cout<<" Enter the element value of the node to be deleted: "<<endl;
cin>>del;
deleteNode(T,del);
}break;
default:cout<<" Illegal input selection ";break;
}
cout<<" Enter your choice: "<<endl;
cin>>commands;
}
}
void initQueue(Queue *q){//Initialize queue
q->elem=new TreeNode;
q->front=q->rear=0;
}
bool isEmpty(Queue *q){//Check that the queue is empty
if(q->front==q->rear)
return true;//Team is empty
else return false;//The team is not null
}
void enQueue(Queue *q,TreeNode *e){//The team
q->elem[q->rear]=*e;
q->rear++;
}
void outQueue(Queue *q,TreeNode *e){//Out of the team
if(q->front==q->rear)return;
*e=q->elem[q->front];
q->front++;
}
void createBiTree(TreeNode * &T){//Create a binary tree
char ch;
cin>>ch;
if(ch=='#') T=NULL;
else {// Use recursive first order Create a binary tree
T=new TreeNode;
T->num=ch;
createBiTree(T->leftchild);
createBiTree(T->rightchild);
}
}
TreeNode* PreFind(TreeNode *T,char da){//Given element value to find the node pointer position and return its pointer, this method USES the first order traversal
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){//The sequence traverses the binary tree
Queue *q=new Queue;
TreeNode *p=new TreeNode;
if(T!=NULL) {
initQueue(q);
enQueue(q,T);
while(!isEmpty(q)){//Push the left and right children of the root node into the queue
outQueue(q,p);
cout<<p->num<<" ";
if(p->leftchild!=NULL)
enQueue(q,p->leftchild);
if(p->rightchild!=NULL)
enQueue(q,p->rightchild);
}
}else
cout<<" The binary tree is empty !!!";
}
void midOrder(TreeNode * T){//Order recursive traversal in binary trees
if(T!=NULL){
midOrder(T->leftchild);//The middle order traverses the left subtree of T
cout<<T->num<<" "; //Accessing the root node
midOrder(T->rightchild);//The middle order traverses the right subtree of T
}
}
void addChild(TreeNode *T,char clue,char add,string side){//Insert left child operation, look up the node according to clue, and it is up to side to insert left child or right child
TreeNode *&late=new TreeNode;
late->num=add;
late->leftchild=NULL;
late->rightchild=NULL;
TreeNode *original=PreFind(T,clue);//Finds the specified node
if(side=="left"){
if(original->leftchild==NULL){//The left child of the root is nil
original->leftchild=late;
}
}else{
if(original->rightchild==NULL){//The right child of the root is nil
original->rightchild=late;
}
}
}
void deleteNode(TreeNode *T,char delchar){ //Delete the node and its children
if (T!=NULL){//If the root node is not empty
if (T->num==delchar){//If the root node is the node to be deleted
delete T->leftchild;//Delete the left child node
T->leftchild=NULL;//The left pointer points to NULL
delete T->rightchild;//Delete the right child node
T->rightchild=NULL;//The right pointer points to NULL
delete T;//Delete node T
}else if (T->leftchild!=NULL&&T->leftchild->num==delchar){//If the left child is the node to be deleted
delete T->leftchild->leftchild;//Delete the left child of the left child first
delete T->leftchild->rightchild;//Delete the left child's right child
delete T->leftchild;//Finally delete left child
T->leftchild=NULL;//The left pointer is null
}else if (T->rightchild!=NULL&&T->rightchild->num==delchar){//If the right child is the node to be deleted
delete T->rightchild->leftchild;//Delete the left child of the right child first
delete T->rightchild->rightchild;//Delete the right child of the right child
delete T->rightchild;//Finally delete the right child
T->rightchild=NULL;//The right pointer is null
}else {
if(T->leftchild!=NULL){ //If the left child is not empty
deleteNode(T->leftchild,delchar);//Delete left child node
}if(T->rightchild!=NULL){ //If the right child is not empty
deleteNode(T->rightchild,delchar);//Delete the right child node
}
}
}
}