创建二叉树 二叉树如何删除节点操作教程

【 tulaoshi.com - 编程语言 】

代码如下：

// 二叉树.cpp : 定义控制台应用程序的入口点。
//
/*
*二叉树作业
*2012.12.1 13:55
*Made By Karld Vorn Doenitz
*/
#include "stdafx.h"
#includeiostream
#includestring
using namespace std;
class TreeNode{//建立节点类
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键先序创建二叉树； ""*"endl;
cout"*""2、按下m键中序递归遍历二叉树； ""*"endl;
cout"*""3、按下o键层次遍历二叉树； ""*"endl;
cout"*""4、按下s键给定元素查找节点； ""*"endl;
cout"*""5、按下i键指定位置插入节点； ""*"endl;
cout"*""6、按下d键删除指定的节点； ""*"endl;
cout"*""请输入你的选择： ""*"endl;
cout"*""__________________________________"endl;
cincommands;
while(commands){
/*
*采用switch语句
*while循环
*/
switch (commands){
case 'c':
{
cout"输入要创建的二叉树，以#为空节点。"endl;
createBiTree(T);
}break;
case 'm':
{ if(T==NULL)cout"此二叉树为空，请先创建二叉树!!!"endl;
else{
cout"中序遍历二叉树的结果为：";
midOrder(T);
coutendl;}
}break;
case 'o':{
if(T==NULL)cout"此二叉树为空，请先创建二叉树!!!"endl;
else{cout"层次遍历二叉树的结果为：";
order(T);
coutendl;
} }break;
case 's':{char ch;
cout"输入要查找的元素："endl;
cinch;
cout"要找的节点的左孩子是：";
TreeNode *bt=PreFind(T,ch);
if(bt-leftchild!=NULL)
coutbt-leftchild-numendl;
else cout"此节点是叶子，无左孩子!!!"endl;
cout"要找的节点的右孩子是：";
if(bt-rightchild!=NULL)
coutbt-rightchild-numendl;
else cout"此节点是叶子，无右孩子!!!"endl;
}break;
case 'i':{char clue,add;
string side;
cout"输入插入位置：";
cinclue;
cout"输入插入的元素:";
cinadd;
cout"选择要插入的是左子树(请输入left)还是右子树(请输入right)";
cinside;
addChild(T,clue,add,side);
}break;
case 'd':{
char del;
cout"输入要删除的节点的元素值："endl;
cindel;
deleteNode(T,del);
}break;
default:cout"输入选择非法";break;
}
cout"输入你的选择："endl;
cincommands;
}
}
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){//创建二叉树
char ch;
cinch;
if(ch=='#') T=NULL;
else {//采用递归先序创建二叉树
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)){//将根节点的左右两个子节点推入队内
outQueue(q,p);
coutp-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的左子树
coutT-num" "; //访问根节点
midOrder(T-rightchild);//中序遍历T的右子树
}
}
void addChild(TreeNode *T,char clue,char add,string side){//插入左右孩子操作,根据clue查找节点,由side决定插入左孩子还是右孩子
TreeNode *&late=new TreeNode;
late-num=add;
late-leftchild=NULL;
late-rightchild=NULL;
TreeNode *original=PreFind(T,clue);//查找指定的节点
if(side=="left"){
if(original-leftchild==NULL){//根结点的左孩子结点为空
original-leftchild=late;
}
}else{
if(original-rightchild==NULL){//根结点的右孩子结点为空
original-rightchild=late;
}
}
}
void deleteNode(TreeNode *T,char delchar){ //删除节点及其子节点
if (T!=NULL){//如果根节点不为空
if (T-num==delchar){//如果根节点为要删除的节点
delete T-leftchild;//删除左孩子节点
T-leftchild=NULL;//左指针指向NULL
delete T-rightchild;//删除右孩子节点
T-rightchild=NULL;//右指针指向NULL
delete T;//删除节点T
}else if (T-leftchild!=NULL&&T-leftchild-num==delchar){//如果左孩子为要删除的节点
delete T-leftchild-leftchild;//先删除左孩子的左孩子
delete T-leftchild-rightchild;//再删除左孩子的右孩子
delete T-leftchild;//最后删除左孩子
T-leftchild=NULL;//左指针为空
}else if (T-rightchild!=NULL&&T-rightchild-num==delchar){//如果右孩子为要删除的节点
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);//删除右孩子节点
}
}
}
}