CTDL&TT: Cây và thao tác

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>

struct Tnode{
    char word[20]; // D. li.u c.a nút
    struct Tnode * left;
    struct Tnode *right;
};

typedef struct Tnode treeNode;

treeNode* makeTreeNode(char *word)
{
    treeNode* newNode = NULL;
    newNode = (treeNode*)malloc(sizeof(treeNode));
    if (newNode == NULL){
        printf("Out of memory\n");
    exit(1);
    }
    else {
        newNode->left = NULL;
        newNode->right= NULL;
        strcpy(newNode->word,word);
    }

    return newNode;
}

int countNodes(treeNode *tree) {
    /* the function counts the number of nodes of a tree*/
    if( tree == NULL ) return 0;
    else {
        int ld = countNodes(tree->left);
        int rd = countNodes(tree->right);

    return 1+ld+rd;
    }
}

int depth(treeNode *tree) {
    /* the function computes the depth of a tree */
    if( tree == NULL ) return 0;
    int ld = depth(tree->left);
    int rd = depth(tree->right);
    /* if (ld > rd) return 1+ld; else return 1+rd; */

    return 1 + (ld > rd ? ld : rd);
}

void freeTree(treeNode *tree)
{
    if( tree == NULL ) return;
    freeTree(tree->left);
    freeTree(tree->right);
    free(tree);

    return;
}

void printPreorder(treeNode *tree)
{
    if( tree != NULL )
    {
        printf("%s\n", tree->word);
        printPreorder(tree->left);
        printPreorder(tree->right);
    }
}

void printInorder(treeNode *tree)
{
    if( tree != NULL )
    {
        printInorder(tree->left);
        printf("%s\n", tree->word);
        printInorder(tree->right);
    }
}

void printPostorder(treeNode *tree)
{
    if( tree != NULL )
    {
        printPostorder(tree->left);
        printPostorder(tree->right);
        printf("%s\n", tree->word);
    }
}

treeNode *RandomInsert(treeNode *tree,char *word){
    treeNode *newNode, *p;
    newNode = makeTreeNode(word);
    if ( tree == NULL ) return newNode;
    if ( rand()%2 ==0 ){
        p=tree;
        while (p->left !=NULL) p=p->left;
        p->left=newNode;
        printf("Node %s is left child of %s \n",word,(*p).word);
    }
    else {
        p=tree;
        while (p->right !=NULL) p=p->right;
        p->right=newNode;
        printf("Node %s is right child of %s \n",word,(*p).word);
    }

    return tree;
}

int main() {
    treeNode *randomTree=NULL;
    char word[20] = "a";
    while( strcmp(word,"~")!=0)
    {
        printf("\nEnter item (~ to finish): ");
        scanf("%s", word);
    if (strcmp(word,"~")==0)
        printf("Cham dut nhap thong tin nut... \n");
    else randomTree=RandomInsert(randomTree,word);
    }

    printf("The tree in preorder:\n"); printPreorder(randomTree);
    printf("The tree in postorder:\n"); printPostorder(randomTree);
    printf("The tree in inorder:\n"); printInorder(randomTree);
    printf("The number of nodes is: %d\n",countNodes(randomTree));
    printf("The depth of the tree is: %d\n", depth(randomTree));
    freeTree(randomTree);
    getch();
    return 0;
}