普通的树有很多种表示方法

双亲表示法,data是数据域,存储结点的数据信息,而parent是指针域,存储该结点的双亲在数组中的下标

树的双亲表示法数据结构:

typedef int TElemType;

typedef struct PTNode {

    TElemType data;

    int parent;

}PTnode; //结点结构

typedef struct {

    PTNode nodes[MAX_TREE_SIZE];

    int r, n;

}PTree; //树结构

 

孩子表示法,将每个结点的孩子结点排列起来,以单链表作为存储结构,则n个结点有n个孩子链表,如果是叶子结点则此单链表为空,然后n个头指针又组成一个线性表,采用顺序存储结构,存放进一个一维数组中

两种结点结构,一个是孩子链表的孩子结点,其中child是数据域,用来存储某个结点在表头数组里的下标,next是指针域,用来存储指向某结点的下一个孩子结点的指针

另一个是表头数组的表头结点,其中data是数据域,存储某结点的数据信息,firstchild是头指针域,存储该结点的孩子链表的头指针

树的孩子表示法数据结构:

typedef struct CTNode {

    int child;

    struct CTNode *next;

} *ChildPtr; //孩子结点

typedef struct {

    TElemType data;

    ChildPtr firstchild;

} CTBox; //表头结构

typedef struct {

    CTBox nodes[MAX_TREE_SIZE];

    int r, n;

} CTree; //树结构

 

孩子兄弟表示法,其中data是数据域,firstchild为指针域,存储该结点的第一个孩子结点的存储地址,rightsib是指针域,存储该结点的右兄弟结点的存储地址

树的孩子兄弟表示法数据结构:

typedef struct CSNode {

    TElemType data;

    struct CSNode *firstchild, *rightsib;

} CSNode, *CSTree;

 

二叉树是n个结点的有限集合,该集合或者为空集(空二叉树),或者由一个根节点和两科互不相交的,分别称为根节点的左子树和右子树的二叉树组成

二叉树链式存储结构,data是数据域,lchild和rchild都是指针域,分别存放指向左孩子和右孩子的指针

二叉树的链表结点数据结构:

typedef struct BiTNode {

    TElemType data;

    struct BitNode *lchild, *rchild;

} BiTNode, *BiTree; //结点结构

创建二叉树:

交互输入结点数据,如果输入的是0,表示结点不存在,不分配节点空间,创建简单二叉树以及先序遍历

#include <stdio.h>
#include <malloc.h>

typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
}TreeNode;

TreeNode* CreateTree(){
    TreeNode *t;
    int ch;
    scanf_s(“%d”, &ch);
    if (ch == 0)
        t = NULL;
    else {
        t = (TreeNode *)malloc(sizeof(TreeNode));
        t->data = ch;
        printf(“\nInput Node %d left child node: “, t->data);
        t->left = CreateTree();
        printf(“\nInput Node %d right child node: “, t->data);
        t->right = CreateTree();
    }
    return t;
}

int FirstVisit(TreeNode *n){
    if (n == NULL)
        return 0;
    else {
        printf(“%d “, n->data);
        FirstVisit(n->left);
        FirstVisit(n->right);
    }
    return 0;
}

int main(){
    TreeNode *tree;
    tree = (TreeNode *)malloc(sizeof(TreeNode));
    printf(“Input root node: “);
    tree = CreateTree();
    printf(“First Visit: “);
    FirstVisit(tree);
    printf(“\n”);

    return 0;
}

发表评论