C++实现二叉树的基本操作
包括 添加节点、删除节点、前序遍历、中序遍历、后续遍历、层序遍历、最大值、最小值、二叉树的高度
//Tree.h 头文件
#include <stdio.h>
class Tree
{
private :
//节点元素类型为结构体
struct LinkNode
{
int data;
LinkNode *left;
LinkNode *right;
LinkNode(const int& dat,LinkNode *l,LinkNode *r):data(dat),left(l),right(r){}
};
LinkNode *head;//表头节点
//添加节点
void AddTreeNode(LinkNode *node,LinkNode *newNode);
//显示中序排列
void ShowCLR(LinkNode *root);
//显示前序排列
void ShowLCR(LinkNode *root);
//显示右序排列
void ShowLRC(LinkNode *root);
//高度
int Height(LinkNode *root);
public :
//添加节点
bool AddTreeNode(int data);
//显示中序排列
bool ShowCLR();
//显示前序排列
bool ShowLCR();
//显示右序排列
bool ShowLRC();
//前序排列
bool Floor();
//最小值
bool Min(int** minValue);
//最大值
bool Max(int** maxValue);
//是否是空树
bool Empty();
//高度
void Height(int** height);
~Tree()
{
delete[] head;
}
Tree()
{
head=new LinkNode(-1,NULL,NULL);
}
};
//实现文件Tree.cpp
#include "stdafx.h"
#include <stdio.h>
#include<iostream>
using namespace std ;
#include "Tree.h";
#include <queue>
//添加节点
void Tree::AddTreeNode(LinkNode *node,LinkNode *newNode)
{
if(node->data>newNode->data)
{
if(node->left==NULL)
{
node->left=newNode;
}else{
AddTreeNode(node->left,newNode);
}
}else if(node->data<newNode->data)
{
if(node->right==NULL)
{
node->right=newNode;
}else{
AddTreeNode(node->right,newNode);
}
}
}
//添加节点
bool Tree::AddTreeNode(int data)
{
LinkNode *node=new LinkNode(data,NULL,NULL);
if(head->left==NULL)
{
head->left=node;
}
AddTreeNode(head->left,node);
return true;
}
//中序遍历
void Tree::ShowCLR(LinkNode *root)
{
if(root!=NULL){
cout<<root->data<<" ";
}
if(root->left!=NULL)
{
ShowCLR(root->left);
}
if(root->right!=NULL)
{
ShowCLR(root->right);
}
}
//中序遍历
bool Tree::ShowCLR()
{
if(Empty())
{
return false;
}
ShowCLR(head->left);
return true;
}
//前序遍历
void Tree::ShowLCR(LinkNode *root)
{
if(root->left!=NULL)
{
ShowLCR(root->left);
}
if(root!=NULL){
cout<<root->data<<" ";
}
if(root->right!=NULL)
{
ShowLCR(root->right);
}
}
//前序遍历
bool Tree::ShowLCR()
{
if(Empty())
{
return false;
}
ShowLCR(head->left);
return true;
}
//后序遍历
void Tree::ShowLRC(LinkNode *root)
{
if(root->left!=NULL)
{
ShowLRC(root->left);
}
if(root->right!=NULL)
{
ShowLRC(root->right);
}
if(root!=NULL){
cout<<root->data<<" ";
}
}
//后序遍历
bool Tree::ShowLRC()
{
if(Empty())
{
return false;
}
ShowLRC(head->left);
return true;
}
//最小值
bool Tree::Min(int** minValue)
{
if(Empty())
{
return false;
}
LinkNode *tmp=head->left;
while(tmp!=NULL && tmp->left!=NULL)
{
tmp=tmp->left;
}
**minValue= tmp->data;
return true;
}
//最大值
bool Tree::Max(int** maxValue)
{
if(Empty())
{
return false;
}
LinkNode *tmp=head->left;
while(tmp!=NULL && tmp->right!=NULL)
{
tmp=tmp->right;
}
**maxValue= tmp->data;
return true;
}
//判断树是否为空
bool Tree::Empty()
{
return head->left==NULL;
}
//用队列实现二叉树层序遍历
//1:添加根节点
//2:打印根节点的数据,添加根节点的子节点,弹出根节点
//3:循环第二步
bool Tree::Floor()
{
queue<LinkNode*> q;
LinkNode* cur=head->left;
q.push(head->left);
while(!q.empty())
{
cur=q.front();
cout<<cur->data<<" ";
if(cur->left!=NULL){
q.push(cur->left);
}
if(cur->right!=NULL)
{
q.push(cur->right);
}
q.pop();
}
return true;
}
//求两个数中较大的一个
int max(int a,int b)
{
if(a>b)
{
return a;
}else
{
return b;
}
}
//递归求二叉树的高度
//二叉树的高度就是左子树和右子树中较大一颗二叉树的高度
int Tree::Height(LinkNode *root)
{
if(root==NULL)
{
return 0;
}
return 1+max(Height(root->left),Height(root->right));
}
//用指向指针的指针接受二叉树的高度
void Tree::Height(int** height)
{
**height=Height(head->left);
}
#include "stdafx.h"
#include <stdio.h>
#include <iostream>
using namespace std;
#include "Tree.h"
void TreeTest() ;
int main()
{
TreeTest();
int a=0;
cin>>a;
return 0;
}
//指针类型调用属性和方法用“->” 对象类型用“.”
//变量在不需要使用的时候就要释放掉它的内存
void TreeTest()
{
Tree tree;
int a[]={1,3,6,7,8,2,4,9,10,5};
for(int i=0;i<10;i++){
tree.AddTreeNode(a[i]);
}
cout<<"-----------原始数组----------"<<endl;
for(int i=0;i<10;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
cout<<endl;
cout<<"-----------中序排列----------"<<endl;
tree.ShowCLR();
cout<<endl;cout<<endl;
cout<<"-----------前序排列----------"<<endl;
tree.ShowLCR();
cout<<endl;cout<<endl;
cout<<"-----------后序排列----------"<<endl;
tree.ShowLRC();
cout<<endl;
cout<<endl;
cout<<"-----------层序排列----------"<<endl;
cout<<endl;
tree.Floor();
cout<<endl;
int min=-1;
int *pmin=&min;
tree.Max(&pmin);
cout<<endl;
cout<<"最大值:"<<min<<endl;
cout<<endl;
tree.Min(&pmin);
cout<<"最小值:"<<min<<endl;
cout<<endl;
int h=-1;
int *height=&h;
tree.Height(&height);
cout<<"高度:"<<h<<endl;
}
分享到:
相关推荐
C++二叉树基本操作
C++二叉树基本操作实验报告.pdfC++二叉树基本操作实验报告.pdf
(完整版)C++二叉树基本操作实验报告.pdf(完整版)C++二叉树基本操作实验报告.pdf
递归二叉树的基本操作,递归创建,递归先序遍历、中序遍历、后序遍历,求树的高度,求叶子结点的个数,交换树的左右孩子
用C++编写二叉树基本操作(包括)建立二叉树 进行层次遍历 中序遍历 后序遍历 树的高度 树中节点数 树中叶子节点数等,
二叉树的基本操作的各种操作 先序 中序 后序 遍历二叉树 还有二叉树的节点数的求法
C++二叉树模板,包含了基本的二叉树的操作。
创建,输出左右结点,求深度,宽度,求叶子结点及总结点的个数,查找结点,求某结点的子孙个数,输出二叉树
主要为大家详细介绍了C++实现二叉树基本操作,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
不用你再改正了,这是一个下载解压后可以直接执行的程序,省去了你改来改去的麻烦,实现二叉树的基本操作,包括建树、前序遍历、中序遍历、后序遍历、删除、求节点数、高度等等操作。
编写程序实现二叉树的如下操作: 1) 建立二叉链表 2) 二叉树的先序、中序、后序遍历 3) 求解二叉树的叶子结点个数 4) 将二叉树中所有结点的左、右子树相互交换 输入: 扩展二叉树先序序列:ab#d##ce###。其中#...
南邮数据结构实验使用C++描述,二叉树的基本操作
包含二叉树创建,以及增删查改节点,线索二叉树等
程序的输入是数组,通过二叉树的数组表示创建的链表表示的二叉树,输出没有做成树型输出,感觉太复杂,而是按照广义表的输出方式输出 写的时候感觉大部分的操作实现都很简单,不过非递归方式的后序和中序的游标遍历搞的...
二叉树的操作 二叉树的基本操作 遍历 叶子 层数
二叉树基本操作:定义、建立、输入、输出等操作以及各种遍历,交换using namespace std; //二叉树定义 typedef char ElementType; typedef struct BiTreeNode { ElementType data; struct BiTreeNode* lchild; ...
熟悉二叉树结点的结构和对二叉树的基本操作。掌握对二叉树每一种操作的具体实现。学会利用递归方法和非递归方法编写对二叉树这种递归数据结构进行处理的算法。
目的:1、掌握二叉链表上实现二叉树基本操作。 2、学会设计基于遍历的求解二叉树应用问题的递归算法。 3、理解哈夫曼树的构造算法,学习设计哈夫曼编码和译码系统 要求:能成功演示二叉树的有关算法,运算完毕后能...