`
smallearth
  • 浏览: 33750 次
  • 性别: Icon_minigender_1
社区版块
存档分类
最新评论

C++ 二叉树(创建,遍历,查找,插入,删除)『菜鸟版』

 
阅读更多
//二叉树操作

#include "stdafx.h"
#include<iostream>
using namespace std; 
int num_visit=0;//记录输出元素个数
struct tnode{   
    public: int data;
    public: tnode *left,*right;
	
    tnode(){}
	tnode(int item,tnode *p,tnode *q):data(item),left(p),right(q){}
 };
typedef tnode *Tnode;
//生明函数
int menu();//菜单
void main_menu(Tnode root,int n);//主菜单
Tnode createTree();//创建二叉树
int visit(int t);//访问节点
void showTree(Tnode , int );//遍历
int level_showTree(Tnode root);//先序便遍历二叉树
int inorder_showTree(Tnode root);//中序遍历二叉树
int postorder_showTree(Tnode root);//后序遍历二叉树
bool search(Tnode root,int search_num);//查找二叉树
Tnode insert(Tnode root,int insert_num);//插入
void d_delete(Tnode,int);//删除
void free(Tnode root);//free
//主函数
void main()
{
	Tnode root = createTree();	
	//菜单
	int n = menu();
	//退出
	if(n ==0 ){
	  return;
	}
	//遍历
	if(n<=3)
	{
	  showTree(root,n);
      main_menu(root,n);
	}
	//查找
	 if(n == 4){
	     cout<<"请输入要查找的结点的元素值:";
		 cin>>n;
		 search(root,n);
		 main_menu(root,n);
	  }
	//插入
    if(n == 5){
	    cout<<"请输入要插入的节点的元素值:";
		cin>>n;
		insert(root,n);
		main_menu(root,n);
	  }
	//删除
	if(n == 6){
	   cout<<"请输入要删除的结点元素值:";
	   cin>>n;
	   d_delete(root,n);
	   n = menu();
	   main_menu(root,n);
	}
}
//菜单
int menu(){
	  cout<<"        菜单:输入0退出."<<endl<<endl;
	  cout<<"一 遍历:"<<endl;
	  cout<<"1.先序遍历 请输入1.";
	  cout<<endl<<"2.中序遍历 请输入2.";
	  cout<<endl<<"3.后序遍历 请输入3.";
	  cout<<endl<<endl<<"二 查找:"<<endl;
	  cout<<"4.查找 请输入4."<<endl;
	  cout<<endl<<"三 插入:"<<endl;
	  cout<<"5.插入 请输入5."<<endl;
	  cout<<endl<<"四 删除:"<<endl;
	  cout<<"6.删除 请输入6."<<endl<<endl;
	  cout<<"请输入:";
	  int n;
	  cin>>n;
	  return n;
}
//主菜单
void main_menu(Tnode root,int n){
	while(n>=0){
		n = menu();

		if(n==0){
		return;
		}
		if(n<=3)
		{
		  showTree(root,n);
		}
		//查找
		 if(n == 4){
			 cout<<"请输入要查找的结点的元素值:";
			 cin>>n;
			 cout<<search(root,n);
		  }
		//插入
		if(n == 5){
			cout<<"请输入要插入的节点的元素值:";
			cin>>n;
			insert(root,n);
		  }
		if(n == 6){
		   cout<<"请输入要删除的结点元素值:";
		   cin>>n;
		   d_delete(root,n);
		}
	}
}
//创建二叉树
Tnode createTree(){
   Tnode root,p,q;
   
   //左子树
   p = new tnode(96,NULL,NULL);
   //右子树
   q = new tnode(104,NULL,NULL);
   //根节点
   root = new tnode(100,p,q);
   return root;
}
//访问节点
int visit(int t){
	   cout<<t<<" ";
	   if(++num_visit%5 == 0)
		   cout<<endl;
	 return 1;
}
//遍历
void showTree(Tnode root,int n){
  
  switch(n){
      case 1: 
		   cout<<"先序遍历:"<<endl;
		   level_showTree(root);
	    break;
	  case 2: 
		  cout<<"中序遍历:"<<endl;
		  inorder_showTree(root);
		break;
	  case 3:
		  cout<<"后序遍历:"<<endl;
		  postorder_showTree(root);
		break;
	  default:
		  return; 
  }
  cout<<endl;
}
//先序遍历二叉树
int level_showTree(Tnode root){
	if(root){
	    visit(root->data);
		level_showTree(root->left);
		level_showTree(root->right);
	}else
		return 0;
}
//中序遍历
int inorder_showTree(Tnode root){
	if(root){
		inorder_showTree(root->left);
		visit(root->data);
		inorder_showTree(root->right);
	}else
		return 0;
}
//后序遍历
int postorder_showTree(Tnode root){
	if(root){
		postorder_showTree(root->left);
		postorder_showTree(root->right);
		visit(root->data);
	}else 
		return 0;
}
//查找
bool search(Tnode root,int search_num){
	if(root){
	   if(root->data == search_num){
			cout<<root->data <<"=="<< search_num<<endl;
		    return true;
	   }else{
		   search(root->left,search_num);
		   search(root->right,search_num);
		 }  
	}else{
		return false;
	}
}
//插入
Tnode insert(Tnode root,int insert_num){
	if(search(root,insert_num)){
    	cout<<"此节点存在!"<<endl;
		return NULL;
	}else
		if(root == NULL){
			root = new tnode(insert_num,NULL,NULL);
		}else{
		  if(root->data>insert_num){
			  root->left = insert(root->left,insert_num);	
		  }else{
			  root->right = insert(root->right,insert_num);
		  }
		}
		return root;
}
//删除
void d_delete(Tnode root,int d_num){
	if(root){
		if(root->left->data == d_num){
			root->left = NULL;
			free(root->left);
		}else if(root->right->data == d_num){
			root->right = NULL;
			free(root->right);
		}else{
			d_delete(root->left,d_num);
			d_delete(root->right,d_num);
		}
	}else
		return;
}
//free
void free(Tnode root){
	if(root){
		free(root->left);
		free(root->right);
		delete root;
	}
}

分享到:
评论

相关推荐

    c++使用二叉树进行查找 插入 删除

    c++使用二叉树进行查找 插入 删除 #include "stdafx.h" #include&lt;iostream&gt; using namespace std; int num_visit=0;//记录输出元素个数 struct tnode{ public: int data; public: tnode *left,*right; ...

    C++实现异质二叉树的查找、插入、删除和遍历操作

    C++实现异质二叉树的查找、插入、删除和遍历操作。

    二叉树插入删除遍历,满足您各种需求

    二叉树类模板,C++实现 二叉树构造、插入删除查找、返回父兄双子结点、各种遍历。。。能满足最苛刻用户的个中年稀奇古怪的需求~~

    10个数据结构课程设计实例二叉树建立遍历冒泡排序快速排序等.zip

    c 代码 10个数据结构课程设计例子 查找.c 二叉排序树.c 二叉树层次遍历.c 二叉树非递归遍历.c 二叉树建立.c 快速排序.c 括号匹配.c 冒泡排序.c 直接插入排序.c 直接选择排序.c

    10个数据结构课程设计实例-二叉树建立遍历、冒泡排序、快速排序等.zip

    10个数据结构课程设计例子: 1、查找.c 2、二叉排序树.c ...4、二叉树非递归遍历.c 5、二叉树的建立.c 6、快速排序.c 7、括号匹配.c 8、冒泡排序.c 9、直接插入排序.c 10、直接选择排序.c 注意,亲测有效!

    C++实现二叉树搜索树

    功能:插入、查找、删除、清除整个树、返回最大值、返回最小值、前序遍历、中序遍历、后序遍历。 注:此二叉树允许插入相同的值

    C++数据结构-二叉查找树和平衡二叉树

    实现了二叉查找树的查找、插入...实现了平衡二叉树(AVL树)的查找、插入、删除和迭代遍历的完整功能,插入时的各种旋转操作按照经典数据结构教材实现,并有详细的注释和说明。删除操作和相关旋转方法有单独描述文档。

    二叉搜索的实现、插入、搜索、各种遍历及判断

    二叉搜索树的实现算法、插入算法、搜索算法、前序遍历、中序遍历、后序遍历,以及判断一课二叉树是否为二叉搜索树的算法。其中删除算法采用“用右子树上具有最小关键码的结点顶替被删结点”和“用左子树上具有最大...

    二叉排序树与平衡二叉树的实现

    而在二叉排序树上进行查找时的平均查找长度和二叉树的形态有关: ①在最坏情况下,二叉排序树是通过把一个有序表的n个结点依次插入而生成的,此时所得的二叉排序树蜕化为棵深度为n的单支树,它的平均查找长度和...

    C++编程资料整合版

    1.C++树的生成与遍历 2.遍历二叉树 3.插入排序,快速排序 4.查找 5.抽象数据类型的表示与实现 6.串操作应用举例 7.串的表示和实现 8.串的定义 9.串的实现实验 10.动态查找表 11.队列 12.二叉树的存储结构 13.二叉树...

    c++数据结构-实验.zip

    2)设计一个线性表,分别用顺序存储结构和链式存储结构实现,完成线性表的构造、查找、插入、删除、输出等基本操作。 3)掌握两种存储结构的优缺点以及在实际应用中如何选择存储方式。 4)选作:约瑟夫环的顺序存储...

    平衡二叉树C语言.zip

    自己做的平衡二叉树,学校的实验作业,包括查找插入前中后序递归非递归遍历,包括层次遍历,树形打印,合并、分裂平衡二叉树等基本操作。

    C++数据抽象和问题求解(第6版).[美]Frank M. Carrano(带详细书签).pdf

    15.3.3 创建二叉查找树 435 15.3.4 遍历二叉查找树 437 15.3.5 二叉查找树操作的效率 437 第16章 树的实现 443 16.1 二叉树中的节点 444 16.1.1 基于数组的表示 444 16.1.2 基于链表的表示 446 16.2 ADT...

    二叉树的建立及操作

    本文件为基于vs2010平台的使用C++语言的二叉树建立和操作。其中有二叉树的四种遍历方式,查找插入删除等基本操作。代码精心总结,有详细的注释,结构清晰,对初学算法的人有很大帮助。

    排序二叉树完整代码

    本代码涵盖二叉查找树的创建,插入,删除,添加,遍历等操作,结合http://blog.csdn.net/wenqian1991/article/details/18228309 可理解

    AVL树的C++实现

    AVL平衡二叉树的C++实现(模板),实现了插入、查找、删除,前序、后序、中序遍历等

    吉林大学软件学院2011数据结构实验题C++实现

    2) 实现二叉查找树的查找、插入和删除等算法; 第三次实验 题目1 邻接表存储的图相关算法的实验验证。 [实验目的] 验证邻接表存的图及其上的基本操作。 [实验内容及要求] 1、 定义邻接表存储的图类。 2、 实验验证...

    数据结构课程设计-C++实验代码

    能够实现一个基于二叉树遍历实现一个算法操作 4.实验过程中应用递归 实验五 图的应用 实验要求: 1.用邻接矩阵或者邻接表定义图的应用 2.实现图的基本操作: 构造,销毁 广度,深度优先搜索 &lt;3&gt; 图的打印 3.图的...

    数据结构课程设计(C语言实现)

    4.二叉树的基本操作及应用:①创建②遍历(先序、中序、后序)③求结点个数④求树的深度⑤查找双亲⑥查找兄弟(左/右)⑦查找孩子(左/右)⑧应用,二叉树的应用,如二叉排序树、Huffman编码等。 5.图的基本操作及...

    红黑树(C++)

    本文件为基于vs2010平台的使用C++语言的红黑树建立和操作。其中有二叉树的四种遍历方式,查找插入删除深度等基本操作。代码精心总结,有详细的注释,运行完全通过,结构清晰,对初学算法的人有很大帮助。

Global site tag (gtag.js) - Google Analytics