BiTree – Implement in C
本文最后更新于 875 天前,其中的信息可能已经有所发展或是发生改变。 / This article was last updated 875 days ago and the information in it may have evolved or changed.

Basis

LevelOrderTraverse is implemented based on Queue.

typedef BiTNode* QElemtype; 
typedef struct QNode{
    QElemtype data;
    struct QNode* next;
}QNode;
typedef struct{
    QNode* front;
    QNode* rear;
}LinkQueue;

// Queue Function Declaration
Status InitQueue(LinkQueue& Q);
Status DestroyQueue(LinkQueue& Q);
bool QueueEmpty(LinkQueue Q);
Status ClearQueue(LinkQueue& Q);
Status EnQueue(LinkQueue& Q, QElemtype e);
Status DeQueue(LinkQueue& Q, QElemtype& e);

Status InitQueue(LinkQueue& Q){
   /* 
    * ===  FUNCTION  ======================================================================
    *         Name:  InitQueue
    *  Description:  Initialize a Queue. Will allocate memory for pointers.
    * =====================================================================================
    */
    Q.front = (QNode*)malloc(sizeof(QNode));
    if(!Q.front)    return FAILURE;
    Q.front->next = NULL;
    Q.rear = Q.front;
    return SUCCESS;
}    

Status DestroyQueue(LinkQueue& Q){
    /* 
     * ===  FUNCTION  ======================================================================
     *         Name:  DestroyQueue
     *  Description:  Destroy a Queue. Free all the pointers.
     * =====================================================================================
     */
    if(!ClearQueue(Q))  return FAILURE;
    free(Q.rear);   Q.rear = NULL;  //Q.rear and Q.front must point to the 
    Q.front = NULL;                 // same address, free once.        
    return SUCCESS;
}

Status ClearQueue(LinkQueue& Q){
    /* 
     * ===  FUNCTION  ======================================================================
     *         Name:  ClearQueue
     *  Description:  Clear Q to an emply queue.
     * =====================================================================================
     */
    QElemtype temp;
    while(!QueueEmpty(Q))
        if(!DeQueue(Q, temp))   return FAILURE;
    return SUCCESS;
}

Status EnQueue(LinkQueue& Q, QElemtype e){
    /* 
     * ===  FUNCTION  ======================================================================
     *         Name:  EnQueue
     *  Description:  insert e to Queue ('s rear).
     * =====================================================================================
     */
    QNode* NewNodePtr = (QNode*)malloc(sizeof(QNode));
    if(!NewNodePtr) return FAILURE;
    NewNodePtr -> data = e;
    NewNodePtr -> next = NULL;
    Q.rear -> next = NewNodePtr;
    Q.rear = NewNodePtr;
    return SUCCESS;
}    

Status DeQueue(LinkQueue& Q, QElemtype& e){
    /* 
     * ===  FUNCTION  ======================================================================
     *         Name:  DeQueue
     *  Description:  Delete the first element in Q after assigning it to e.
     * =====================================================================================
     */
    if(QueueEmpty(Q))   return FAILURE;
    e = (Q.front -> next) -> data;
    QNode* FreeHere = Q.front -> next;
    if (FreeHere == Q.rear)  Q.rear = Q.front;
    Q.front -> next = FreeHere -> next;
    free(FreeHere); FreeHere = NULL;
    return SUCCESS;
}

bool QueueEmpty(LinkQueue Q){
    /* 
     * ===  FUNCTION  ======================================================================
     *         Name:  QueueEmpty
     *  Description:  return TRUE if Q is empty; else return FALSE.
     * =====================================================================================
     */
    if(Q.front->next == NULL)   return TRUE;
    else return FALSE;
}

Code

/*
 * =====================================================================================
 *
 *       Filename:  BiTree.cpp
 *
 *    Description:  Implemrnt a BiTree in C.
 *
 *        Version:  1.0
 *        Created:  2021/10/21 18:21:42
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  CuSO4_Deposit (Depoze), CuSO4D@protonmail.com
 */         
 <stdio.h>
 <iostream>
 <stdlib.h>

 TRUE 1
 FALSE 0
 SUCCESS 1
 FAILURE 0

typedef int Status;
typedef char TElemtype;
typedef struct BiTNode{
    TElemtype data;
    struct BiTNode* lchild;
    struct BiTNode* rchild;
}BiTNode;

// Function Declaration
Status InitBiTree(BiTNode* T);
Status DestroyBiTree(BiTNode*& T); 
Status ClearBiTree(BiTNode*& T);
bool BiTreeEmpty(BiTNode* T);
Status CreateBiTree(BiTNode*& T);
int BiTreeDepth(BiTNode* T);
TElemtype Value(BiTNode* T);
Status Assign(BiTNode* T, TElemtype e);
BiTNode* Parent(BiTNode* T);
BiTNode* LeftChild(BiTNode* T);
BiTNode* RightChild(BiTNode* T);
Status InsertChild(BiTNode* T, int LR, TElemtype Value);
Status DeleteChild(BiTNode*& T, int LR);
Status PostorderTraverse(BiTNode* T, Status (*visit)(BiTNode*));
Status LevelorderTraverse(BiTNode* T, Status (*visit)(BiTNode*));

Status InitBiTree(BiTNode* T){
    /* 
     * ===  FUNCTION  ======================================================================
     *         Name:  InitBiTree
     *  Description:  Initialize a BiTree, assigning NULL to pointers.
     * =====================================================================================
     */
    T->lchild = NULL;
    T->rchild = NULL;
    return SUCCESS;
}

Status DestroyBiTree(BiTNode*& T){
    /* 
     * ===  FUNCTION  ======================================================================
     *         Name:  DestroyBiTree
     *  Description:  free memory.
     * =====================================================================================
     */
    if(!T) return SUCCESS;
    DestroyBiTree(T->lchild);
    DestroyBiTree(T->rchild);
    free(T); T = NULL;
    return SUCCESS;
}

Status PostorderTraverse(BiTNode* T, Status (*visit)(BiTNode*)){
    /* 
     * ===  FUNCTION  ======================================================================
     *         Name:  PostorderTraverse
     *  Description:  Postorfer traverse a tree. to each node N. execute visit(N);
     * =====================================================================================
     */
    if(!T)  return SUCCESS;
    PostorderTraverse(T->lchild, visit);
    PostorderTraverse(T->rchild, visit);
    visit(T);
    return SUCCESS;
}

Status ClearBiTree(BiTNode*& T){
    /* 
     * ===  FUNCTION  ======================================================================
     *         Name:  ClearBiTree
     *  Description:  Delete all son nodes, T becomes an empty tree.
     * =====================================================================================
     */
    if(!T) return SUCCESS;
    ClearBiTree(T->lchild);
    ClearBiTree(T->rchild);
    DeleteChild(T, 0);
    DeleteChild(T, 1);
    return SUCCESS;
}

Status CreateBiTree(BiTNode*& T){
    /* 
     * ===  FUNCTION  ======================================================================
     *         Name:  CreateBiTree
     *  Description:  input a preorder traverse sequence, replace empty tree with '#'.
     *                  Function will create a BiTree with T as its root.
     * =====================================================================================
     */
    char temp = '0';
    std::cin>>temp;
    if (temp == '#'){
        T = NULL;
        return SUCCESS;
    }
    else{
        if(!(T = (BiTNode*)malloc(sizeof(BiTNode)))) return FAILURE;
        T->data = temp;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
}

TElemtype Value(BiTNode* T){
    /* 
     * ===  FUNCTION  ======================================================================
     *         Name:  Value
     *  Description:  return the data of T.
     * =====================================================================================
     */
    return T->data;
}

Status Assign(BiTNode* T, TElemtype e){
    /* 
     * ===  FUNCTION  ======================================================================
     *         Name:  Assign
     *  Description:  assign e to T->data.
     * =====================================================================================
     */
    if(!T)  return FAILURE;
    T->data = e;
    return SUCCESS;
}

Status DeleteChild(BiTNode*& T, int LR){
    /* 
     * ===  FUNCTION  ======================================================================
     *         Name:  DeleteChlid
     *  Description:  Delete the child of a node. L = 0; R = 1.
     * =====================================================================================
     */
    if(LR){
        if(!T->rchild)  return SUCCESS;
        free(T->rchild);    T->rchild = NULL;
    }
    else{   //LR = 1
        if(!T->lchild)  return SUCCESS;
        free(T->lchild);    T->lchild = NULL; 
    }
    return SUCCESS;
}

Status InsertChild(BiTNode* T, int LR, TElemtype ChildData){
    /* 
     * ===  FUNCTION  ======================================================================
     *         Name:  InsertChild
     *  Description:  insert a child to this root. L = 0, R = 1.
     *                  if the place has already got a child, return FALSE. 
     * =====================================================================================
     */
    if(LR){
        if(T->rchild)   return FAILURE;
        BiTNode* temp = (BiTNode*)malloc(sizeof(BiTNode));
        temp->data = ChildData;
        temp->lchild = NULL; temp->rchild = NULL;
        T->rchild = temp;
    }
    else{   //LR = 1
        if(T->lchild)   return FAILURE;
        BiTNode* temp = (BiTNode*)malloc(sizeof(BiTNode));
        temp->data = ChildData;
        temp->lchild = NULL; temp->rchild = NULL;
        T->lchild = temp;
    }
    return SUCCESS;
}

bool BiTreeEmpty(BiTNode* T){
    /* 
     * ===  FUNCTION  ======================================================================
     *         Name:  BiTreeEmpty
     *  Description:  if BiTree is empty, return TRUE, else return FALSE.
     * =====================================================================================
     */
   if(T)    return TRUE;
   else return FALSE;
}

int BiTreeDepth(BiTNode* T){
    /* 
     * ===  FUNCTION  ======================================================================
     *         Name:  BiTreeDepth
     *  Description:  return the depth of bitree. (the depth of only a root is 1)
     * =====================================================================================
     */
    if(!T)  return 0;
    int lDepth = BiTreeDepth(T->lchild);
    int rDepth = BiTreeDepth(T->rchild);
    return lDepth < rDepth
        ? rDepth + 1
        : lDepth + 1;
}

Status LevelorderTraverse(BiTNode* T, Status (*visit)(BiTNode*)){
    /* 
     * ===  FUNCTION  ======================================================================
     *         Name:  LevelorderTraverse
     *  Description:  Traverse in level order, based on queue.
     * =====================================================================================
     */
    LinkQueue Q;
    InitQueue(Q);
    QElemtype Processing;
    if(!T)  return SUCCESS;
    EnQueue(Q, T);
    while (!QueueEmpty(Q)){
        DeQueue(Q, Processing);
        if(!visit(Processing))  return FAILURE;
        if(Processing->lchild)  EnQueue(Q, Processing->lchild);
        if(Processing->rchild)  EnQueue(Q, Processing->rchild);
    }

    DestroyQueue(Q);
    return SUCCESS;
}

BiTNode* Parent(BiTNode* T){
    /* 
     * ===  FUNCTION  ======================================================================
     *         Name:  Parent
     *  Description:  if T has parent return its parent, else return NULL.
     * =====================================================================================
     */
    LinkQueue Q;
    InitQueue(Q);
    QElemtype Processing;
    while (!QueueEmpty(Q)){
        DeQueue(Q, Processing);
        if(Processing->lchild == T || Processing->rchild == T)  return Processing;
        if(Processing->lchild)  EnQueue(Q, Processing->lchild);
        if(Processing->rchild)  EnQueue(Q, Processing->rchild);
    }
    return NULL;
    DestroyQueue(Q);
 
}

BiTNode* LeftChild(BiTNode* T){
    /* 
     * ===  FUNCTION  ======================================================================
     *         Name:  LeftChild
     *  Description:  return the address of T's left child. if it doesn't have one, return NULL.
     * =====================================================================================
     */
    return T->lchild;
}

BiTNode* RightChild(BiTNode* T){
    /* 
     * ===  FUNCTION  ======================================================================
     *         Name:  RightChild
     *  Description:  return the address of T's right child. if it doesn't have one, return NULL.
     * =====================================================================================
     */
    return T->rchild;
}

Test



Status TestVisit(BiTNode* T){
    /* 
     * ===  FUNCTION  ======================================================================
     *         Name:  TestVisit
     *  Description:  a test visit function for traverse.
     * =====================================================================================
     */
    if(!T)   return SUCCESS;
    printf("%c\n", T->data);
    return SUCCESS;    
}

int main(){
    BiTNode* T = (BiTNode*)malloc(sizeof(BiTNode));
    InitBiTree(T);
    Assign(T, 'a');
    InsertChild(T, 0, 'b');
    InsertChild(T, 1, 'c');
    InsertChild(LeftChild(T),0 ,'e');
    PostorderTraverse(T, TestVisit);
    LevelorderTraverse(T, TestVisit);
    ClearBiTree(T);
    PostorderTraverse(T, TestVisit);
    return 0;
}

result:

C:\WINDOWS\system32\cmd.exe /c (^"D:\Learning\Computer\Data-Structure\ADT\BiTree\BiTree.exe^" )
e
b
c
a
a
b
c
e
a
Hit any key to close this window...
Author: CuSO4_Deposit
This article uses the CC BY-NC-SA 4.0 License.
No Comments

Send Comment Edit Comment


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
Previous
Next