系统学习图像算法Day.13——数据结构学习——“二叉树”的代码实现

朱雀 2023-10-09 09:45 45阅读 0赞

//本程序测试的是二叉搜索树
    #include <stdio.h>
    #include <stdlib.h>
    #ifndef _Tree_H
    struct TreeNode;
    typedef int ElementType;
    typedef struct TreeNode *Position;
    typedef struct TreeNode *SearchTree;
    #endif
    
    struct TreeNode
    { 
          ElementType Element;
          SearchTree Left;
          SearchTree Right;
    };
    
    SearchTree initial()
    { 
      SearchTree T;
      T = (SearchTree)malloc(sizeof(SearchTree));
      T->Element = 0;
      T->Left = NULL;
      T->Right = NULL;
      return T;
    };
    
    void TreeFirstInput(SearchTree T)
    { 
     printf("现在初始化的树根值为：%d",T->Element);
     printf("\n输入树根值：");
     scanf_s("%d",&T->Element);
     printf("\n现在树根值为 %d",T->Element );
    }
    
    SearchTree Insert(ElementType X,SearchTree T)
    { 
         if( T == NULL)
            { 
                T = (SearchTree)malloc(sizeof(SearchTree));
                if( T == NULL )
                printf("Out of sapce");
                else
                     { 
                      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;
    }
    
    SearchTree MakeEmpty( SearchTree T)
    { 
     if( T != NULL)
         { 
            MakeEmpty(T->Left);
            MakeEmpty(T->Right);
            free(T);
         }
     return NULL;
    }
    
    SearchTree AllInsert(ElementType X1,ElementType X2,ElementType X3,ElementType X4,ElementType X5,ElementType X6,SearchTree A)
    { 
     A = Insert(X1,A);
     A = Insert(X2,A);
     A = Insert(X3,A);
     A = Insert(X4,A);
     A = Insert(X5,A);
     A = Insert(X6,A);
     return A;
    }
    
    Position Find( ElementType X, SearchTree T )
    { 
      if(T == NULL)
        { 
            printf("没找着");
            return NULL;
         }
         
      if(X < T->Element)
      return Find( X, T->Left );
      
      else if(X > T->Element)
      return Find(X, T->Right);
    
      else
      return T;
    }
    
    Position FindMin(SearchTree T)
    { 
      if (T == NULL)
      return NULL;
      else if( T->Left == NULL )
               return T;
           else
               return FindMin(T->Left);
    }
    
    SearchTree Delete( ElementType X, SearchTree T )
    { 
         Position Tmp;
         Tmp = (SearchTree)malloc(sizeof(SearchTree));
         
         if(T == NULL)
         printf("Not Found");
       
         else
             {  
               if(X < T->Element)
                     T->Left = Delete ( X, T->Left );
               else
                  if(X > T->Element)  
                     T->Right = Delete ( X, T->Right );
                  else
                      { 
                        if( T->Left && T->Right )
                             { 
                               Tmp = FindMin(T->Right);
                               T->Element = Tmp->Element;
                               T->Right = Delete(Tmp->Element, T->Right);
                              }
                        else
         { 
             if(T->Left = NULL)
                  T = T->Right;
             else if(T->Right = NULL)
                  T = T->Left;
                  //有个大疑问，这里如果加个free(Tmp);就报错，搞不懂！！！！
          }
       }
     }
     return T;
    }
    
    int main()
    { 
     int X1,X2,X3,X4,X5,X6,X,XDel;
     SearchTree A, FindX ;
                    A =initial();
     FindX =initial();
     TreeFirstInput(A);
     printf("\n输入要插入的值");
     scanf_s("%d %d %d %d %d %d",&X1,&X2,&X3,&X4,&X5,&X6);
        A = AllInsert( X1,X2,X3,X4,X5,X6,A );
     /*printf("最左的树叶的值是：%d",A->Left->Left->Element);*/
     printf("输入你要查找的值");
     scanf("%d",&X);
     FindX = Find(X,A);
     printf("查找到了 %d",FindX->Element);
     printf("\n开始删除前的验证操作,请输入你要删除的元素值：");
     scanf("%d",&XDel);
     FindX = Find(XDel,A);
     printf("\n目前查找到了 %d",FindX->Element);
     A = Delete(XDel,A);
     printf("删完了");
     if(A != NULL)
      printf("%d",A->Element);
     if(A->Left != NULL)
         printf("%d",A->Left->Element);
     if(A->Left->Left != NULL)
      printf("%d",A->Left->Left->Element);
      getchar();
     getchar();
     return 0;
    
    }