创建二叉树 二叉树如何删除节点操作教程
更新时间:2020年4月25日 17:48 点击:1723
复制代码 代码如下:
// 二叉树.cpp : 定义控制台应用程序的入口点。
//
/*
*二叉树作业
*2012.12.1 13:55
*Made By Karld Vorn Doenitz
*/
#include "stdafx.h"
#include<iostream>
#include<string>
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;
cin>>commands;
while(commands){
/*
*采用switch语句
*while循环
*/
switch (commands){
case 'c':
{
cout<<"输入要创建的二叉树,以#为空节点。"<<endl;
createBiTree(T);
}break;
case 'm':
{ if(T==NULL)cout<<"此二叉树为空,请先创建二叉树!!!"<<endl;
else{
cout<<"中序遍历二叉树的结果为:";
midOrder(T);
cout<<endl;}
}break;
case 'o':{
if(T==NULL)cout<<"此二叉树为空,请先创建二叉树!!!"<<endl;
else{cout<<"层次遍历二叉树的结果为:";
order(T);
cout<<endl;
} }break;
case 's':{char ch;
cout<<"输入要查找的元素:"<<endl;
cin>>ch;
cout<<"要找的节点的左孩子是:";
TreeNode *bt=PreFind(T,ch);
if(bt->leftchild!=NULL)
cout<<bt->leftchild->num<<endl;
else cout<<"此节点是叶子,无左孩子!!!"<<endl;
cout<<"要找的节点的右孩子是:";
if(bt->rightchild!=NULL)
cout<<bt->rightchild->num<<endl;
else cout<<"此节点是叶子,无右孩子!!!"<<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<<"输入要删除的节点的元素值:"<<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){//创建二叉树
char ch;
cin>>ch;
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);
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<<" "; //访问根节点
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);//删除右孩子节点
}
}
}
}
相关文章
- 这篇文章主要介绍了在C#中使用二叉树实时计算海量用户积分排名的实现详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-06-25
- 这篇文章主要介绍了举例讲解C语言程序中对二叉树数据结构的各种遍历方式,先序中序后序二叉树遍历几乎成了最老生常谈的数据结构基础知识,的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了一波二叉树遍历问题的C++解答实例分享,包括节点打印和转换为镜像等问题的解答,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法,涉及C++二叉树的定义、遍历、统计相关操作技巧,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言数据结构之二叉树的非递归后序遍历算法的相关资料,希望通过本文能帮助到大家,让大家实现这样的功能,需要的朋友可以参考下...2020-04-25
- 二叉树是数据结构中的树的一种特殊情况,有关二叉树的相关概念,这里不再赘述,如果不了解二叉树相关概念,建议先学习数据结构中的二叉树的知识点...2020-04-25
- 这篇文章主要介绍了php实现的二叉树遍历算法,结合具体实例形式分析了php针对二叉树的常用前序、中序及后序遍历算法实现技巧,需要的朋友可以参考下...2017-06-20
- 这篇文章主要介绍了如何在Python中创建二叉树,帮助大家更好的理解和学习使用python,感兴趣的朋友可以了解下...2021-03-30
- 这篇文章主要介绍了C语言 二叉查找树性质详解及实例代码的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C++基于先序、中序遍历结果重建二叉树的方法,结合实例形式分析了基于C++构建二叉树的相关操作技巧,需要的朋友可以参考下...2020-04-25
C++基于递归和非递归算法判定两个二叉树结构是否完全相同(结构和数据都相同)
这篇文章主要介绍了C++基于递归和非递归算法判定两个二叉树结构是否完全相同,若判断二叉树的结构和数据都相同则为完全相同.涉及C++二叉树的创建、遍历、比较等相关操作技巧,需要的朋友可以参考下...2020-04-25- 这篇文章主要为大家详细介绍了C++实现二叉树基本操作,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
- 这篇文章主要介绍了C语言实现二叉树遍历的迭代算法,包括二叉树的中序遍历、先序遍历及后序遍历等,是非常经典的算法,需要的朋友可以参考下...2020-04-25
- 在本篇文章里小编给大家分享了关于c++先序二叉树的构建的相关知识点,需要的朋友们跟着学习下。...2020-04-25
- 这篇文章主要为大家详细介绍了C++二叉树实现词频分析功能,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
- 这篇文章主要介绍了平衡二叉树的实现实例,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C++ 数据结构二叉树(前序/中序/后序递归、非递归遍历)的相关资料,这里提供实例代码来帮助大家理解掌握二叉树,需要的朋友可以参考下...2020-04-25
C++实现LeetCode(105.由先序和中序遍历建立二叉树)
这篇文章主要介绍了C++实现LeetCode(105.由先序和中序遍历建立二叉树),本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...2021-07-23- 这篇文章主要介绍了C语言二叉树的非递归遍历,包括了先序遍历、中序遍历与后序遍历,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C++非递归建立二叉树的方法,实例分析了二叉树的原理与C++实现技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-04-25