山东大学数据结构与算法分析: 实验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;
}