实验4：二叉树操作
（第十三周星期四8-10节）
一 、实验目的
1．学会实现二叉树结点结构和对二叉树的基本操作。
2．掌握对二叉树每种操作的具体实现，学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。
二 、实验要求
1．认真阅读和掌握和本实验相关的教材内容。
2．编写完整程序完成下面的实验内容并上机运行。
3．整理并上交实验报告。
三、实验内容
1．编写程序任意输入二叉树的结点个数和结点值，构造一棵二叉树，采用三种递归遍历算法(前序、中序、后序)对这棵二叉树进行遍历并计算出二叉树的高度。
2 .编写程序生成下面所示的二叉树，并采用中序遍历的非递归算法对此二叉树进行遍历。
四、源代码、结果：
1、
#include<iostream.h>
#include<stdlib.h>
typedef char ElemType;
struct BTreeNode {
    ElemType data;
    BTreeNode*left;
    BTreeNode*right;
};
void InitBTree(BTreeNode*& BT)
{
    BT=NULL;
}
void CreateBTree(BTreeNode*& BT,char*a)
{
    const int MaxSize=10;
    BTreeNode*s[MaxSize];
    int top=-1;
    BT=NULL;
    BTreeNode*p;
    int k;
    int i=0;
    while(a[i])
    {
        switch(a[i]){
        case' ':
            break;
        case'(':
            if(top==MaxSize-1) {
                cout<<"栈空间太小，请增加MaxSize的值!"<<endl;
                exit(1);
            }
            top++;s[top]=p;k=1;
            break;
        case')':
            if(top==-1) {
                cout<<"二叉树广义表字符串错!"<<endl;exit(1);
            }
            top--;break;
        case',':
            k=2;break;
        default:
            p=new BTreeNode;
            p->data=a[i];p->left=p->right=NULL;
            if(BT==NULL) BT=p;
            else{
                if(k==1) s[top]->left=p;
                else s[top]->right=p;
            }
        }
        i++;
    }
}
bool EmptyBTree(BTreeNode*BT)
{
    return BT==NULL;
}
int DepthBTree(BTreeNode*BT)
{
    if(BT==NULL)
        return 0;
    else{
        int dep1=DepthBTree(BT->left);
        int dep2=DepthBTree(BT->right);
        if(dep1>dep2)
            return dep1+1;
        else
            return dep2+1;
    }
}
bool FindBTree(BTreeNode*BT,ElemType& x)
{
    if(BT==NULL) return false;
    else {
        if(BT->data==x) {
            x=BT->data; return true;
        }
        else {
            if(FindBTree(BT->left,x)) return true;
            if(FindBTree(BT->right,x)) return true;
            return false;
        }
    }
}
void PrintBTree(BTreeNode*BT)
{
    if(BT!=NULL) {
        cout<<BT->data;
        if(BT->left!=NULL||BT->right!=NULL) {
            cout<<'(';
            PrintBTree(BT->left);
            if(BT->right!=NULL)
                cout<<',';
            PrintBTree(BT->right);
            cout<<')';
        }
    }
}
void ClearBTree(BTreeNode*&BT)
{
    if(BT!=NULL) {
        ClearBTree(BT->left);
        ClearBTree(BT->right);
        delete BT;
        BT=NULL;
    }
}
void PreOrder(BTreeNode*BT)
{
    if(BT!=NULL) {
        cout<<BT->data<<' ';
        PreOrder(BT->left);
        PreOrder(BT->right);
    }
}
void InOrder(BTreeNode*BT)
{
    if(BT!=NULL) {
        InOrder(BT->left);
        cout<<BT->data<<' ';
        InOrder(BT->right);
    }
}
void PostOrder(BTreeNode*BT)
{
    if(BT!=NULL) {
        PostOrder(BT->left);
        PostOrder(BT->right);
        cout<<BT->data<<' ';
    }
}
void main()
{
    BTreeNode*bt;
    InitBTree(bt);
    char b[50];
二叉树中序遍历非递归算法    cout<<"输入二叉树用广义表表示的字符串!"<<endl;
        line(b,sizeof(b));
    CreateBTree(bt,b);
    PrintBTree(bt);cout<<endl;
    cout<<"前序："; PreOrder(bt); cout<<endl;
    cout<<"中序："; InOrder(bt); cout<<endl;
    cout<<"后序:";PostOrder(bt);cout<<endl;
    ElemType x;
    cout<<"输入一个待查字符：";
    cin>>x;
    if(FindBTree(bt,x)) cout<<"查字符"<<x<<"成功"<<endl;
    else cout<<"查字符"<<x<<"失败!"<<endl;
    cout<<"深度: ";cout<<DepthBTree(bt)<<endl;

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。