程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> 關於C >> 二叉樹的創建、打印、刪除等函數(c)

二叉樹的創建、打印、刪除等函數(c)

編輯:關於C

我認為要看懂下面的代碼,對於遞歸的運行,要很了解才是!

[html]
#include <stdio.h> 
#include <stdlib.h> 
 
struct TreeNode; 
typedef struct TreeNode *Position; 
typedef struct TreeNode *SearchTree; 
 
/* Placein the implement file */ 
struct TreeNode 

    int Element; 
    SearchTree Left; 
    SearchTree Right; 
}; 
 
/*  clean up tree */ 
SearchTree MakeEmpty(SearchTree T) 

    if (T != NULL) 
    { 
        MakeEmpty(T->Left); 
        MakeEmpty(T->Right); 
        free(T); 
        T = NULL; 
    } 
     
    return NULL; 

 
/* find x in the tree */ 
Position Find(int X, SearchTree T) 

    if (T != NULL) 
    { 
        if (T->Element == X) 
        { 
            return T; 
        } 
        else if(T->Element < X) 
        { 
             return Find(X, T->Right); 
        } 
        else if (T->Element > X) 
        { 
            return Find(X, T->Left); 
        } 
    } 
    else 
    { 
        return NULL; 
    } 

 
/* find min */ 
Position FindMin(SearchTree T) 

    if (T == NULL) 
    { 
        return NULL; 
    } 
    else 
    { 
        if (T->Left != NULL) 
        { 
            FindMin(T->Left); 
        } 
        else 
        { 
            printf("MIN = %d\n", T->Element); 
            return T; 
        } 
    } 
         

/* find max */ 
Position FindMax(SearchTree T) 

    if (T == NULL) 
    { 
        return NULL; 
    } 
    else 
    { 
        if (T->Right!= NULL) 
        { 
            FindMax(T->Right); 
        } 
        else 
        { 
            printf("MAX = %d\n", T->Element); 
            return T; 
        } 
    } 
     

 
/* insert x */ 
SearchTree Insert(int X, SearchTree T) 

    if (T == NULL) 
    { 
        T = (SearchTree)malloc(sizeof(struct TreeNode)); 
        if (T == NULL) 
        { 
            printf("out of space!!!\n"); 
        } 
        else 
        { 
            T->Element = X; 
            T->Left = NULL; 
            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; 

 
/* delete x */ 
SearchTree DeleteTree(int X, SearchTree T) 

    Position TmpCell; 
 
    if (T == NULL) 
    { 
        printf("X not found.\n"); 
    } 
    else 
    { 
        if (X < T->Element)  /* go to left */ 
        { 
            T->Left = DeleteTree(X, T->Left); 
        } 
        else if (X > T->Element) 
        { 
            T->Right = DeleteTree(X, T->Right); 
        }        
        else 
        { 
            if (T->Left && T->Right)   /* Two children */ 
    { 
                /* replace  with smallest in right subtree */ 
                TmpCell = FindMin(T->Right); 
                T->Element = TmpCell->Element; 
                T->Right = DeleteTree(T->Element, T->Right); 
            } 
            else 
            { 
                TmpCell = T; 
                if (T->Left == NULL) 
                    T = T->Right; 
                else if (T->Left == NULL) 
                    T = T->Left; 
                free(TmpCell); 
            } 
        } 
    } 
    return T; 

 
// 中序遍歷。打印。 
void ShowTree(SearchTree T) 

    if (T != NULL) 
    { 
        ShowTree(T->Left); 
        printf("   %d  ", T->Element); 
        ShowTree(T->Right); 
    } 
 

 
int main(void) 

    Position tree = NULL; 
    tree = Insert(6, tree); 
    tree = Insert(2, tree); 
    tree = Insert(8, tree); 
    tree = Insert(1, tree); 
    tree = Insert(5, tree); 
    tree = Insert(4, tree); 
    tree = Insert(3, tree); 
    DeleteTree(3, tree); 
    //DeleteTree(3, tree); 
    //DeleteTree(6, tree); 
    ShowTree(tree); 
    printf("\n"); 
    FindMax(tree); 
    FindMin(tree); 
    return 0; 
     
     


摘自 angelbosj的專欄
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved