数据结构实验2：二叉树的应用

实验内容：

1．输入字符序列，建立二叉链表。
2．中序遍历二叉树：递归算法。
3．中序遍历二叉树：非递归算法。（最好也实现先序，后序非递归算法）
4．求二叉树的高度。
5．求二叉树的叶子数。
6．借助队列实现二叉树的层次遍历。
7．在主函数中设计一个简单的菜单，调用上述算法。

实验说明:

二叉链表存储

   #define  ElemType  char  // 元素类型 
   typedef  struct  BiTNode
   {
ElemType  data; 
      BiTNode  *Lchild,  *Rchild ; 
   } BiTNode,  *pBiTree ; 

源代码:

    
#include<iostream>
#include<stdlib.h>
using namespace std;
typedef char ElemType;  //定义二叉树结点值的类型为字符型

typedef struct BiTNode //二叉链表的定义
{
    ElemType data;
    struct BiTNode *Lchild, *Rchild;
}BiTNode, *BiTree;

void create_bt(BiTree &T)//建立二叉树 
{
    ElemType e;
    cin >> e;
    if (e == '#') T = NULL;
    else {
        T = (BiTree)malloc(sizeof(BiTNode));
        T->data = e;
        create_bt(T->Lchild);
        create_bt(T->Rchild);
    }
}

void preorder(BiTree T)//先序遍历
{
    if (T == NULL)
        return;
    cout << T->data;
    preorder(T->Lchild);
    preorder(T->Rchild);
}

void inorder(BiTree T)//中序遍历
{
    if (T == NULL)
        return;

    preorder(T->Lchild);
    cout << T->data;
    preorder(T->Rchild);
}

void postorder(BiTree T)//后序遍历
{
    if (T == NULL)
        return;
    preorder(T->Lchild);
    preorder(T->Rchild);
    cout << T->data;
}

int treedepth(BiTree T)//计算二叉树的高度
{
    int hl, hr, max;
    if (T != NULL)
    {
        hl = treedepth(T->Lchild);
        hr = treedepth(T->Rchild);
        max = (hl > hr) ? hl : hr;
        return max + 1;
    }
    else 
        return 0;
}
int leafcount(BiTree T)//求二叉树的叶子个数
{
    static  int  count = 0;
    if (T == NULL)  return (0);
    if (T->Lchild == NULL &&
        T->Rchild == NULL)
        count++;  //叶节点特点？
    leafcount(T->Lchild);
    leafcount(T->Rchild);
    return count;

}

#define M 100
BiTree que[M];
int front = 0, rear = 0;
void enqueue(BiTree T)
{

    if (front != (rear + 1) % M)
    {
        rear = (rear + 1) % M;
        que[rear] = T;
    }
}
BiTree queue()
{
    if (front == rear)
        return NULL;
    front = (front + 1) % M;
    return(que[front]);
}
void levelorder(BiTree T)  //层次遍历二叉树
{
    BiTree p;
    if (T)
    {
        enqueue(T);
        while (front != rear) {
            p = queue();
            cout << p->data;
            if (p->Lchild != NULL)enqueue(p->Lchild);
            if (p->Rchild != NULL)enqueue(p->Rchild);
        }
    }
}
int main()
{
    BiTree T=0;
    int num;
    cout << "1．输入字符序列，建立二叉链表" << endl;
    cout << "2．先序遍历二叉树：递归算法" << endl;
    cout << "3．中序遍历二叉树：递归算法" << endl;
    cout << "4．后序遍历二叉树：递归算法" << endl;
    cout << "5．借助队列实现二叉树的层次遍历" << endl;
    cout << "6．求二叉树的高度" << endl;
    cout << "7．求二叉树的叶子数" << endl;
    cout << "8.退出";
    cout << endl;
    while (true)
    {
        cout << "请输入一个数字选项:";
        cin >> num;
        switch (num)
        {
        case 1: //调用递归建立二叉树算法
        {
            cout << "请输入二叉树各结点值:";
            create_bt(T);
            cout << endl;
        }break;
        case 2:
        {
            cout << "先序遍历二叉树:";
            preorder(T);
            cout << endl;
        }break;
        case 3:
        {
            cout << "中序遍历二叉树:";
            inorder(T);
            cout << endl;
        }break;
        case 4:
        {
            cout << "后序遍历二叉树:";
            postorder(T);
            cout << endl;
        }break;
        case 5:
        {
            cout << "层次遍历二叉树：";
            levelorder(T);
            cout << endl;
        }break;
        case 6:
        {
            cout << "二叉树的高度为：";
            cout << treedepth(T);
            cout << endl;
        }break;
        case 7:
        {
            cout << "二叉树的叶子结点数为：";
            cout << leafcount(T);
            cout << endl;
        }break;
        case 8:
        {
            return 0;
        }break;
        default:
            cout << "输入错误！请重新输入！" << endl;
        }
    }
}

运行截图：

image
image