BiTree - Implement in C
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
*/
#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define SUCCESS 1
#define 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…