2 baidu 24427837 baidu_24427837 于 2014.12.11 18:55 提问

有哪位哥哥姐姐可以帮我写下程序(关于二叉树的 或者栈)

那个运用c++编写两个程序,其中一个是实现二叉树(或者栈),另一个是运用二叉树(或者栈)解决实际问题。谢谢啦,实在是没搞懂。

2个回答

caozhy
caozhy   Ds   Rxr 2014.12.11 19:26
已采纳

/**

  • <!--
  • File : stack.h
  • Author : fancy
  • Email : fancydeepin@yeah.net
  • Date : 2013-02-03
  • --!> */ #include #include #include #define Element char #define INIT_SIZE 10 #define INCREMENT_SIZE INIT_SIZE / 2

typedef struct TStack {
Element *base;
Element *top;
int size;
} *Stack;

//栈的构造器,创建空栈
void stackConstructor(Stack &stack){
stack->base = (Element *)malloc(INIT_SIZE * sizeof(Element));
if(!stack->base){
printf("\n为栈分配内存空间失败!\n");
exit(0);
}
stack->top = stack->base; //空栈 top == base
stack->size = INIT_SIZE;
}

//是否为空栈
bool isEmpty(Stack stack){
if(stack->top == stack->base){
return true;
}
return false;
}

//压栈
bool push(Stack &stack, Element e){
if(stack->top - stack->base >= stack->size){ //栈满
stack->base = (Element *)realloc(stack->base, (stack->size + INCREMENT_SIZE) * sizeof(Element));
if(!stack->base){
printf("\n为栈扩展内存空间失败!\n");
return false;
}
stack->top = stack->base + stack->size;
stack->size += INCREMENT_SIZE;
}
*stack->top++ = e;
return true;
}

//弹栈
Element pop(Stack stack){
if(isEmpty(stack)){
printf("\n栈为空,弹栈操作失败!\n");
return ' ';
}
return *--stack->top;
}

/**

  • <!--
  • File : Stack.cpp
  • Author : fancy
  • Email : fancydeepin@yeah.net
  • Date : 2013-02-03
  • --!> */ #include "stack.h"

int main() {

Stack stack;
stackConstructor(stack);
push(stack, 'f');
push(stack, 'a');
push(stack, 'n');
push(stack, 'c');
push(stack, 'y');
printf("%c", pop(stack));
printf("%c", pop(stack));
printf("%c", pop(stack));
printf("%c", pop(stack));
printf("%c", pop(stack));
//output[result]: ycnaf
return 0;

}

baidu_24427837
baidu_24427837 谢谢,但是有的看不懂。。好像不是c++
3 年多之前 回复
caozhy
caozhy 参考:http://www.blogjava.net/fancydeepin/archive/2013/02/03/395062.html
3 年多之前 回复
caozhy
caozhy   Ds   Rxr 2014.12.11 19:25

C++实现二叉树的基本操作

包括 添加节点、删除节点、前序遍历、中序遍历、后续遍历、层序遍历、最大值、最小值、二叉树的高度

//Tree.h 头文件

#include

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
#include
using namespace std ;
#include "Tree.h";
#include

//添加节点
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->datadata)
{
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<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<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<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 q;
LinkNode* cur=head->left;
q.push(head->left);
while(!q.empty())
{
cur=q.front();
cout<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
#include
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;
}

baidu_24427837
baidu_24427837 谢谢,不过好像运行之后有问题。但是还是很感谢
3 年多之前 回复
caozhy
caozhy 参考:http://www.cnblogs.com/hlxs/archive/2011/04/02/2087980.html
3 年多之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!