山东大学数据结构与算法分析: 实验3 二叉树的编程与实现

一、实验目的

掌握指针变量、动态变量的含义,掌握二叉树的结构特征,以及各种存储结构的特点及适用范围,掌握指针类型描述、访问和处理二叉树的运算;

二、实验原理

参照课本p.95-107, Figure4.13-4.25;

三、实验内容

已知以二叉树表作为存储结构,写出按层次顺序遍历二叉树的算法

算法思想:本算法采用一个队列q,先将二叉树根节点入队列,然后退队列,输出该节点,若它有左子树,便将左子树根节点入队列;若有右子树,便将右子树根节点入队列,直到队列空为止。因为队列的特点是先进先出,从而达到按层次顺序遍历二叉树的目的。

四、实验要求                                                                              

1)实现二叉树表的层次遍历算法,并给出应用。

五、实验源程序

#include<malloc.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

struct TreeNode;
//定义一个TreeNode类型的结构体指针
typedef struct TreeNode *SearchTree;
struct TreeNode
{
    int Element;
    SearchTree Left;
    SearchTree Right;
};
//插入
SearchTree Insert(int X, SearchTree T)
 { 
    if (T == NULL) 
    { 
        T = (SearchTree)malloc(sizeof(struct TreeNode)); 
        
            T->Element = X; 
            T->Left = T->Right = NULL; 
    } 
    else 
        //递归实现插入
        if (X < T->Element) 
            T->Left = Insert(X, T->Left); 
        else 
            //递归实现插入
            if (X > T->Element)
                T->Right = Insert(X, T->Right);
        return T; 
}

//顺序遍历函数
void Order(SearchTree T)
{ 
    if (T != NULL) 
    { 
        printf("%d ",T->Element); 
        Order(T->Left); 
        Order(T->Right); 
    } 
}

//主函数
int main()
{
    printf("输入序列: \n"); 
    SearchTree T = NULL;  
    char tmp; 
    while (scanf("%c", &tmp)) 
    { 
        if (tmp == '\n') 
            break; 
        T = Insert(tmp-48, T);
    }
    printf("顺序遍历结果为  :\n");
    Order(T);
    printf("\n");
    return 0;
}

© 版权声明
THE END
喜欢就支持以下吧
点赞0赞赏 分享
评论 抢沙发

请登录后发表评论

    暂无评论内容