treeop.cpp

参照网上的例子改写的多叉树的读写程序

    node = get_node(root, path);
    if (NULL == node)                    /* 路径为 path 的结点不存在 */
        return NULL;

    sibling = node->nextsibling;
    if (NULL == sibling)
        return NULL;

    len = strlen(node->data);
    pathlen = strlen(path);
    nextpathlen = pathlen - len + strlen(sibling->data) + 1;
    nextpath = (char *)malloc(nextpathlen);
    if (nextpath == NULL)
        return NULL;
    
    memset(nextpath, NULL, nextpathlen);
    strncpy(nextpath, path, pathlen-len);
    strcat(nextpath, sibling->data);

    *flag = sibling->flag;

    return nextpath;
}

/********************************************************
     函 数 名：update_node
     功能描述：修改路径 path 对应的结点的数据
     参数说明：
        root，树根
        path，路径
        newdata，新 data 域
        newvalue，新 value 域        
     返 回 值：成功返回1，失败返回 -1
*********************************************************/
int update_node(struct tree_node *root, 
                const char *path, 
                const char *newdata, 
                const char *newvalue)
{
    struct tree_node *destnode = NULL;

    if ((NULL == root) || (NULL == path))
        return -1;
    if ((NULL == newdata) && (NULL == newvalue))
        return -1;

    destnode = get_node(root, path);
    if (NULL == destnode)
	{
		printf("cannot get  node \n" );

        return -1;
	}

	printf("get node data =  [%s]\n",destnode->data);

    /* 修改 data 域 */
    memset(destnode->data, NULL, sizeof(destnode->data));
    strcpy(destnode->data, newdata);

    if (destnode->flag == NODE_IS_LEAF)        /* 为叶子 */
    {
        /* 修改 value 域，只有叶子才有 value 域 */
        memset(destnode->value, NULL, sizeof(destnode->value));
        strcpy(destnode->value, newvalue);
    }    

    return 1;
}

/********************************************************
  函 数 名：insert_node
  功能描述：如果 path 对应的结点是内部结点，则在路径 path 下插入一个结点；
                      如果 path 对应的结点是叶子结点，则将结点作为 path 对应的结点的兄弟
                     结点插入；
  参数说明：
      root，树根
      path，路径
      data， 新结点的 data 域，不能为 NULL
      value，新结点的 value 域 ，可以为 NULL，如果为 NULL表示结点作为内部结点插入，
                    否则表示作为叶子结点插入
  返 回 值：成功返回1，失败返回 -1
*********************************************************/
int insert_node(struct tree_node *root, const char *path, const char *data, const char *value)
{
    struct tree_node *parentnode    = NULL;
    struct tree_node *newnode        = NULL;    /* 将被插入的结点 */
    struct tree_node *sibling        = NULL;
    struct tree_node *backsibling    = NULL;    /* sibling 的前一个兄弟 */

    if ((NULL == root) || (NULL == path) || (NULL == data))
        return -1;
    
    parentnode = get_node(root, path);
    if (NULL == parentnode)
        return -1;

    newnode = (struct tree_node *)malloc(sizeof(struct tree_node));
    if (NULL == newnode)
        return -1;
    
    memset(newnode, 0, sizeof(struct tree_node));
    /* 初始化 */
    newnode->flag = -2;
    if (data != NULL)
    {    
        strcpy(newnode->data, data);
        newnode->flag = NODE_IS_BRANCH;
    }
    if (value != NULL)
    {    
        strcpy(newnode->value, value);
        newnode->flag = NODE_IS_LEAF;
    }

    if (parentnode->flag == NODE_IS_BRANCH)            /* 如果 parentnode 是内部结点 */
    {
        /* 作为 parentnode 的子结点插入 */
        insertnode_byparent(parentnode, newnode);
    }        
    else if (parentnode->flag == NODE_IS_LEAF)        /* 如果 parentnode 是叶子结点 */
    {
        /* 作为 parentnode 的兄弟插入 */        
        sibling = parentnode->nextsibling;
        if (sibling == NULL)
        {
            parentnode->nextsibling = newnode;
            
            return 1;
        }        
        
        while (sibling != NULL)
        {
            backsibling = sibling;            /* 得到 sibling 的前一兄弟 */

            sibling = sibling->nextsibling;
            
            if (sibling == NULL)
            {
                sibling = newnode;
                backsibling->nextsibling = sibling;
                
                return 1;
            }    
        }
    }


    return -1;
}

/********************************************************
     函 数 名：get_parentnode
     功能描述：得到路径 path 对应的结点父结点
     参数说明：
        root，树根
        path，结点对应的路径
        parent，path 对应结点的父结点
     返 回 值：成功返回1，失败返回 -1    
*********************************************************/
int get_parentnode(struct tree_node *root, const char *path, struct tree_node **parent)
{
    struct tree_node *node = NULL; /* path 对应的结点 */
    char *parentpath       = NULL;
    int len                = 0;

    if ((NULL == root) || (NULL == path))
        return -1;

    node = get_node(root, path);
    if (NULL == node)
        return -1;

    len = strlen(path) - strlen(node->data);
    parentpath = (char *)malloc(len);
    if ((len < 2) || (NULL == parentpath))
        return -1;
    memset(parentpath, NULL, len);

    /* 得到父结点路径 */
    strncpy(parentpath, path, len-1);        /* 要去掉 ":"，故要 -1 */
    trim(parentpath);

    *parent =  (struct tree_node *)get_node(root, parentpath) ;
    if (NULL == *parent)
        return -1;

    free(parentpath);
    parentpath = NULL;

    return 1;
}

/********************************************************
     函 数 名：get_parentnodepath
     功能描述：得到路径 path 对应的结点父结点路径
     参数说明：
        root，树根
        path，结点对应的路径
        parentpath，父结点路径
     返 回 值：成功返回父结点路径，失败返回 NULL
*********************************************************/
char *get_parentnodepath(struct tree_node *root, const char *path)
{
    struct tree_node *node = NULL; /* path 对应的结点 */
    char *parentnode_path       = NULL;
    int len                = 0;

    if ((NULL == root) || (NULL == path))
        return NULL;

    node = get_node(root, path);
    if (NULL == node)
        return NULL;

    len = strlen(path) - strlen(node->data);
    parentnode_path = (char *)malloc(len);
    if ((len < 2) || (NULL == parentnode_path))
        return NULL;
    memset(parentnode_path, NULL, len);

    /* 得到父结点路径 */
    strncpy(parentnode_path, path, len-1);        /* 要去掉 ":"，故要 -1 */
    trim(parentnode_path);
    
    return parentnode_path;
}

/********************************************************
     函 数 名：delete_node
     功能描述：删除路径 path 对应的结点
     参数说明：
        root，树根
        path，要删除的结点对应的路径        
     返 回 值：成功返回1，失败返回 -1

    思路：要删除一个结点，需知道它的父结点或前一个兄弟结点，
        这可以通过父路径得到
*********************************************************/
int delete_node(struct tree_node *root, const char *path)
{
    struct tree_node *node            = NULL;
    struct tree_node *backsibling    = NULL;    /* node 的前一个兄弟 */
    struct tree_node *nextsibling    = NULL;    /* node 的下一个兄弟 */
    struct tree_node *parentnode    = NULL;    /* node 的父结点 */

    struct tree_node *firstchild    = NULL;    /* parentnode 的第一个儿子 */
    struct tree_node *sibling        = NULL;    /* firstchild 的兄弟 */

    char *parentpath = NULL;
    int len = 0;

    if ((NULL == root) || (NULL == path))
        return -1;

    node = get_node(root, path);
    if (NULL == node)
        return -1;

    len = strlen(path) - strlen(node->data);
    parentpath = (char *)malloc(len);
    if ((len < 2) || (NULL == parentpath))
        return -1;
    memset(parentpath, NULL, len);

    /* 得到父结点路径 */
    strncpy(parentpath, path, len-1);        /* 要去掉 ":"，故要 -1 */
    trim(parentpath);
    parentnode=get_node(root, parentpath);
    if (NULL == parentnode)
        return -1;

    free(parentpath);
    parentpath = NULL;

    firstchild = parentnode->firstchild;
    if (firstchild == node)        /* 如果 node 是 parentnode 的第一个儿子 */
    {
        if (NULL != node->nextsibling)        /* parentnode 还有其它儿子 */
        {
            parentnode->firstchild = node->nextsibling;

            node->nextsibling = NULL;        /* 断开 node 与其下一兄弟的连接 */            
        }
        else
        {
            parentnode->firstchild = NULL;
        }

        free(node);                        /* 释放此结点 */
        node = NULL;

        return 1;
    }
    else
    {
        backsibling = firstchild;
        sibling = firstchild->nextsibling;
        while (sibling != NULL)
        {
            if (sibling == node)
            {
                nextsibling = sibling->nextsibling;

                if (nextsibling != NULL)
                {
                    backsibling->nextsibling = nextsibling;
                }
                else
                {
                    backsibling->nextsibling = NULL;
                }

                node->nextsibling = NULL;

                free(node);
                node = NULL;

                return 1;
            }

            backsibling = sibling;

            sibling = sibling->nextsibling;
        }
    }

    return -1;
}

/********************************************************
  函 数 名：create_treeroot
  功能描述：创建树的根结点
  参数说明：
      data，树根的 data域，其缺省参数为 NULL
  返 回 值：成功返回得到的根结点的指针，失败返回 NULL
*********************************************************/
struct tree_node *create_treeroot(char *data)
{
    struct tree_node *root = NULL;

    root = (struct tree_node *)malloc(sizeof(struct tree_node));
    if (NULL == root)
        return NULL;

    memset(root, NULL, sizeof(struct tree_node));

    root->flag = -1;
    if (NULL != data)
        strcpy(root->data, data);

    return root;
}

/********************************************************
  函 数 名：insert_subtree
  功能描述：插入一棵子树
  参数说明：
      root，根
      path，路径
      subtree，子树
  返 回 值：成功返回 1， 失败 -1
*********************************************************/
int insert_subtree(struct tree_node *root, const char *path, struct tree_node *subtree)
{
    struct tree_node *parentnode = NULL;

    parentnode=get_node(root, path);
    if (NULL == parentnode)
        return -1;

    insertnode_byparent(parentnode, subtree);

    return 1;
}


void print_tree(struct tree_node *root,int spaceNum)
{

	if(root != NULL)  // 非叶节点
	{
		struct tree_node *child = root->firstchild;
		struct tree_node *sibling = root->nextsibling;
		int i;
		for(i=0;i<spaceNum;i++)
		{
			printf("   ");
		}

		if(root->flag!=0)
			printf("[%s]\n",root->data);
		else
			printf("%s=%s\n",root->data,root->value);
	
		if(child != NULL)
		{
			print_tree(child,spaceNum+1);
		}


		if( sibling != NULL)
		{
			
			print_tree(sibling,spaceNum);
			
			//sibling = sibling->nextsibling;	
		}
	}


}


void print_tree(struct tree_node *root)
{

	if(root != NULL)  // 非叶节点
	{
		struct tree_node *child = root->firstchild;
		struct tree_node *sibling = root->nextsibling;
		
		if(root->flag!=0)
			printf("[%s]\n",root->data);
		else
			printf("%s=%s\n",root->data,root->value);
	
		if(child != NULL)
		{
			//printf("  ");
			print_tree(child);
		}


		if( sibling != NULL)
		{
			
			print_tree(sibling);
			
		}
	}


}








//////////////////////////////////////////////////////////////////////