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

总体设计：设计单向链表实现对二叉树的查询和插入操作要求：
（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