二叉树基本操作设计及实现

时间:2022-12-14 17:33:21
总体设计:设计单向链表实现对二叉树的查询和插入操作要求: 
(1)设计单向链表,实现二叉树的生成。
(2)实现对二叉树的遍历查询;
(3)实现对二叉树叶节点的增加 

10 个解决方案

#1


又是学生作业题??

#2


我刚编了一个二叉树的基本操作程序,给你参考一下吧~
#include<iostream>
using namespace std;
typedef struct BiTNode 
{
    char data;
    struct BiTNode* lchild;
    struct BiTNode* rchild;
}Bitnode,*BiTree;
BiTree createbintree() 

    BiTree t; 
    char x; 
    //  scanf("%c",&x); 
    cin>>x;
    if(x=='#') 
        t=NULL; 
    else 
    { 
        //      t=(BTNode*)malloc(sizeof(BTNode)); 
        t=new Bitnode;
        t->data=x; 
        cout<<"请输入"<<x<<"的左子树(若无请输入#):";
        t->lchild=createbintree(); 
        cout<<"请输入"<<x<<"的右子树(若无请输入#):";
        t->rchild=createbintree(); 
    } 
    return(t); 


//先序遍历二叉树,并输出结果
void Preorder(BiTree t)
{
    if(t!=NULL)
    {
        cout<<t->data<<"->";//输出根节点
        Preorder(t->lchild);
        Preorder(t->rchild);//递归访问左右子树
    }
//    else
//        cout<<"先序遍历结束\n";
}
//中序遍历二叉树,并输出结果
void Inorder(BiTree t)
{
    if(t!=NULL)
    {
        Inorder(t->lchild);
        cout<<t->data<<"->";
        Inorder(t->rchild);
    }
//    else
//        cout<<"中序遍历结束\n"; 
}
//后序遍历二叉树
void Postorder(BiTree t)
{
    if(t!=NULL)
    {
        Postorder(t->lchild);
        Postorder(t->rchild);
        cout<<t->data<<"->";
    }
//    else
//        cout<<"后序遍历结束\n"; 

//统计二叉树的结点个数 
int Nodecount(BiTree t)
{
    int n=0;
    if(t==NULL)
    {
        return 0;
    }
    else
    {
        n=1+Nodecount(t->lchild)+Nodecount(t->rchild);
        return n;
    }
}
//统计叶节点个数
int Leafcount(BiTree t)
{
    int n=0,n1,n2;
    if(t==NULL)
        return 0;
    else if(t->lchild==NULL&&t->rchild==NULL)
    {
        return 1;
    }
    else
    {
        n1=Leafcount(t->lchild);
        n2=Leafcount(t->rchild);
        n=n1+n2;
        return n;
    }
}
//计算二叉树深度
int Depth(BiTree t)
{
    int n1,n2;
    if(t==NULL)
        return 0;
    else
    {
        n1=Depth(t->lchild);
        n2=Depth(t->rchild);
        if(n1>n2)
            return (n1+1);
        else 
            return (n2+1);
    }

int main()
{
    char n;
    BiTree t;


    cout<<"二叉树的基本操作!\n";
    cout<<"首先创建一棵二叉树\n"; 
    cout<<"请输入头结点(以'#'为结束)\n";
    t=createbintree();
        Preorder(t);
    cout<<endl;
    cout<<"请输入数字选择操作\n";
    cout<<"--1、输出先序遍历二叉树结果--\n";
    cout<<"--2、输出中序遍历二叉树结果--\n";
    cout<<"--3、输出后序遍历二叉树结果--\n";
    cout<<"--4、计算二叉树节点数      --\n";
    cout<<"--5、计算叶子节点数        --\n";
    cout<<"--6、计算二叉树深度        --\n";
    cout<<"--7、退出                  --\n"; 

    cin>>n;
    while(n!='7')
    { 
        switch(n)
        {
        case '1':
        //    system("cls");
            cout<<endl;
            Preorder(t);
            break;
        case '2':
        //    system("cls");
            cout<<endl;
            Inorder(t);
            break;
        case '3':
    //        system("cls");
            cout<<endl;
            Postorder(t);
            break;
        case '4':
        //    system("cls");
            cout<<endl;
            cout<<"二叉树节点数:"<<Nodecount(t);
            break;
        case '5':
        //    system("cls");
            cout<<endl;
            cout<<"叶子的数:"<<Leafcount(t);
            break;
        case '6':
        //    system("cls");
            cout<<endl;
            cout<<"二叉树深度:"<<Depth(t);
            break;
        case '7':
        //    system("pause");
            cout<<endl;
            exit(1);
            break; 
        default:
            cout<<"输入有误!!\n";
        }
        cout<<endl;
        cout<<"请输入数字选择操作\n";
        cout<<"--1、输出先序遍历二叉树结果--\n";
        cout<<"--2、输出中序遍历二叉树结果--\n";
        cout<<"--3、输出后序遍历二叉树结果--\n";
        cout<<"--4、计算二叉树节点数      --\n";
        cout<<"--5、计算叶子节点数        --\n";
        cout<<"--6、计算二叉树深度        --\n";
        cout<<"--7、退出                  --\n";
        cin>>n;
    }
    system("pause");

    return 1;

#3


采用的是先序遍历创建二叉树

#4


每天回帖即可获得10分可用分!

#5


快结贴吧~
快结贴吧~
快结贴吧~
O(∩_∩)O哈哈~
快没分可用了。
希望可以分多一点分。

#6


数据结构的考试题??

#7


学习中

#8


单向链表实现二叉树?
到底是单向链表还是二叉树?

如果单向链表带索引的话,i是父节点,2i+1是右节点,2i左节点。

#9


该回复于2010-11-12 13:48:34被版主删除

#10


请楼主改写一下,不就可以了?

#1


又是学生作业题??

#2


我刚编了一个二叉树的基本操作程序,给你参考一下吧~
#include<iostream>
using namespace std;
typedef struct BiTNode 
{
    char data;
    struct BiTNode* lchild;
    struct BiTNode* rchild;
}Bitnode,*BiTree;
BiTree createbintree() 

    BiTree t; 
    char x; 
    //  scanf("%c",&x); 
    cin>>x;
    if(x=='#') 
        t=NULL; 
    else 
    { 
        //      t=(BTNode*)malloc(sizeof(BTNode)); 
        t=new Bitnode;
        t->data=x; 
        cout<<"请输入"<<x<<"的左子树(若无请输入#):";
        t->lchild=createbintree(); 
        cout<<"请输入"<<x<<"的右子树(若无请输入#):";
        t->rchild=createbintree(); 
    } 
    return(t); 


//先序遍历二叉树,并输出结果
void Preorder(BiTree t)
{
    if(t!=NULL)
    {
        cout<<t->data<<"->";//输出根节点
        Preorder(t->lchild);
        Preorder(t->rchild);//递归访问左右子树
    }
//    else
//        cout<<"先序遍历结束\n";
}
//中序遍历二叉树,并输出结果
void Inorder(BiTree t)
{
    if(t!=NULL)
    {
        Inorder(t->lchild);
        cout<<t->data<<"->";
        Inorder(t->rchild);
    }
//    else
//        cout<<"中序遍历结束\n"; 
}
//后序遍历二叉树
void Postorder(BiTree t)
{
    if(t!=NULL)
    {
        Postorder(t->lchild);
        Postorder(t->rchild);
        cout<<t->data<<"->";
    }
//    else
//        cout<<"后序遍历结束\n"; 

//统计二叉树的结点个数 
int Nodecount(BiTree t)
{
    int n=0;
    if(t==NULL)
    {
        return 0;
    }
    else
    {
        n=1+Nodecount(t->lchild)+Nodecount(t->rchild);
        return n;
    }
}
//统计叶节点个数
int Leafcount(BiTree t)
{
    int n=0,n1,n2;
    if(t==NULL)
        return 0;
    else if(t->lchild==NULL&&t->rchild==NULL)
    {
        return 1;
    }
    else
    {
        n1=Leafcount(t->lchild);
        n2=Leafcount(t->rchild);
        n=n1+n2;
        return n;
    }
}
//计算二叉树深度
int Depth(BiTree t)
{
    int n1,n2;
    if(t==NULL)
        return 0;
    else
    {
        n1=Depth(t->lchild);
        n2=Depth(t->rchild);
        if(n1>n2)
            return (n1+1);
        else 
            return (n2+1);
    }

int main()
{
    char n;
    BiTree t;


    cout<<"二叉树的基本操作!\n";
    cout<<"首先创建一棵二叉树\n"; 
    cout<<"请输入头结点(以'#'为结束)\n";
    t=createbintree();
        Preorder(t);
    cout<<endl;
    cout<<"请输入数字选择操作\n";
    cout<<"--1、输出先序遍历二叉树结果--\n";
    cout<<"--2、输出中序遍历二叉树结果--\n";
    cout<<"--3、输出后序遍历二叉树结果--\n";
    cout<<"--4、计算二叉树节点数      --\n";
    cout<<"--5、计算叶子节点数        --\n";
    cout<<"--6、计算二叉树深度        --\n";
    cout<<"--7、退出                  --\n"; 

    cin>>n;
    while(n!='7')
    { 
        switch(n)
        {
        case '1':
        //    system("cls");
            cout<<endl;
            Preorder(t);
            break;
        case '2':
        //    system("cls");
            cout<<endl;
            Inorder(t);
            break;
        case '3':
    //        system("cls");
            cout<<endl;
            Postorder(t);
            break;
        case '4':
        //    system("cls");
            cout<<endl;
            cout<<"二叉树节点数:"<<Nodecount(t);
            break;
        case '5':
        //    system("cls");
            cout<<endl;
            cout<<"叶子的数:"<<Leafcount(t);
            break;
        case '6':
        //    system("cls");
            cout<<endl;
            cout<<"二叉树深度:"<<Depth(t);
            break;
        case '7':
        //    system("pause");
            cout<<endl;
            exit(1);
            break; 
        default:
            cout<<"输入有误!!\n";
        }
        cout<<endl;
        cout<<"请输入数字选择操作\n";
        cout<<"--1、输出先序遍历二叉树结果--\n";
        cout<<"--2、输出中序遍历二叉树结果--\n";
        cout<<"--3、输出后序遍历二叉树结果--\n";
        cout<<"--4、计算二叉树节点数      --\n";
        cout<<"--5、计算叶子节点数        --\n";
        cout<<"--6、计算二叉树深度        --\n";
        cout<<"--7、退出                  --\n";
        cin>>n;
    }
    system("pause");

    return 1;

#3


采用的是先序遍历创建二叉树

#4


每天回帖即可获得10分可用分!

#5


快结贴吧~
快结贴吧~
快结贴吧~
O(∩_∩)O哈哈~
快没分可用了。
希望可以分多一点分。

#6


数据结构的考试题??

#7


学习中

#8


单向链表实现二叉树?
到底是单向链表还是二叉树?

如果单向链表带索引的话,i是父节点,2i+1是右节点,2i左节点。

#9


该回复于2010-11-12 13:48:34被版主删除

#10


请楼主改写一下,不就可以了?