二叉树的递归及非递归的遍历及其应用

2023-10-19 16:03:16

二叉树的递归及非递归的遍历及其应用（必做，设计性实验）

  1. 实验目的
    熟练掌握二叉树的二叉链表存储结构的C语言实现。掌握二叉树的基本操作-前序、中序、后序遍历二叉树的三种方法。了解非递归遍历过程中“栈”的作用和状态，而且能灵活运用遍历算法实现二叉树的其它操作。

  2. 实验内容（1&2必做，3-8选3, 10-11选1）
    （1）二叉树的二叉链表的创建（必做）
    （2）二叉树的前、中、后序遍历的递归算法（必做）
    （3）求二叉树中叶子结点数目的递归算法。
    （4）编写求二叉树深度的递归算法。
    （5）编写判断二叉树是否相似/相等的递归算法
    （6）编写求二叉树左右子树互换的递归算法
    （7）编写二叉树中位于后序序列第k个结点的值的算法
    （8）编写算法删除二叉树中所有以值为x的结点为根的子树并释放相应空间
    （9）二叉树的前/中/后序遍历的非递归算法的实现（必做）
    （10）编写二叉树层序遍历的算法
    编写判断二叉树是否是完全二叉树的算法
    创建二叉树的二叉链表结构、进行先、中、后序的递归函数显示不同遍历序列，结合习题了解二叉树遍历的应用实例。编写前、中、后、层序遍历的非遍历函数，注意用以前做过的栈和队列作辅助存储结构。掌握用遍历算法求解其它问题的方法。

  3. 数据结构定义
    该题目要求实现二叉链表的实现，所以理所应当的我们应该实现出存储二叉链表的结点的数据结构，由于是二叉树，则有两个指针指向该节点的孩子，还有一个位置用来存储数据，我们必须要开辟一块空间来存储这个。具体定义如下：

  4. 算法思想及算法设计
    本题目中出现的各个遍历算法的思想大致分为两种，一种是带有递归性质的算法，另一种不带递归性质，需要另外增加栈或者队列使得非递归算法能够实现。

Status CreateBiTree(Bitree &T) //此题仍然需要递归创建二叉树
{                              //此题目采用先序次序创建二叉树，空格仍需要表示出来，否则不能创建
   //ABC##DE#G##F###  模拟栈的数据

   char ch = '\0';
   scanf("%c", &ch);
   if (ch == '#')
       T = NULL;
   else
   {
       if (!(T = new BiTnode))
           exit(OVERFLOW);
       T->data = ch;
       CreateBiTree(T->lchild);
       CreateBiTree(T->rchild);
   }
   return OK;
}
Status PreorderTraverse(Bitree T, Status (*visit)(TElemtype e))
{
   if (T)
   {
       if (visit(T->data))
           if (PreorderTraverse(T->lchild, visit))
               if (PreorderTraverse(T->rchild, visit))
                   return OK;
       return ERROR;
   }
   else
   {
       return OK;
   }
}
Status InorderTraverse(Bitree T, Status (*visit)(TElemtype e))
{
   if (T)
   {
       InorderTraverse(T->lchild, visit);
       visit(T->data);
       InorderTraverse(T->rchild, visit);
   }
   return OK;
}
Status PostorderTraverse(Bitree T, Status (*visit)(TElemtype e))
{
   if (T)
   {
       PostorderTraverse(T->lchild, visit);
       PostorderTraverse(T->rchild, visit);
       visit(T->data);
   }
   return OK;
}
Status Equal(Bitree T1, Bitree T2)
{
   if (T1 == NULL && T2 == NULL)
       return TRUE;
   else if (T1 == NULL || T2 == NULL)
       return FALSE;
   else if (T1->data == T2->data && Equal(T1->lchild, T2->lchild) && Equal(T2->rchild, T1->rchild))
       return TRUE;
   return FALSE;
}
int leavesnumber(Bitree T)
{

   if (T->rchild == NULL && T->lchild == NULL)
       return 1;
   else if (T->rchild == NULL && T->lchild)
       return leavesnumber(T->lchild);
   else if (T->lchild == NULL && T->rchild)
       return leavesnumber(T->rchild);
   else
       return leavesnumber(T->rchild) + leavesnumber(T->rchild);
}
int depth(Bitree T)
{
   if (!T)
       return 0;
   int depth1 = depth(T->lchild);
   int depth2 = depth(T->rchild);
   return (depth1 > depth2 ? depth1 : depth2) + 1;
}
void fInorderTraverse(Bitree T, Status (*visit)(TElemtype e))
{
   Bitree stack[100];
   for (int i = 0; i < 100; i++)
       stack[i] = NULL;
   int head = 0;
   stack[head++] = T;
   while (head > 0)
   {
       while (!stack[head - 1])
           stack[head++] = T->lchild;
       if (head > 0)
       {
           visit(stack[head - 1]->data);
           head--;
           printf("1");
           stack[head] = stack[head]->rchild;
           head++;
       }
   }
}
void fPreorderTraverse2(Bitree T, Status (*visit)(TElemtype e))
{
   Bitree stack[100];
   int head = 0;
   Bitree p = T;
   while (p || head != 0)
   {
       if (p)
       {
           stack[head++] = p;

           p = p->lchild;
       }
       else
       {
           p = stack[--head];
           visit(p->data);
           p = p->rchild;
       }
   }
}
void fPostorderTraverse(Bitree T, Status (*visit)(TElemtype e))
{
   Bitree stack[100];
   int head = 0;
   stack[head++] = T;
   while (head != 0)
   {
       while (head - 1 > 0)
           stack[head++] = T->lchild;
       head--;
       while (head - 1 >= 0 && stack[head - 1]->rchild == stack[head])
       {
           visit(stack[head - 1]->data);
           head--;
       }
       if (head - 1 >= 0)
       {
           stack[head] = stack[head - 1]->rchild;
           head++;
       }
   }
}

Status LevelorderTraverse(Bitree T, Status (*visit)(TElemtype e))
{
   Bitree p = T;
   Bitree queue[100];
   int head = 0;
   int tail = 0;
   if (p)
       queue[tail++] = p; //如何使用层次遍历
   while ((head - tail) != 0)
   {
       p = queue[head];
       head++;
       visit(p->data); //对本层次的节点进行访问
       if (p->lchild)
           queue[tail++] = p->lchild;
       if (p->rchild)
           queue[tail++] = p->rchild;
   }
   return OK;
}
Status deletenode(Bitree &T, Bitree &p, TElemtype x)
{
   if (!T)
       return 0;
   if (x == T->data)
   {
       if (p->lchild == T)
       {
           free(T);
           p->lchild = NULL;
       }
       else
       {

           free(T);
           p->rchild = NULL;
       }
       return OK;
   }
   else
   {
       return deletenode(T->lchild, T, x) || deletenode(T->rchild, T, x);
   }
}
  1. 实验代码
    算法部分已在上面具有，不再输入。
#ifndef constant_h
#define constant_h
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

typedef int Status;

#endif /* constant_h */
#include "constant.h"
#include <iostream>
#define TElemtype char
using namespace std;
#define visit print
#define Status int
typedef struct BiTnode
{
   struct BiTnode *lchild, *rchild;
   TElemtype data;
} * Bitree, BiTnode;
Status CreateBiTree(Bitree &T);
Status PreorderTraverse(Bitree T, Status (*visit)(TElemtype e));
Status InorderTraverse(Bitree T, Status (*visit)(TElemtype e));
Status PostorderTraverse(Bitree T, Status (*visit)(TElemtype e));
Status LevelorderTraverse(Bitree T, Status (*visit)(TElemtype e));
Status print(TElemtype e);
Status deletenode(Bitree &T, Bitree &p, TElemtype x);
int depth(Bitree T);
Status Equal(Bitree T1, Bitree T2);
int leavesnumber(Bitree T);
void fInorderTraverse(Bitree T, Status (*visit)(TElemtype e));
void fInorderTraverse2(Bitree T, Status (*visit)(TElemtype e));
void fPreorderTraverse(Bitree T, Status (*visit)(TElemtype e));
void fPostorderTraverse(Bitree T, Status (*visit)(TElemtype e));


#include <iostream>
#include "BiTree.hpp"
#include "constant.h"
using namespace std;
Status visit(TElemtype e)
{
   printf("%c ", e);
   return OK;
}

void test01()
{
   Bitree B;
   printf("请输入你要插入的序列\n");
   CreateBiTree(B);
   printf("先序遍历序列为\n");
   PreorderTraverse(B, visit); //先序
   printf("\n中序遍历序列为\n");
   InorderTraverse(B, visit); //中序
   printf("\n后序遍历序列为\n");
   PostorderTraverse(B, visit); //后序
   printf("\n层次遍历序列为\n");
   LevelorderTraverse(B, visit); //层次遍历
   int depth(Bitree T);
   printf("树的深度为:%d\n", depth(B));
   printf("树的叶子数目为：%d", leavesnumber(B));
   printf("\n以下为演示树的比较操作\n请输入要比较的树，请用先序序列来表示,空树仍然用#表示\n");
   Bitree c;
   getchar(); //注意空字符空格字符的吸收；
   printf("请输入你要插入的序列\n");
   CreateBiTree(c);

   if (Equal(B, c))
       printf("该两个二叉树相等\n");
   else
       printf("这两棵树不相等\n");

   int leavesnumber(Bitree T);
}
void test02()
{
   Bitree B, t;
   t = NULL;
   printf("请输入你要插入的序列\n");
   CreateBiTree(B);
   char ch;
   printf("请输入你要删除的子树\n");
   getchar();
   scanf("%c", &ch);

   deletenode(B, t, ch);
   printf("删除之后的子树为：\n");
   PreorderTraverse(B, visit);
}
void test03()
{
   Bitree B;
   printf("请输入你要插入的序列\n");
   CreateBiTree(B);
   printf("非递归先序遍历序列为\n");
   fPreorderTraverse2(B, visit); //先序
   printf("\n非递归中序遍历序列为\n");
   fInorderTraverse(B, visit); //中序
   printf("\n非递归后序遍历序列为\n");
   fPostorderTraverse(B, visit); //后序
}
int main(int argc, char *argv[])
{
   test01();
}
  1. 分析与总结
    （1）算法复杂度分析及优、缺点分析
    采用递归算法的时间复杂度为：O（n），递归算法的优点在于算法简单，易于理解并且容易写出，而非递归算法优点在于不需要让系统分配栈空间，而是自己分配栈空间，有利于对中间节点进行操作。对于某些情况不得不考虑用非递归算法。

（2）实验总结
在输入完第一个序列并输出其各个输出序列之后，输入另一个序列的时候，不知道为什么同一个函数，两次调用结果不一样，在经过很长时间的debug过程之后，终于找到错误原因，原来是在输入完一个输出序列之后，我输入了回车键，而回车键也被系统误认为是树的一部分，进而五大比较这两棵树。
在写代码的时候，要注意防止段错误的出现，这种情况很难发现，但是认真的找，就一定能找到。
要注意每次写代码的时候注意写完一个程序的时候注意运行，否则很可能会出现错误。

上一篇：Scala中的构造器和高阶函数


下一篇：数据结构—树