树(C语言实现,基于链式结构)

蚂蚁的窝 2014-08-07

树(C语言实现,基于链式结构)

Tree.h文件

/**
 * 树(C语言实现,基于链式结构)
 * 该树为二叉树
 * 指定数据类型为字符型
 */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0

typedef int Status;
typedef int bool;
typedef char ElemType;

//定义树节点的结构
typedef struct TreeNode{
    ElemType data;
    struct TreeNode *leftchild, *rightchild;
}TreeNode;
//定义树的结构
typedef struct TreeNode* Tree;

/*
 * 初始化树
 */
Tree InitTree(Tree t);
/*
 * 创建树按照给定的规则
 */
void CreateTree(Tree* t, char* s);
/*
 * 销毁树
 */
void DestroyTree(Tree t);
/*
 * 清空树
 */
void ClearTree(Tree t);
/*
 * 判断树是否为空
 */
bool TreeEmpty(Tree t);
/*
 *
 */
int TreeDepth();
/*
 *
 */
void Root();
/*
 *
 */
void Value();
/*
 *
 */
void Assign();
/*
 *
 */
void Parent();
/*
 *
 */
void LeftChild();
/*
 *
 */
void RightChild();
/*
 *
 */
void InsertChild();
/*
 *
 */
void DeleteChild();
/*
 * 前序遍历树
 */
void PreOrderTraverse(Tree t);
/*
 * 中序遍历树
 */
void InOrderTraverse(Tree t);
/*
 * 后序遍历树
 */
void PostOrderTraverse(Tree t);
/*
 * 层次遍历树
 */
void LevelOrderTraverse(Tree t);

Tree.c文件

#include <stdio.h>
#include <stdlib.h>
#include "Tree.h"

int i = 0;
int tree_depth_num;
Tree InitTree(Tree t)
{
    return t = NULL;
}

void CreateTree(Tree* t, char* s)  //该处的Tree*是TreeNode指针的指针,用于操作指针变量的值
{
    //使用前序遍历方式创建树
    char ch = s[i];
    i++;
    if(ch == '#')
        *t = NULL;
    else{
        *t = (TreeNode*)malloc(sizeof(TreeNode));
        (*t)->data = ch;
        CreateTree(&(*t)->leftchild, s);
        CreateTree(&(*t)->rightchild, s);
    }
}

void DestroyTree(Tree t)
{
    if(t == NULL)
        return;
    ClearTree(t->leftchild);
    ClearTree(t->rightchild);
    free(t);
}

void ClearTree(Tree t)
{
    if(t == NULL)
        return;
    t->data = ' ';
    ClearTree(t->leftchild);
    ClearTree(t->rightchild);
}

bool TreeEmpty(Tree t)
{
    if(t == NULL)
        return TRUE;
    else
        return FALSE;
}

void ProOrderTraverse(Tree t)
{
    if(t == NULL)
        return;
    printf("%c\n", t->data);
    ProOrderTraverse(t->leftchild);
    ProOrderTraverse(t->rightchild);
}

void InOrderTraverse(Tree t)
{
    if(t == NULL)
        return;
    InOrderTraverse(t->leftchild);
    printf("%c\n",t->data);
    InOrderTraverse(t->rightchild);
}

void PostOrderTraverse(Tree t)
{
    if(t == NULL)
        return;
    PostOrderTraverse(t->leftchild);
    PostOrderTraverse(t->rightchild);
    printf("%c\n",t->data);
}

void LevelOrderTraverse(Tree t)
{
    //要用到队列
}

int main()
{
    Tree t = InitTree(t);
    CreateTree(&t,"AB#D##C##");//AB#D##C## //ABDG##H###CE#I##F##
    ProOrderTraverse(t);
    ClearTree(t);
    ProOrderTraverse(t);
}

将C语言梳理一下,分布在以下10个章节中:

  1. Linux-C成长之路(一):Linux下C编程概要 http://www.linuxidc.com/Linux/2014-05/101242.htm
  2. Linux-C成长之路(二):基本数据类型 http://www.linuxidc.com/Linux/2014-05/101242p2.htm
  3. Linux-C成长之路(三):基本IO函数操作 http://www.linuxidc.com/Linux/2014-05/101242p3.htm
  4. Linux-C成长之路(四):运算符 http://www.linuxidc.com/Linux/2014-05/101242p4.htm
  5. Linux-C成长之路(五):控制流 http://www.linuxidc.com/Linux/2014-05/101242p5.htm
  6. Linux-C成长之路(六):函数要义 http://www.linuxidc.com/Linux/2014-05/101242p6.htm
  7. Linux-C成长之路(七):数组与指针 http://www.linuxidc.com/Linux/2014-05/101242p7.htm
  8. Linux-C成长之路(八):存储类,动态内存 http://www.linuxidc.com/Linux/2014-05/101242p8.htm
  9. Linux-C成长之路(九):复合数据类型 http://www.linuxidc.com/Linux/2014-05/101242p9.htm
  10. Linux-C成长之路(十):其他高级议题

相关推荐