ADT tree.keywords:left child right sibling

tree.c

/*
 * =========================================================
 *       Filename:  ADT_tree.c
 *    Description:  数据结构之树
 *
 * =========================================================
 */
#include <stdio.h>
#include <stdlib.h>

/*---------------------------------------------------
 *  数据集定义
 *---------------------------------------------------*/
//一般化的树,左孩子右兄弟
typedef struct treenode{
    int elem;
    struct treenode *child;
    struct treenode *brother;
}TreeNode;
//int nodecount=0;


/*---------------------------------------------------
 *  基于一般化树的方法
 *---------------------------------------------------*/
TreeNode *PreorderSearch(TreeNode *root , int target);
TreeNode *CreatTree();
void PrePrint(TreeNode *root);

int main(){
    TreeNode *root;
    root = CreatTree();
    PrePrint(root);
//    int target = 'G';  为什么会段错误?
//    scanf("%d",&target);
//    TreeNode *find;
//    find =PreorderSearch(root , 'G');
//    printf("%c %s in tree\n",'G',(find)?"":"not");

}


TreeNode *PreorderSearch(TreeNode *root , int target){//无序二叉树的前序遍历
    if (root == NULL)
        return NULL;
    else if (target == root->elem)
        return root;
    else{
        TreeNode *result;
        result = PreorderSearch(root->child ,target);
        if (result == NULL)
            result = PreorderSearch(root->brother , target);
        return result;
    }
}
TreeNode *CreatTree(){
/*     tree >
 *           A
 *      B    C    D
 *         E   F
 *     input >
 *         ABCD
 *         CEF
 *     output >
 *           A
 *      B
 *           C
 *      E         D
 *           F
 */
    int c;//elem in tree
    TreeNode *root,*pre;//记录pre方便插入新的节点,root的pre是NULL
    int search =1;//每行输入的开头元素,都要search该元素在tree中的位置
    int child =1;//每行第二个节点插入到child节点，其它插入到brother节点
    while ( (c=getchar()) != 'q'){
        if (c =='\n')
            search =child =1;//上面已经初始化search,child为1，之后每行开始就初始化一次
        else{
            if(search){
                pre=PreorderSearch(root , c);//让下一个节点知道它的pre在哪儿
                if (!pre){//只有A节点 pre==NULL
                    root = malloc(sizeof(TreeNode));
                    root->elem =c;
                    root->child=root->brother=NULL;
//                    ++nodecount;
                    pre = root;//B节点的pre是A
                }
                search =0;
            }
            else{
                TreeNode *node = malloc(sizeof(TreeNode));
                node->elem =c;
                node->child = node->brother =NULL;
//                ++nodecount;
                if(child)
                    pre->child = node;
                else
                    pre->brother = node;
                pre = node;//更新pre
                child =0;
            }
        }
    }
    return root;
}
void PrePrint(TreeNode *root){
    if (root){
        printf ("%c ",root->elem);
        PrePrint(root->child);
        PrePrint(root->brother);
    }
}