报告实验报告二叉树实验报告

二叉树实验报告

时间：2024.4.21

*******************

实践教学

*******************

 ***学院

计算机信息与科学学院

20##年春季学期

算法与数据结构课程设计

题    目：  二叉排序树的实现  

专业班级：    ********   

姓    名：    ********   

学    号：     **********  

指导教师：      ********      

成    绩：_______________

目  录

摘  要...................................................................................................................... 2

前  言...................................................................................................................... 2

正  文...................................................................................................................... 3

1.    问题描述...................................................................................................... 3

2.    任务与分析.................................................................................................. 3

3.    整体程序设计.............................................................................................. 3

4．  程序编码...................................................................................................... 4

5.    程序的测试和演示.................................................................................... 16

设计总结................................................................................................................ 17

参考文献................................................................................................................ 18

附录Ⅰ程序代码................................................................................................... 18

                              

摘   要

                                                                                                                                          

该设计要求学生设计程序，实现二叉排序树的相关操作。通过该题目的设计过程，可以加深理解二叉树、查找表的逻辑结构、存储结构，掌握二叉排序树上基本运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养学生的动手能力。

使用二叉链表存储二叉排序树，生成一棵二叉排序树，并掌握二叉树正确查找，插入，删除一个给定值的方法。

关键词：二叉排序树，二叉链表，查寻，删除，遍历，输出结果

前 言

问题的背景

二叉树是树型结构的一个重要类型，关于二叉树的存储结构及算法都较为简单，因此，二叉树在数据结构的研究领域中具有很重要的地位。

问题的意义

   掌握二叉树的概念，二叉树的性质，存储结构以及基本运算，并用二叉树解决一些综合应用问题。

正文

1. 问题描述

操作1 ：用顺序和二叉链表作存储结构设置一个字符作为输入结束标志,输入数列L，生成一棵二叉排序树T；对二叉排序树T作中序遍历，输出结果。

操作2：输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”；

2.任务与分析

1、查阅文献资料，一般在3篇以上；

2、建立数据的逻辑结构和物理结构；

3、完成相应算法的设计；

4、完成测试工作；

5、撰写设计说明书；

6、做好答辩工作。

任务是一个二叉排序树的实现问题，根据任一数列生成一棵二叉排序树；查询结点并删除结点且保证仍为二叉排序树。根据二叉排序树的概念，查找当前插入的元素的位置；删除结点如果不是叶子结点，要注意考虑如何使树仍为二叉排序树；当删除结点为根结点时，考虑如何保证二叉树照常输出。

3.整体程序设计方案

此课题是研究二叉排序树的实现，建立二叉树；查找一个数是否存在；插入一个给定的值；删除一个给定的值并输出结果。为了直观和方便，画出流程图如下图1：

                                       图--1

                                       

4.程序编码

4.1主程序

程序执行时需要的头文件及程序中运用到的结构体。

#include<malloc.h>

#include<stdio.h>

#include<string.h>

#include<iostream.h>

#include<windows.h>

#define maxsize 50

typedef struct node2

{

       char data;  //数据域

       struct node2 *lchild,*rchild,*parent;  //左指针域，右指针域

}btnode;//二叉链接点类型

typedef struct stack 

{

    btnode* data[maxsize];

    int top;

}seqstack; //建立一个栈 以便非递归使用

4.2 建立一个二叉排序树

以先序形式构建一个二叉树，使产生的结点有3个指针域，左、右孩子及父结点，以空格结束（结点为空）。

btnode *createbitree(btnode *&t)     //先序产生二叉树

{

        char ch;

        scanf("%c",&ch);

        if(ch==' ') t=NULL;

        else

        {

           t=(btnode*)malloc(sizeof(btnode));

           t->data=ch;t->parent=NULL;

           t->lchild=createbitree(t->lchild);

            if(t->lchild)

               t->lchild->parent=t;

            t->rchild=createbitree(t->rchild);

            if(t->rchild)

               t->rchild->parent=t;

        }

        return t;

}

4.3 在一个二叉排序树查找一个数是否存在

对输入的字符x进行查找，当x存在时返回该结点，否则返回空。

btnode *searchnode(btnode *b,char x)   //查找结点

{

       btnode *p;

       if(b==NULL)

          return NULL;      //空二叉树的查找失败出口

       else if(b->data==x)

          return b;         //查找成功出口

       else

       {

          p=searchnode(b->lchild,x);   //在左子树查找

          if(p!=NULL)

              return p;

          else

              return searchnode(b->rchild,x);   //在右子树查找

       }

}

4.5 删除结点

对结点进行删除，有以下5种情况：根结点、叶子结点、有右无左、有左无右、有左有右，当结点删除后不改变输出二叉树的顺序。

btnode* deltree(btnode *t,char x)

{

   

               btnode *q;

              if(t->lchild==NULL&&t->rchild==NULL)  //删除结点为叶子结点

               {             

                              if(t->parent==NULL)  //删除结点为根结点

                              {

                                 q=t;

                                 q=NULL;

                              }             

                              else if(t->parent->lchild->data==x)

                              {

                                             q=t->parent->lchild;

                                             t->parent->lchild=NULL;

                              }

                              else

                              {

                                             q=t->parent->rchild;

                                             t->parent->rchild=NULL;

                              }

                              free(t);

               }

               else if(t->lchild==NULL&&t->rchild!=NULL)  //删除结点无左孩子，将右孩子上提，代替该结点

               {

        if(t->parent==NULL)  //删除结点为根结点

                              {

                                 q=t->rchild;                         

                                 while(q->lchild!=NULL)  // 以先序方式遍历到最后一个左孩子

                                 {

                                               q=q->lchild;

                                 }

           q->parent->lchild=NULL;                   

                                 q->rchild=t->rchild;

                                 t->rchild->parent=q;

                                 q->parent=NULL;

                              }

                              else if (t->parent->lchild->data==x)

                              {

                             

                                             t->parent->lchild=t->rchild;

                                             t->rchild->parent=t->parent;

                              }

                              else

                              {

            t->parent->rchild=t->rchild;

                                             t->rchild->parent=t->parent;

                                             }

                              free(t);

               }

               else if(t->lchild!=NULL&&t->rchild==NULL)  //删除结点无右孩子，将左孩子上提，代替该结点

               {

                              if(t->parent==NULL)  //删除结点为根结点

                              {

                                 q=t->lchild;

                                 q->parent=NULL;

                              }

                              else if(t->parent->lchild->data==x)

                              {

                             

                                             t->parent->lchild=t->lchild;

                                             t->lchild->parent=t->parent;

                              }

                              else

                              {

                       t->parent->rchild=t->lchild;

                                             t->lchild->parent=t->parent;

                              }

                              free(t);

               }

               else    //删除结点既有 左孩子又有右孩子

               {             

                              if(t->parent==NULL)  //删除结点为根结点

                              {

                                 q=t->rchild;                         

                                 while(q->lchild!=NULL)  // 以先序方式遍历到最后一个左孩子

                                 {

                                               q=q->lchild;

                                 }

           q->parent->lchild=NULL;                   

                                 q->lchild=t->lchild;

                                 q->rchild=t->rchild;

                                 t->rchild->parent=q;

                                 t->lchild->parent=q;

                                 q->parent=NULL;

                              }

                              else if(t->parent->lchild->data==x||t->parent->rchild->data==x)//  直接指向 删除结点的右孩子

                              {

                                             q=t->rchild;

                                             while(q->lchild!=NULL)  // 以先序方式遍历到最后一个左孩子

                                             {

                                                q=q->lchild;

                                             }

                                  q->parent->lchild=NULL;  //当将q结点提出时，则应该其原来的储存位置置空

                                  //  用q代替要删除结点，  保证以中序输出的结点顺序不变

                                 if(t->parent->lchild->data==x)

                                 {

                                               q->lchild=t->lchild;

                                               q->rchild=t->rchild;

                                               t->lchild->parent=q;

                                    t->rchild->parent=q;

                                               t->parent->lchild=q;

                                               q->parent=t->parent;   

                                 }

                                 else

                                 {

                                               q->lchild=t->lchild;

                                               q->rchild=t->rchild;

                                               t->lchild->parent=q;

                                               t->rchild->parent=q;

                                               t->parent->rchild=q;

                                               q->parent=t->parent;

                                 }        

                              }

                             

                              free(t);      

               }

               return q;

}4.5 进行遍历

void preorder(btnode *bt)   //递归 先序 遍历

{

       if(bt!=NULL)

       {

          printf("%c",bt->data);

          preorder(bt->lchild);

          preorder(bt->rchild);

       }

}

void preorder2(btnode* bt)  //非递归 先序遍历

{

       btnode* p;

       seqstack ps;

       ps.top=-1;

       if(bt==NULL)

       {

          return;

       }

       else

       {

          ps.top++;

          ps.data[ps.top]=bt;

          while(ps.top!=-1)

          {

              p=ps.data[ps.top];

              ps.top--;

              printf("%c",p->data);

              if(p->rchild!=NULL)

              {

                  ps.top++;

                  ps.data[ps.top]=p->rchild;

              }

              if(p->lchild!=NULL)

              {

                  ps.top++;

                  ps.data[ps.top]=p->lchild;

              }

          }

       }

}

void inorder(btnode *p)   // 递归中序遍历

{

       if(p!=NULL)

       {

         inorder(p->lchild);

         printf("%c",p->data);

      inorder(p->rchild);

       }

}

void inorder2(btnode *bt)  //非递归中序遍历

{

       btnode *p,*q;

       seqstack ps;

       ps.top=-1;

       if(bt==NULL)

       {

          return;

       }

       else

       {

          while(bt!=NULL)

          {

              ps.top++;

              ps.data[ps.top]=bt;

              bt=bt->lchild;

          }

          while(ps.top!=-1)

          {

              p=ps.data[ps.top];

              ps.top--;

              printf("%c",p->data);

             

              while(p->rchild!=NULL)

              {

                  ps.top++;

                  ps.data[ps.top]=p->rchild;

                  q=p->rchild;

                  while(q->lchild!=NULL)

                  {

                      ps.top++;

                      ps.data[ps.top]=q->lchild;

                      q=q->lchild;

                  }

                  break;

              }

        }

       }

}

void postorder(btnode *bt)   //递归后序遍历

{

       if(bt!=NULL)

       {

          postorder(bt->lchild);

          postorder(bt->rchild);

          printf("%c",bt->data);

       }

}

void postorder2(btnode* bt)  //非递归后序遍历

{

       seqstack ps;

    ps.top=-1;

    btnode* t;

    int flag;

    do

       {

          while (bt!=NULL)

          {

              ps.top++;

              ps.data[ps.top]=bt;

              bt=bt->lchild;

          }

          t=NULL;

          flag=1;

          while (ps.top!=-1 && flag)

          {

              bt=ps.data[ps.top];

              if(bt->rchild==t) //t：表示为null，或者右子节点被访问过了。

              {

                  printf("%c ",bt->data);

                  ps.top--;

                  t=bt; //t记录下刚刚访问的节点

              }

              else

              {

                  bt=bt->rchild;

                  flag=0;

              }

          }

       }

       while (ps.top!=-1);

}

4.6 创建菜单

void output1() 

{

       int i;

       for(i=0;i<23;i++)

          printf(" ");

       for(i=0;i<32;i++)

          printf("*");

       printf("\n");

}

void mainpp()

{

       int i;

       output1();

       for(i=0;i<23;i++)

          printf(" ");

       printf("*    ");

    printf("1.先 序 建 立 二 叉 树");

       for(i=0;i<4;i++)

          printf(" ");

       printf("*");

       printf("\n");

       for(i=0;i<23;i++)

          printf(" ");

       printf("*    ");

    printf("2.非递归先序遍历二叉树");

       for(i=0;i<4;i++)

          printf(" ");

       printf("*");

       printf("\n");

       for(i=0;i<23;i++)

          printf(" ");

       printf("*    ");

    printf("3.非递归中序遍历二叉树");

       for(i=0;i<4;i++)

          printf(" ");

       printf("*");

       printf("\n");

       for(i=0;i<23;i++)

          printf(" ");

       printf("*    ");

    printf("4.非递归后序遍历二叉树");

       for(i=0;i<4;i++)

          printf(" ");

       printf("*");

       printf("\n");

       for(i=0;i<23;i++)

          printf(" ");

       printf("*    ");

       printf("5.递归先序 遍历 二叉树");

       for(i=0;i<4;i++)

          printf(" ");

       printf("*");

       printf("\n");

       for(i=0;i<23;i++)

          printf(" ");

       printf("*    ");

       printf("6.递归中序 遍历 二叉树");

       for(i=0;i<4;i++)

          printf(" ");

       printf("*");

       printf("\n");

       for(i=0;i<23;i++)

          printf(" ");

       printf("*    ");

       printf("7.递归后序 遍历 二叉树");

       for(i=0;i<4;i++)

          printf(" ");

       printf("*");

       printf("\n");

       for(i=0;i<23;i++)

          printf(" ");

       printf("*    ");

       printf("8.查 找 并 删 除 结 点");

       for(i=0;i<4;i++)

          printf(" ");

       printf("*");

       printf("\n");

      

       for(i=0;i<23;i++)

          printf(" ");

       printf("*    ");

       printf("9.输出删除结点的二叉树");

       for(i=0;i<4;i++)

          printf(" ");

       printf("*");

       printf("\n");

      

       for(i=0;i<23;i++)

          printf(" ");

       printf("*    ");

       printf("10.以嵌套形式输出二叉树");

       for(i=0;i<3;i++)

          printf(" ");

       printf("*");

       printf("\n");

       for(i=0;i<23;i++)

          printf(" ");

       printf("*    ");

       printf("0.退               出");

       for(i=0;i<5;i++)

          printf(" ");

       printf("*");

       printf("\n");

       output1();

}

4.7主函数

void main()

{

   system("color 0B");

   mainpp();

   btnode *root,*t;

   char x;

   int w,k=1;                        

   while(k)

   {

          printf("请选择0--9：");

          scanf("%d",&w);

          getchar();

       switch(w)

          {

          case 0:  return;

          case 1:  {

                          printf("先 序 建 立 二 叉 树:  ");

                         createbitree(root);

                         getchar();

                         break;

                     }

          case 2:  {

                          printf("非递归先序遍历二叉树:   ");

                         preorder2(root);

                         break;

                     }

          case 3:  {

                          printf("非递归中序遍历二叉树:   ");

                         inorder2(root);

                         break;

                     }

          case 4:  {

                          printf("非递归后序遍历二叉树:   ");

                         postorder(root);

                         break;

                     }

          case 5:  {

                          printf("递归先序遍历二叉树:   ");

                         preorder(root);

                         break;

                     }

          case 6:  {

                          printf("递归中序遍历二叉树:   ");

                         inorder(root);

                         break;

                     }

          case 7:  {

                          printf("递归后序遍历二叉树:   ");

                         postorder(root);

                         break;

                     }

          case 8:  {

                          printf("输入字符x：");

                         scanf("%c",&x);

                         getchar();                   

                         t=searchnode(root,x);

                        

                         if(t)

                         {

                             if(t==root)

                             {

                                 root=deltree(t,x);   

                             }

                             else

                                 deltree(t,x);

                          printf("删除结点成功!\n");

                         }

                         else

                            printf("无x!\n");

                         break;

                     }

            case 9:  {

                        

                         printf("中序输出删除后二叉树的各结点:\n");                    

                         inorder(root);                  

                         break;

                     }

            case 10:{

                         printf("嵌套形式输出二叉树：");

                         dispbitree(root);

                    }

         default:  return;

          }  

       printf("\n继续运行吗y(1)/n(0):   ");

       scanf("%d",&k);

          getchar();   

       if(!k)

          return;

   }

}

5．程序测试与演示：

   测试数据：a + b * c - d -e/f。

测试结果下如图：       

                 设  计  总  结

通过这次课程设计的程序实践，我实在获益匪浅！数据结构是这个学期开展的一门学科，学习好这门学科是非常重要的，在以后的程序设计方面这门学科能给我们很大的帮助。同时，学习这门学科也是艰辛的，因为它比较难懂，这不仅需要我们要发挥我们的聪明才志，还需要我们在不断的实践中领悟。

这次的程序设计对我来说无疑是一个具大的考验，从接起课题后，我就一直为实现程序而努力，翻阅相关书籍、在网上查找资料。因为开始时基础不是很好，过程中遇到了不少的阻碍，编写程序的进度也比较慢。但是通过努力，我对这次实验的原理有了一定的理解，通过参照从网上找到的源程序，终于在其它源程序的基础下写出了本次课程设计的核心算法，并使其能够正常的运行。

这次的设计工作，让我体会到了作为一个编程人员的艰难，一个算法到具体实现，再到应用层面的开发是需要有一段较长的路要走的，不是一朝一夕就可以实现的，而且在编好程序后，编程人员还要花很多的时间去完善它，其中的辛苦，很难用言语表达出来。

今后，我会更加努力的学习专业知识，努力提高自我的能力。

参考文献

1.          谭浩强.《c语言程序设计》. 清华大学出版社.

2.   陈建新、李志敏。《数据结构》（实验指导与课程设计教程）

附录Ⅰ 程序代码

#include<malloc.h>

#include<stdio.h>

#include<string.h>

#include<iostream.h>

#include<windows.h>

#define maxsize 50

typedef struct node2

{

      char data;  //数据域

      struct node2 *lchild,*rchild,*parent;  //左指针域，右指针域

}btnode;//二叉链接点类型

typedef struct stack  //建立一个栈

{

    btnode* data[maxsize];

    int top;

}seqstack;

btnode *createbitree(btnode *&t)     //先序产生二叉树

{

       char ch;

       scanf("%c",&ch);

       if(ch==' ')

          t=NULL;

       else

       {

          t=(btnode*)malloc(sizeof(btnode));

          t->data=ch;

          t->parent=NULL;

          t->lchild=createbitree(t->lchild);

         if(t->lchild)

              t->lchild->parent=t;

          t->rchild=createbitree(t->rchild);

          if(t->rchild)

              t->rchild->parent=t;

       }

       return t;

}

btnode *searchnode(btnode *b,char x)   //查找结点

{

      btnode *p;   

      if(b==NULL)

         return NULL;      //空二叉树的查找失败出口

      else if(b->data==x)

         return b;         //查找成功出口

      else

      {

         p=searchnode(b->lchild,x);   //在左子树查找

         if(p!=NULL)

             return p;

         else

             return searchnode(b->rchild,x);   //在右子树查找

      }

}

btnode* deltree(btnode *t,char x)

{

   

      btnode *q;

      if(t->lchild==NULL&&t->rchild==NULL)  //删除结点为叶子结点

      { 

         if(t->parent==NULL)  //删除结点为根结点

         {

            printf("删除结点为根结点\n");

            q=t;

            q=NULL;

         }  

         else if(t->parent->lchild->data==x)

         {

             printf("删除结点为叶子结点\n");

             q=t->parent->lchild;

             t->parent->lchild=NULL;

         }

         else

         {

             printf("删除结点为叶子结点\n");

             q=t->parent->rchild;

             t->parent->rchild=NULL;

         }

         free(t);

      }

      else if(t->lchild==NULL&&t->rchild!=NULL)  //删除结点无左孩子，将右孩子上提，代替该结点

      {

        if(t->parent==NULL)  //删除结点为根结点

         {

            printf("删除结点为根结点\n");

            q=t->rchild;         

            while(q->lchild!=NULL)  // 以先序方式遍历到最后一个左孩子

            {

               q=q->lchild;

            }

           q->parent->lchild=NULL;         

            q->rchild=t->rchild;

            t->rchild->parent=q;

            q->parent=NULL;

         }

         else if (t->parent->lchild->data==x)

         {

             printf("删除结点叶结点\n");

             t->parent->lchild=t->rchild;

             t->rchild->parent=t->parent;

         }

         else

         {

             printf("删除结点叶结点\n");

            t->parent->rchild=t->rchild;

             t->rchild->parent=t->parent;

             }

         free(t);

      }

      else if(t->lchild!=NULL&&t->rchild==NULL)  //删除结点无右孩子，将左孩子上提，代替该结点

      {

         if(t->parent==NULL)  //删除结点为根结点

         {

            printf("删除结点根结点\n");

            q=t->lchild;

            q->parent=NULL;

         }

         else if(t->parent->lchild->data==x)

         {

             printf("删除结点叶结点\n");

             t->parent->lchild=t->lchild;

             t->lchild->parent=t->parent;

         }

         else

         {

            printf("删除结点叶结点\n");

              t->parent->rchild=t->lchild;

             t->lchild->parent=t->parent;

         }

         free(t);

      }

      else    //删除结点既有 左孩子又有右孩子

      { 

         if(t->parent==NULL)  //删除结点为根结点

         { 

            printf("删除结点叶结点\n");

            q=t->rchild;         

            while(q->lchild!=NULL)  // 以先序方式遍历到最后一个左孩子

            {

               q=q->lchild;

            }

           q->parent->lchild=NULL;         

            q->lchild=t->lchild;

            q->rchild=t->rchild;

            t->rchild->parent=q;

            t->lchild->parent=q;

            q->parent=NULL;

         }

         else if(t->parent->lchild->data==x||t->parent->rchild->data==x)//  直接指向 删除结点的右孩子

         { 

             printf("删除结点叶结点\n");

             q=t->rchild;

             while(q->lchild!=NULL)  // 以先序方式遍历到最后一个左孩子

             {

                q=q->lchild;

             }

             q->parent->lchild=NULL;  //当将q结点提出时，则应该其原来的储存位置置空

                        //  用q代替要删除结点，  保证以中序输出的结点顺序不变

            if(t->parent->lchild->data==x)

            {

               q->lchild=t->lchild;

               q->rchild=t->rchild;

               t->lchild->parent=q;

               t->rchild->parent=q;

               t->parent->lchild=q;

               q->parent=t->parent;   

            }

            else

            {

               q->lchild=t->lchild;

               q->rchild=t->rchild;

               t->lchild->parent=q;

               t->rchild->parent=q;

               t->parent->rchild=q;

               q->parent=t->parent;

            }  

         }

        

         free(t);      

      }

      return q;

}

void preorder(btnode *bt)   //递归 先序 遍历

{

      if(bt!=NULL)

      {

         printf("%c",bt->data);

         preorder(bt->lchild);

         preorder(bt->rchild);

      }

}

void preorder2(btnode* bt)  //非递归 先序遍历

{

      btnode* p;

      seqstack ps;

      ps.top=-1;

      if(bt==NULL)

      {

         return;

      }

      else

      {

         ps.top++;

         ps.data[ps.top]=bt;

         while(ps.top!=-1)

         {

             p=ps.data[ps.top];

             ps.top--;

             printf("%c",p->data);

             if(p->rchild!=NULL)

             {

                 ps.top++;

                 ps.data[ps.top]=p->rchild;

             }

             if(p->lchild!=NULL)

             {

                 ps.top++;

                 ps.data[ps.top]=p->lchild;

             }

         }

      }

}

void inorder(btnode *p)   // 递归中序遍历

{

      if(p!=NULL)

      {

        inorder(p->lchild);

        printf("%c",p->data);

      inorder(p->rchild);

      }

}

void inorder2(btnode *bt)  //非递归中序遍历

{

      btnode *p,*q;

      seqstack ps;

      ps.top=-1;

      if(bt==NULL)

      {

         return;

      }

      else

      {

         while(bt!=NULL)

         {

             ps.top++;

             ps.data[ps.top]=bt;

             bt=bt->lchild;

         }

         while(ps.top!=-1)

         {

             p=ps.data[ps.top];

             ps.top--;

             printf("%c",p->data);

            

             while(p->rchild!=NULL)

             {

                 ps.top++;

                 ps.data[ps.top]=p->rchild;

                 q=p->rchild;

                 while(q->lchild!=NULL)

                 {

                     ps.top++;

                     ps.data[ps.top]=q->lchild;

                     q=q->lchild;

                 }

                 break;

             }

        }

      }

}

void postorder(btnode *bt)   //递归后序遍历

{

      if(bt!=NULL)

      {

         postorder(bt->lchild);

         postorder(bt->rchild);

         printf("%c",bt->data);

      }

}

void postorder2(btnode* bt)  //非递归后序遍历

{

      seqstack ps;

    ps.top=-1;

    btnode* t;

    int flag;

    do

      {

         while (bt!=NULL)

         {

             ps.top++;

             ps.data[ps.top]=bt;

             bt=bt->lchild;

         }

         t=NULL;

         flag=1;

         while (ps.top!=-1 && flag)

         {

             bt=ps.data[ps.top];

             if(bt->rchild==t) //t：表示为null，或者右子节点被访问过了。

             {

                 printf("%c ",bt->data);

                 ps.top--;

                 t=bt; //t记录下刚刚访问的节点

             }

             else

             {

                 bt=bt->rchild;

                 flag=0;

             }

         }

      }

      while (ps.top!=-1);

}

void dispbitree(btnode *b)      //嵌套 输出二叉树

{

      if(b!=NULL)

      {

        printf("%c",b->data);

         if(b->lchild!=NULL||b->rchild!=NULL)

         {

             printf("(");

             dispbitree(b->lchild);    //递归处理左子树

             if(b->rchild!=NULL)

             {

                 printf(",");

                 dispbitree(b->rchild);      //递归处理右子树

             }

             printf(")");

         }

      }

}

void output1()

{

      int i;

      for(i=0;i<23;i++)

         printf(" ");

      for(i=0;i<32;i++)

         printf("*");

      printf("\n");

}

void mainpp()

{

      int i;

      output1();

      for(i=0;i<23;i++)

         printf(" ");

      printf("*    ");

    printf("1.先 序 建 立 二 叉 树");

      for(i=0;i<4;i++)

         printf(" ");

      printf("*");

      printf("\n");

      for(i=0;i<23;i++)

         printf(" ");

      printf("*    ");

    printf("2.非递归先序遍历二叉树");

      for(i=0;i<4;i++)

         printf(" ");

      printf("*");

      printf("\n");

      for(i=0;i<23;i++)

         printf(" ");

      printf("*    ");

    printf("3.非递归中序遍历二叉树");

      for(i=0;i<4;i++)

         printf(" ");

      printf("*");

      printf("\n");

      for(i=0;i<23;i++)

         printf(" ");

      printf("*    ");

    printf("4.非递归后序遍历二叉树");

      for(i=0;i<4;i++)

         printf(" ");

      printf("*");

      printf("\n");

      for(i=0;i<23;i++)

         printf(" ");

      printf("*    ");

      printf("5.递归先序 遍历 二叉树");

      for(i=0;i<4;i++)

         printf(" ");

      printf("*");

      printf("\n");

      for(i=0;i<23;i++)

         printf(" ");

      printf("*    ");

      printf("6.递归中序 遍历 二叉树");

      for(i=0;i<4;i++)

         printf(" ");

      printf("*");

      printf("\n");

      for(i=0;i<23;i++)

         printf(" ");

      printf("*    ");

      printf("7.递归后序 遍历 二叉树");

      for(i=0;i<4;i++)

         printf(" ");

      printf("*");

      printf("\n");

      for(i=0;i<23;i++)

         printf(" ");

      printf("*    ");

      printf("8.查 找 并 删 除 结 点");

      for(i=0;i<4;i++)

         printf(" ");

      printf("*");

      printf("\n");

     

      for(i=0;i<23;i++)

         printf(" ");

      printf("*    ");

      printf("9.输出删除结点的二叉树");

      for(i=0;i<4;i++)

         printf(" ");

      printf("*");

      printf("\n");

     

      for(i=0;i<23;i++)

         printf(" ");

      printf("*    ");

      printf("10.以嵌套形式输出二叉树");

      for(i=0;i<3;i++)

         printf(" ");

      printf("*");

      printf("\n");

      for(i=0;i<23;i++)

         printf(" ");

      printf("*    ");

      printf("0.退               出");

      for(i=0;i<5;i++)

         printf(" ");

      printf("*");

      printf("\n");

      output1();

}

void main()

{

   system("color 0B");

   mainpp();

   btnode *root,*t;

   char x;

   int w,k=1;                       

   while(k)

   {

         printf("请选择0--9：");

         scanf("%d",&w);

         getchar();

       switch(w)

         {

          case 0:  return;

          case 1:  {

                         printf("先 序 建 立 二 叉 树:  ");

                        createbitree(root);

                        getchar();

                        break;

                    }

          case 2:  {

                         printf("非递归先序遍历二叉树:   ");

                        preorder2(root);

                        break;

                    }

          case 3:  {

                         printf("非递归中序遍历二叉树:   ");

                        inorder2(root);

                        break;

                    }

          case 4:  {

                         printf("非递归后序遍历二叉树:   ");

                        postorder(root);

                        break;

                    }

          case 5:  {

                         printf("递归先序遍历二叉树:   ");

                        preorder(root);

                        break;

                    }

          case 6:  {

                         printf("递归中序遍历二叉树:   ");

                        inorder(root);

                        break;

                    }

          case 7:  {

                         printf("递归后序遍历二叉树:   ");

                        postorder(root);

                        break;

                    }

          case 8:  {

                         printf("输入字符x：");

                        scanf("%c",&x);

                        getchar();                   

                        t=searchnode(root,x);

                       

                        if(t)

                        {

                            if(t==root)

                            {

                                root=deltree(t,x);   

                            }

                            else

                                deltree(t,x);

                          printf("删除结点成功!\n");

                        }

                        else

                           printf("无x!\n");

                        break;

                    }

           case 9:  {

                       

                        printf("中序输出删除后二叉树的各结点:\n");                    

                        inorder(root);                  

                        break;

                    }

           case 10:{

                        printf("嵌套形式输出二叉树：");

                        dispbitree(root);

                   }

         default:  return;

         }  

       printf("\n继续运行吗y(1)/n(0):   ");

       scanf("%d",&k);

         getchar();   

       if(!k)

         return;

   }

}    

更多相关推荐：
实验六 二叉树实验报告(1)

实验四二叉树的操作班级：计算机1002班姓名：**学号：**完成日期：20XX.6.14题目：对于给定的一二叉树，实现各种约定的遍历。一、实验目的：（1）掌握二叉树的定义和存储表示，学会建立一棵特定二叉树的方法…

二叉树实验报告

实验六树和二叉树的操作一实验目的1进一步掌握树的结构及非线性特点递归特点和动态性2进一步巩固对指针的使用和二叉树的三种遍历方法建立方法二实验内容二叉树的实现和运算三实验要求1用CC完成算法设计和程序设计并上机调...

树和二叉树实验报告

树和二叉树一实验目的1掌握二叉树的结构特征以及各种存储结构的特点及适用范围2掌握用指针类型描述访问和处理二叉树的运算二实验要求1认真阅读和掌握本实验的程序2上机运行本程序3保存和打印出程序的运行结果并结合程序进...

二叉树基本操作--实验报告

宁波工程学院电信学院计算机教研室实验报告一实验目的1熟悉二叉树树的基本操作2掌握二叉树的实现以及实际应用3加深二叉树的理解逐步培养解决实际问题的编程能力二实验环境1台WINDOWS环境的PC机装有VisualC...

二叉树实验报告

二叉树实验报告问题描述1问题描述用先序递归过程建立二叉树存储结构二叉链表输入数据按先序遍历所得序列输入当某结点左子树或右子树为空时输入号如输入abcde得到的二叉树为编写递归算法计算二叉树中叶子结点的数目按凹入...

二叉树实验报告

数据结构课程设计报告专业计算机科学与技术班级3班姓名学号指导教师起止时间20xx1220xx1课程设计二叉树一任务描述二叉树的中序前序后序的递归非递归遍历算法应包含建树的实现任务设计一个程序实现二叉树的前序中序...

二叉树的遍历实验报告

二叉树的遍历实验报告一需求分析在二叉树的应用中常常要求在树中查找具有某种特征的结点或者对树中全部结点逐一进行某种处理这就是二叉树的遍历问题对二叉树的数据结构进行定义建立一棵二叉树然后进行各种实验操作二叉树是一个...

二叉树的遍历及其应用实验报告

实验报告题目二叉树的遍历及应用院系数学系专业数学与应用数学学号20xx114036姓名郭奇瑞一实验名称二叉树的遍历及应用二实验日期20xx年11月14日三实验要求编程实现二叉树的建立并对其进行遍历四实验目的1掌...

二叉树基本操作--实验报告

实验三二叉树的基本操作学院物理与电子学院班级电信1105班姓名刘岩学号1404110729一实验目的1熟悉二叉树的基本操作掌握二叉树的实现以及实际应用3加深对于二叉树的理解逐步培养解决实际问题的编程能力二实验环...

实验报告(二叉树)

仲恺农业工程学院实验报告纸信息科学与技术院系计算机专业144班数据结构与算法课一实验目的1掌握二叉树的特点以及的二叉链表存储结构2熟练掌握二叉树的各种操作如建立遍历查找和输出3利用已经掌握的知识进行实际应用二实...

数据结构树和二叉树实验报告

数据结构课程实验报告注空间不够可以增加页码

数据结构-二叉树实验报告

数据结构实验报告课程数据结构实验名称二叉树实验院系电信学院专业班级计科104姓名学号一实验构思首先构造二叉树的存储结构用data存储当前节点的值分别用lchildrchild表示该节点的左右孩子然后应用BiTr...

二叉树实验报告（43篇）

热门关注

数据结构C二叉树实验报告

二叉树实验报告

树和二叉树的实验报告

二叉树实验报告

二叉树的建立和遍历实验报告

实验12 二叉树遍历实验报告

12信管实验报告(树与二叉树的基本操作_1)

二叉树实验报告

猜你喜欢

能源评估管理办法

水电施工总结

XXX职业健康检查报告书

高中化学课本实验总结

视频会议保障总结（6篇）

安全活动月工作总结（57篇）