2021-12-11 【数据结构平时实验】【树】

2021-12-11 【数据结构平时实验】【树】 6-1.采用先序遍历方法建立一棵二叉树，对其进行中序遍历，输出结果。 code:

#include 
using namespace std;
#define TElemType char
#define Status int
//------------二叉树的二叉链表存储表示-------------
typedef struct BiTNode
{
    TElemType data;
    struct BiTNode *lchild, *rchild; //左右孩子指针
} BiTNode, *BiTree;

Status CreateBiTree(BiTree &T){ 
    //算法6.4
    TElemType ch;
    scanf("%c", &ch);
    if (ch == '#') 
        T = NULL;
    else
    {
        T = (BiTree)malloc(sizeof(BiTNode));
        if (!T)
            exit(_OVERFLOW);
        T->data = ch;             
        CreateBiTree(T->lchild); 
        CreateBiTree(T->rchild);
    }
    return 1;
}

Status Visit(TElemType e){
    cout << e <<" ";
    return 1;
}

//中序遍历
Status InOrderTraverse(BiTree T,Status Visit(TElemType e)){
    if(T!=NULL){
	    InOrderTraverse(T->lchild, Visit);
	    Visit(T->data);
	    InOrderTraverse(T->rchild, Visit);
	}
    return 1;
}

int main(){
	printf("测试代码n");
	BiTree T;
	T = (BiTree)malloc(sizeof(BiTNode));
	printf("请给二叉树按照先序方式依次输入结点的值(空结点为#):n");
	CreateBiTree(T);
	printf("中序方式遍历结果：n");
	InOrderTraverse(T,Visit);
	printf("n");
	return 0;

}

6-2.实现二叉树的层序遍历的算法 code:

#include 
using namespace std;
#define TElemType char
#define Status int
//------------二叉树的二叉链表存储表示-------------
typedef struct BiTNode
{
    TElemType data;
    struct BiTNode *lchild, *rchild; //左右孩子指针
} BiTNode, *BiTree;

Status CreateBiTree(BiTree &T){ 
    //算法6.4
    TElemType ch;
    scanf("%c", &ch);
    if (ch == '#') 
        T = NULL;
    else
    {
        T = (BiTree)malloc(sizeof(BiTNode));
        if (!T)
            exit(_OVERFLOW);
        T->data = ch;             
        CreateBiTree(T->lchild); 
        CreateBiTree(T->rchild);
    }
    return 1;
}

Status Visit(TElemType e){
    cout << e <<" ";
    return 1;
}

//层次遍历
#define QElemType BiTree
#define Status int
//---------链队列实现--------------
typedef struct QNode{
    QElemType data;
    struct QNode *next;
} QNode, *QueuePtr;

typedef struct{
    QueuePtr front;
    QueuePtr rear;
} linkQueue;
Status QueueEmpty(linkQueue Q){
    if (Q.front == Q.rear)
        return 1;
    else
        return 0;
}
Status InitQueue(linkQueue &Q){
    Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
    if (!Q.front)
        exit(_OVERFLOW);
    Q.front->next = NULL;
    return 1;
}
Status EnQueue(linkQueue &Q, QElemType e){
    QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
    if (!p)
        exit(_OVERFLOW);
    p->data = e;
    p->next = NULL;
    Q.rear->next = p; 
    Q.rear = p;    
    return 1;
}

Status DeQueue(linkQueue &Q, QElemType &e){
    QueuePtr p;
    if (Q.front == Q.rear)
        return 0;
    p = Q.front->next;   
    e = p->data;           
    Q.front->next = p->next; 
    if (Q.rear == p)  
        Q.rear = Q.front;
    free(p);
    return 1;
}
Status LevelOrderTraverse(BiTree &T){
	linkQueue lq;
    InitQueue(lq);
    QElemType q;
    EnQueue(lq, T);
    while (QueueEmpty(lq) != 1){ //队列不空，则出队
        DeQueue(lq, q);
        printf("%c ", q->data);
        if(q->lchild)
            EnQueue(lq, q->lchild); //若有左孩子，则入队
        if(q->rchild)
            EnQueue(lq, q->rchild); //若有右孩子，则入队
    }
    return 1; 
}

int main(){
    printf("测试代码n");
	BiTree T;
	T = (BiTree)malloc(sizeof(BiTNode));
	printf("请给二叉树按照先序方式依次输入结点的值(空结点为#):n");
	CreateBiTree(T);
	printf("层序方式遍历结果：n");
	LevelOrderTraverse(T);
	printf("n");
    return 0;
}

6-3.建立二叉树，实现二叉树的先序、中序、后序遍历的递归算法。 code:

#include 
using namespace std;
#define TElemType char
#define Status int
//------------二叉树的二叉链表存储表示-------------
typedef struct BiTNode
{
    TElemType data;
    struct BiTNode *lchild, *rchild; //左右孩子指针
} BiTNode, *BiTree;

Status CreateBiTree(BiTree &T){ 
    //算法6.4
    TElemType ch;
    scanf("%c", &ch);
    if (ch == '#') 
        T = NULL;
    else
    {
        T = (BiTree)malloc(sizeof(BiTNode));
        if (!T)
            exit(_OVERFLOW);
        T->data = ch;             
        CreateBiTree(T->lchild); 
        CreateBiTree(T->rchild);
    }
    return 1;
}

Status Visit(TElemType e){
    cout << e <<" ";
    return 1;
}
//先序遍历
//算法6.1
Status PreOrderTraverse(BiTree T,Status Visit(TElemType e)){
    if(T){
        Visit(T->data);
        PreOrderTraverse(T->lchild, Visit);
        PreOrderTraverse(T->rchild, Visit);
    }
    return 1;
}

//中序遍历
Status InOrderTraverse(BiTree T,Status Visit(TElemType e)){
    if(T!=NULL){
	    InOrderTraverse(T->lchild, Visit);
	    Visit(T->data);
	    InOrderTraverse(T->rchild, Visit);
	}
    return 1;
}

//后序遍历
Status PostOrderTraverse(BiTree T,Status Visit(TElemType e)){
    if(T!=NULL){
	    PostOrderTraverse(T->lchild, Visit);
	    PostOrderTraverse(T->rchild, Visit);
        Visit(T->data);
    }
    return 1;
}
int main(){
	printf("测试代码n");
	BiTree T;
	T = (BiTree)malloc(sizeof(BiTNode));
	printf("请给二叉树按照先序方式依次输入结点的值(空结点为#):n");
	CreateBiTree(T);
	printf("先序方式遍历结果：n");
	PreOrderTraverse(T,Visit);
	printf("n");
	printf("中序方式遍历结果：n");
	InOrderTraverse(T,Visit);
	printf("n");
	printf("后序方式遍历结果：n");
	PostOrderTraverse(T,Visit);
	printf("n");
	return 0;

}

6-4. 建立二叉树，实现二叉树的先序、中序遍历的非递归算法。 code:

#include 
using namespace std;
#define TElemType char
#define Status int
//------------二叉树的二叉链表存储表示-------------
typedef struct BiTNode
{
    TElemType data;
    struct BiTNode *lchild, *rchild; //左右孩子指针
} BiTNode, *BiTree;

Status CreateBiTree(BiTree &T){ 
    //算法6.4
    TElemType ch;
    scanf("%c", &ch);
    if (ch == '#') 
        T = NULL;
    else
    {
        T = (BiTree)malloc(sizeof(BiTNode));
        if (!T)
            exit(_OVERFLOW);
        T->data = ch;             
        CreateBiTree(T->lchild); 
        CreateBiTree(T->rchild);
    }
    return 1;
}

//非递归实现
#define SElemType BiTree
// -----栈的链式存储结构----------------------------------
typedef struct SNode {
    SElemType data;                 // 数据域
    struct SNode *next;             // 指针域
} SNode, *linkStack;


Status InitStack(linkStack &S) {
    S = (linkStack)malloc(sizeof(SNode));
    if(!S)                          // 存储分配失败
        exit(_OVERFLOW);             // exit(-2)程序异常退出
    S->next = NULL;
    return 1;
}
 
//  *** 作结果：销毁栈S，S不再存在。
Status DestroyStack(linkStack &S) {
    linkStack p = S->next, ptmp;    // p指向栈顶
    while(p) {                      // p指向栈底时，循环停止
        ptmp = p->next;
        free(p);                    // 释放每个数据结点的指针域
        p = ptmp;
    }
    free(S);
    return 1;
}
 
//  *** 作结果：把S置为空栈。
Status ClearStack(linkStack &S) {
    linkStack p = S->next, ptmp;    // p指向栈顶
    while(p) {                      // p指向栈底时，循环停止
        ptmp = p->next;
        free(p);                    // 释放每个数据结点的指针域
        p = ptmp;
    }
    S->next = NULL;
    return 1;
}
 
//  *** 作结果：若S为空栈，返回TRUE，否则返回FALSE
Status StackEmpty(linkStack S) {
    if(S->next == NULL)
        return 1;           
    else
        return 0;      
}
 
//  *** 作结果：返回S的元素个数，即栈的长度。
int StackLength(linkStack S) {
    int n = 0;
    linkStack p = S->next;          // p指向栈顶
    while(p) {
        n++;
        p = p->next;
    }
    return n;
}
 
//  *** 作结果：若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR。
Status GetTop(linkStack S, SElemType &e) {
    if ( S->next == NULL )
        return 0;
    e = S->next->data;     // 取栈顶元素
    return 1;
}
 
//  *** 作结果：插入元素e为新的栈顶元素。
Status Push(linkStack &S, SElemType e) {
    linkStack p = (linkStack)malloc(sizeof(SNode));
    p->data = e;
    p->next = S->next;              // 新结点指向栈顶
    S->next = p;                    // 更新栈顶指针
//  printf("插入的栈顶元素：");  visit(e);
    return 1;
}// Push
 
//  *** 作结果：若栈不空，则删除S的栈顶元素，并用e返回其值；否则返回ERROR。
Status Pop(linkStack &S, SElemType &e) {
    // 若1个元素也没有：
    if (S->next == NULL)
        return 0;
    // 若有1个以上元素
    e = S->next->data;
    linkStack ptmp = S->next->next;
    free(S->next);
    S->next = ptmp;
//  printf("删除的栈顶元素：");  visit(e);
    return 1;
}// Pop
 

Status Visit(TElemType e){
    cout << e << " ";
    return 1;
}
//先序遍历
Status PreOrderTraverse1(BiTree T,Status Visit(TElemType e))
{
	if (T == NULL)
		return 0;
    BiTree p;
    linkStack s;
    InitStack(s);
    Push(s, T);//根进栈
    while (!StackEmpty(s))
	{
		while(GetTop(s,p) && p){
            if(!Visit(p->data))
                return 0;
            Push(s, p->lchild); //左走到尽头
		}
        Pop(s, p);  //空指针退栈
        if(!StackEmpty(s)){//访问结点
            Pop(s, p);
            Push(s, p->rchild);
        }
	}
    return 1;
}

Status PreOrderTraverse2(BiTree T,Status Visit(TElemType e))
{
	if (T == NULL)
		return 0;
    BiTree p = T, e;
    linkStack s;
    InitStack(s);
    while (p || !StackEmpty(s))
	{
        if(p){          //根指针进栈，遍历左子树
            if(!Visit(p->data))
                return 0;
            Push(s, p);
            p = p->lchild;
        }else{          //根指针退栈，访问根结点，遍历右子树
            Pop(s, p);
            p = p->rchild;
        }
	}
    return 1;
}

//中序非递归实现
//算法6.2
Status InOrderTraverse1(BiTree T,Status Visit(TElemType e))
{
	if (T == NULL)
		return 0;
    BiTree p;
    linkStack s;
    InitStack(s);
    Push(s, T);//根进栈
    while (!StackEmpty(s))
	{
		while(GetTop(s,p) && p){
            Push(s, p->lchild); //左走到尽头
		}
        Pop(s, p);  //空指针退栈
        if(!StackEmpty(s)){//访问结点
            Pop(s, p);
            if(!Visit(p->data))
                return 0;
            Push(s, p->rchild);
        }
	}
    return 1;
}
//算法6.3
Status InOrderTraverse2(BiTree T,Status Visit(TElemType e))
{
	if (T == NULL)
		return 0;
    BiTree p = T, e;
    linkStack s;
    InitStack(s);
    while (p || !StackEmpty(s))
	{
        if(p){          //根指针进栈，遍历左子树
            Push(s, p);
            p = p->lchild;
        }else{          //根指针退栈，访问根结点，遍历右子树
            Pop(s, p);
            if(!Visit(p->data))
                return 0;
            p = p->rchild;
        }
	}
    return 1;
}

//后序非递归
Status PostOrderrTraverse2(BiTree T, Status(*Visit)(TElemType e))
{
	if (T == NULL)
		return 0;
	BiTree p = T, r = NULL;
	linkStack s;
	InitStack(s);
	while ( p != NULL || !StackEmpty(s))
	{
		if (p) {
			Push(s, p);
			p = p->lchild;
		}
		else
		{
			GetTop(s, p);
			if (p->rchild && p->rchild != r) {
				p = p->rchild;
				Push(s, p);
				p = p->lchild;
			}
			else
			{
				Pop(s, p);
				Visit(p->data);
				r = p;
				p = NULL;
			}
		}
    }
	return 1;
}


int main(){
	printf("测试代码n");
	BiTree T;
	T = (BiTree)malloc(sizeof(BiTNode));
	printf("请给二叉树按照先序方式依次输入结点的值(空结点为#):n");
	CreateBiTree(T);
	printf("先序方式遍历结果：n");
	PreOrderTraverse2(T,Visit);
	printf("n");
	printf("中序方式遍历结果：n");
	InOrderTraverse2(T,Visit);
	printf("n");
	printf("后序方式遍历结果：n");
	PostOrderrTraverse2(T,Visit);
	printf("n");
	return 0;

}

6-5.（选做） 建立二叉树，实现二叉树的后序遍历的非递归算法。 code见6.4；

---

更多Java内容欢迎订阅我的专栏：JAVA的自学之路 或者进入2021-12-3【JAVA】【开坑目录】

---

推荐： 我的专栏：数据结构 或者进入2021-10-16【严蔚敏数据结构代码实现合集】【c语言学习必备】学习

---

有问题欢迎评论区留言讨论，看到后我就会回复的！！！！