数据结构-二叉树算法拓展

目标效果：

bitree.h页面：

#ifndef BINTREE_H_INCLUDED
#define BINTREE_H_INCLUDED

#include <stdlib.h>
#include "ds.h"

//数据元素的缺省类型用char
#ifndef ElemType
#define ElemType char
#define ELEMTYPE_TAG
#endif
/*下面使用TElemType如同ElemType*/
#define TElemType ElemType
#define QElemType BiTree
///////////////////////////////////////////////////////////
// 二叉链表类型
typedef struct BiTNode {
    TElemType data;
    struct BiTNode *lchild, *rchild; //左右孩子指针
} BiTNode, *BiTree;
//线性表顺序结构类型定义
typedef struct {
    ElemType *elem;
    int length;
    int listsize;
} SqList;
//循环队列类型定义
typedef struct{
    QElemType *base;
    int front;
    int rear;
}SqQueue;
//查找最大节结点值
Status  selectMaxElem(BiTree T,TElemType &max);
//初始化线性表顺序结构
Status InitSqListBiTree(int num,SqList &L);
//在表L中插入元素e. 操作成功返回OK,失败时返回ERROR
void ListInsert(SqList &L, ElemType e);
//计算叶子结点个数
Status NumPoint(BiTree T,int &n);
//初始化队列
Status InitQueue(int num,SqQueue &Q);
//元素入队
Status EnQueue(SqQueue &Q,QElemType e,int num);
//元素出队
Status DeQueue(SqQueue &Q,QElemType &e,int num);
//销毁队列
Status DestroyQueue(SqQueue &Q);
//队列判空
Status QueueEmpty(SqQueue Q);

// 二叉链表的基本操作

//新建二叉链表结点
BiTree MakeNode(TElemType e, BiTree lch, BiTree rch)
{
    BiTree p = (BiTree)malloc(sizeof(BiTNode));
    p->data = e;
    p->lchild = lch;
    p->rchild = rch;
    return p;
}

//按先序次序输入二叉树中的结点值(字符)构造二叉树
Status CreateBiTree(BiTree &T)
{
    char ch;
    read(ch); // NOTE: 这里用字符类型
    if( ch==' ' ) //空格代表空指针
        T = 0;
    else {
		T=(BiTree)malloc(sizeof(BiTNode));
		if(!T)
			return ERROR;
		else{
			T->data=ch;
			CreateBiTree(T->lchild);
			CreateBiTree(T->rchild);
		}
    }
    return OK;
}

//销毁二叉树
Status DestroyBiTree(BiTree &T)
{
    T=NULL;
    return OK;
}

//以直观方式打印二叉树
void PrintTree(BiTree t, int level=0)
{
    int i;
    if(t) {
        PrintTree(t->rchild, level+1);
        for(i=0; i<level; i++) printf("    ");
        write(t->data); write('\n');
        PrintTree(t->lchild, level+1);
    }
}

/////////////////////////////////////////
//交换左右子树
Status Exchange(BiTree T)
{
	BiTree P;
    if(T){
		P=T->lchild;
		T->lchild=T->rchild;
		T->rchild=P;
		Exchange(T->lchild);
		Exchange(T->rchild);
	}
    return OK;
}

//查找根结点下边的最大值
Status selectMaxElem(BiTree T,TElemType &max)
{
	if(!T)
		return ERROR;
	if(T->data>max)
		max=T->data;
	selectMaxElem(T->lchild,max);
	selectMaxElem(T->rchild,max);
	return OK;
}

//将二叉链表表示的完全二叉树转换为二叉树的顺序表示
Status ChangeOrderStorage(BiTree T)
{
    int num=0;
    NumPoint(T,num);    //树的结点个数
    if(!T)
        return ERROR;
    SqList L;
    InitSqListBiTree(num,L);    //初始化顺序结构
    //将每一层的节点分别入队列，然后分别读取，读取后继续将它们的子节点入队，所以保证是按照一层一层来遍历的
    BiTree P=T;
    SqQueue Q;
    InitQueue(num,Q);   //初始化队列
    if(P)
    {
        EnQueue(Q,P,num);
        while(!QueueEmpty(Q))
        {
            DeQueue(Q,P,num);   //出队列
            ListInsert(L,P->data);//将刚出队列的元素顺序插入顺序表
            if(P->lchild)
                EnQueue(Q,P->lchild,num);
            if(P->rchild)
                EnQueue(Q,P->rchild,num);
        }
    }
    DestroyQueue(Q);
    for(int i=0;i<L.length;i++)
       write(L.elem[i]);
    return OK;
}
//计算叶子结点个数
Status NumPoint(BiTree T,int &n)
{
    if(!T)
        return 0;
    else{
        n++;
        return NumPoint(T->lchild,n)+NumPoint(T->rchild,n);
    }
}
//初始化线性表顺序结构
Status InitSqListBiTree(int num,SqList &L)
{
    L.elem=(ElemType *)malloc(sizeof(ElemType)*num);    //分配结点个数个顺序空间
    L.length=0;
    L.listsize=num;
}
//构造一个空队列
Status InitQueue(int num,SqQueue &Q)
{
    Q.base=(QElemType *)malloc((num+1)*sizeof(QElemType));
    if(!Q.base)
        return ERROR;
    Q.front=Q.rear=0;
    return OK;
}
//元素入队
Status EnQueue(SqQueue &Q,QElemType e,int num)
{
    Q.base[Q.rear]=e;
    Q.rear=(Q.rear+1)%num;
    return OK;
}
//元素出队
Status DeQueue(SqQueue &Q,QElemType &e,int num)
{
    if(Q.front==Q.rear)
        return ERROR;
    e=Q.base[Q.front];
    Q.front=(Q.front+1)%num;
    return OK;
}
//判断队列是否为空
Status QueueEmpty(SqQueue Q)
{
    if(Q.rear==Q.front)
        return OK;
    else
        return ERROR;
}
//销毁队列
Status DestroyQueue(SqQueue &Q)
{
    if(!Q.base)
        return ERROR;
    Q.rear=Q.front;
    free(Q.base);
    return OK;
}
//在表L中插入元素e. 操作成功返回OK,失败时返回ERROR
void ListInsert(SqList &L, ElemType e)
{
    int j=L.length;
    L.elem[j]=e;
    L.length++;
}


//取消缺省类型的定义以免影响其它部分
#ifdef ELEMTYPE_TAG
#undef ElemType
#undef ELEMTYPE_TAG
#endif

#endif //BINTREE_H_INCLUDED

dsp0603.h页面：

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

#define ElemType char //二叉树中数据元素类型
#include "bintree.h"  //二叉树的实现

///////////////////////////////////////////////////////////
// 主程序
int main()
{
    BiTree bt = 0;

    //建立二叉树
    printf("建立二叉树（按先序输入二叉树中的结点,空格表示空树）\n");
    if( CreateBiTree(bt)==ERROR ) {
        printf("ERROR: call CreateBiTree\n");
        system("pause");
        exit(1);
    }
    PrintTree(bt);

	printf("\n交换左右子树:\n ");
    if( Exchange(bt)==ERROR )
		printf("ERROR: call CreateBiTree\n");
	else
        PrintTree(bt);

	printf("\n计算以T为根的二叉树中的最大元素的值: ");
	TElemType t;
	t=0;
	if( selectMaxElem(bt,t)==ERROR)
		printf("ERROR: call CreateBiTree\n");
    else
        write(t);

    printf("\n将二叉链表表示的完全二叉树转换为二叉树的顺序表示:");
    if(ChangeOrderStorage(bt)==ERROR)
        printf("ERROR: call CreateBiTree\n");

    printf("\n");
    system("pause"); //暂停以便查看结果
    return 0;
}

难点为完全二叉树转换为顺序结构，使用了队列做中间变量进行层次遍历，出队列后插入顺序表，不过貌似我想麻烦了，使用一个线性表可以直接存储，先这样吧，不改了。

源码链接：点击打开链接