二叉树的实现? — 编程爱好者社区

主题：二叉树的实现?

gz_lwz008@163.com [专家分：0] 发布于 2010-04-11 15:16:00

[code=c]
在主函数中如何实现二叉树?本人用的是层次遍历二叉树;

以下是代码:

#include <iostream.h>
#define max 20
typedef struct BiTNode
{
int data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

//初始化
int Initiate(BiTree &bt)
{
bt=new BiTNode;
if(!bt)
  return 0;
bt->data=-1;
bt->lchild=NULL;
bt->rchild=NULL;
return 1;
}

//创建二叉树
BiTree Creat(int x,BiTree lbt,BiTree rbt)
{
BiTree p;
p=new BiTNode;
if(!p)
  return NULL;
p->data=x;
p->lchild=lbt;
p->rchild=rbt;
return p;
}

//左子树插入节点
BiTree InsertL(BiTree bt,int x,BiTree parent)
{
BiTree p;
p=new BiTNode;
if(parent==NULL)
{
  cout<<"插入失败！"<<endl;
  return NULL;
}
if(!p)
  return NULL;
p->data=x;
p->lchild=NULL;
p->rchild=NULL;
if(parent->lchild==NULL)
  parent->lchild=p;
else
{
  p->lchild=parent->lchild;
  parent->lchild=p;
}
return bt;
}

//右子树插入节点
BiTree InsertR(BiTree bt,int x,BiTree parent)
{
BiTree p;
p=new BiTNode;
if(parent==NULL)
{
  cout<<"插入失败！"<<endl;
  return NULL;
}
if(!p)
  return NULL;
p->data=x;
p->lchild=NULL;
p->rchild=NULL;
if(parent->rchild==NULL)
  parent->rchild=p;
else
{
  p->rchild=parent->rchild;
  parent->rchild=p;
}
return bt;
}

//删除左子树
BiTree DeleteL(BiTree bt,BiTree parent)
{
BiTree p;
if(parent==NULL||parent->lchild==NULL)
{
  cout<<"删除失败！"<<endl;
  return NULL;
}
p=parent->lchild;
parent->lchild=NULL;
delete p;
return bt;
}

//删除左子树
BiTree DeleteR(BiTree bt,BiTree parent)
{
BiTree p;
if(parent==NULL||parent->rchild==NULL)
{
  cout<<"删除失败！"<<endl;
  return NULL;
}
p=parent->rchild;
parent->rchild=NULL;
delete p;
return bt;
}

//访问当前节点的数据域
void Visit(BiTNode *bt)
{
cout<<" "<<bt->data<<" ";
}

//层次遍历
void LevelOrder(BiTree bt)
{
BiTree Queue[max];
int front,rear;
if(bt==NULL)
  return;
front=-1;
rear=0;
Queue[rear]=bt;
while(front!=rear)
{
  front++;
  Visit(Queue[front]);
  if(Queue[front]->lchild!=NULL)
  {
   rear++;
   Queue[rear]=Queue[front]->lchild;
  }
  if(Queue[front]->rchild!=NULL)
  {
   rear++;
   Queue[rear]=Queue[front]->rchild;
  }
}
}

//主函数
void main()
{
BiTree lbt;
BiTree rbt;
BiTree newtree=NULL;
Initiate(lbt);
Initiate(rbt);

//应该怎样实现呢?用以输入和输出二叉树的数据
}[/code]

本帖地址： http://bbs.pfan.cn/post/319572.html

回复列表（共5个回复）

沙发

强强 [专家分：4740] 发布于 2010-04-11 19:00:00

貌似一个牛人说过用队列的,楼主想想吧

板凳

gz_lwz008@163.com [专家分：0] 发布于 2010-04-12 20:04:00

不清楚

3 楼

moke5 [专家分：30] 发布于 2010-09-10 20:45:00

寻找一直寻找机会的人！
一个趋势中的趋势的项目！
一个直销和传销终结者的项目！
一个帮助普通创业者成功的项目！
我们在互联网上正在拓展一个生意项目,现在正在寻求合作伙伴。我们认为成功的关键是你是什么人？还有你和谁在一起。我们在乎的是--您是否是有激情、有梦想的人。有意者请跟我们联系，我们和您谈谈，给您讲解一些生意概念，或许我们可以合作。一个集即时网游、交友，娱乐游戏，网络品牌代理商城，互联网平台项目招商进行中……详情QQ空间资料
网商咨询摩客天宇QQ 909065437

4 楼

清水漂鞋 [专家分：10] 发布于 2010-09-20 10:58:00

这个存入头文件"bitree.h"
#ifndef _DATE_H
#define _DATE_H
#define N 50
typedef struct BiTNode
{
    char data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

class bitree
{
public:
    int CreatBiTree(BiTree &T);
    int DeleteChild(BiTree &T,char e);
    int InsertChild(BiTree &T,char e);
    int PreOrderTraverse(BiTree T,int(*vist)(char e));
    int InOrderTraverse(BiTree T,int(*vist)(char e));
    int PostOrderTraverse(BiTree T,int(*vist)(char e));
    int LevelOrderTraverse(BiTree T,int(*vist)(char e));
    int FindChild(BiTree T,char e,BiTree &p,int &f);

};

#endif

以下存入文件"fuction.cpp"
#include "bitree.h"
#include <iostream>
#include <queue>
using namespace std;
char a[N];
int bitree::CreatBiTree(BiTree &T)
{
    char ch;
    cin>>ch;
    if(ch=='#')
        T=NULL;
    else
    {
        T->data=ch;
        T->lchild=new BiTNode;
        CreatBiTree(T->lchild);
        T->rchild=new BiTNode;
        CreatBiTree(T->rchild);
    }
    return 1;
}
int bitree::FindChild(BiTree T,char e,BiTree &p,int &f)
{
    if(T)
    {
        if(e==T->data)
            return 0;
        p=T;
        f=0;
        if(FindChild(T->lchild,e,p,f))
        {
            p=T;
            f=1;
            if(FindChild(T->rchild,e,p,f))
                return 1;
        }
        return 0;
    }
    else
        return 1;
}
int bitree::DeleteChild(BiTree &T,char e)
{
    BiTree p=NULL;
    int f=0;
    if(FindChild(T,e,p,f))
    {
        cout<<"没有找到"<<e<<endl;
        return 0;
    }
    if(p==NULL)
    {
        T=NULL;
        return 1;
    }
    if(f)
        p->rchild=NULL;
    else
        p->lchild=NULL;
    return 1;
}
int bitree::InsertChild(BiTree &T,char e)
{
    BiTree p=NULL,q;
    int f=0;
    if(FindChild(T,e,p,f))
    {
        cout<<"没有找到"<<e<<endl;
        return 0;
    }
    q=new BiTNode;
    cout<<"输入插入的值:";
    cin>>q->data;
    if(f)
    {
        q->rchild=p->rchild;
        p->rchild=q;
        q->lchild=NULL;
    }
    else
    {
        q->lchild=p->lchild;
        q->lchild=q;
        q->rchild=NULL;
    }
    return 1;
}
int bitree::PreOrderTraverse(BiTree T,int(*vist)(char e))
{
    if(T)
    {
        if(vist(T->data))
            if(PreOrderTraverse(T->lchild,vist))
                if(PreOrderTraverse(T->rchild,vist))
                    return 1;
                return 0;
    }
    else
        return 1;
}
int bitree::InOrderTraverse(BiTree T,int(*vist)(char e))
{
    if(T)
    {
        if(InOrderTraverse(T->lchild,vist))
            if(vist(T->data))
                if(InOrderTraverse(T->rchild,vist))
                    return 1;
                return 0;
    }
    else
        return 1;
}
int bitree::PostOrderTraverse(BiTree T,int(*vist)(char e))
{
    if(T)
    {
        if(PostOrderTraverse(T->lchild,vist))
            if(PostOrderTraverse(T->rchild,vist))
                if(vist(T->data))
                    return 1;
                return 0;
    }
    else
        return 1;
}

int bitree::LevelOrderTraverse(BiTree T,int(*vist)(char e))
{
    queue<BiTree> p;
    BiTree q;
    if(T!=NULL)
    {
        p.push(T);
        while(!p.empty())
        {
            q=p.front();
            vist(q->data);
            p.pop();
            if(q->lchild!=NULL)
                p.push(q->lchild);
            if(q->rchild!=NULL)
                p.push(q->rchild);
        }//endwhile
    }//endif
    return 1;
}

5 楼

清水漂鞋 [专家分：10] 发布于 2010-09-20 10:58:00

以下存入"main.cpp"
#include "bitree.h"
#include <iostream>

using namespace std;
int print(char x)
{
    cout<<x<<" ";
    return 1;
}
void main()
{
    BiTree HT;
    HT=new BiTNode;
    bitree tree;
    cout<<"创建一个树:"<<endl;
    tree.CreatBiTree(HT);
    cout<<"1删除结点 2增加结点"<<endl;
    cout<<"3先序遍历 4中序遍历"<<endl;
    cout<<"5后序遍历 6层序遍历"<<endl;
    cout<<"7退出"<<endl;
    int x=0;
    while(x<7)
    {
        cout<<"输入你的选择:";
        cin>>x;
        switch(x)
        {
        case 1:
            {
                char e1;
                cout<<"输入删除的结点的值:";
                cin>>e1;
                tree.DeleteChild(HT,e1);
            }break;
        case 2:
            {
                char e2;
                cout<<"输入增加的结点的位置值:";
                cin>>e2;
                tree.InsertChild(HT,e2);
            }break;
        case 3:
            {
                tree.PreOrderTraverse(HT,print);
                cout<<endl;
            }break;
        case 4:
            {
                tree.InOrderTraverse(HT,print);
                cout<<endl;
            }break;
        case 5:
            {
                tree.PostOrderTraverse(HT,print);
                cout<<endl;
            }break;
        case 6:
            {
                tree.LevelOrderTraverse(HT,print);
                cout<<endl;
            }break;
        }
    }
}

基本上实现几种功能了

我来回复

您尚未登录，请登录后再回复。点此登录或注册

主题：二叉树的实现?

回复列表（共5个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：二叉树的实现?

回复列表 （共5个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共5个回复）