跪求关于c语言多叉树添加节点的问题

数据结构:

struct list

{

/* other data */

int effectif_class_1

int effectif_class_2

struct list *parent

struct list *child[]

}

struct list * findNode(struct list *point)

{

int i

if(point->data == data)

return point

i=0

while(point->child[i] != NULL){

if( (findNode(point->child[i])) == point->child[i])

return point->child[i]

i++

}

return NULL

}

void addNode_changeNoeud(struct list *point)

{

int i=0

while(point->child[i] != NULL)

{

point->child[i]->Noeud ++

addNode_changeNoeud(point->child[i])

i++

}

}

void addNode(struct list *point, /* data */)

{ //在point的最右端插入一个子节点

int i=0

/* 定位到最右端 */

while(point->child[i] != NULL){

i++

}

point->child[i] = (struct list *)malloc(sizeof(struct list))

/* 保存其他数据到 point->child[i]->data */

/* 更改所有父节点的 effectif_class */

struct list *tmp

tmp = point->parent

while(tmp != NULL){

tmp->effectif_class_1 = tmp->effectif_class_1 + /* effectif_class_1 */

tmp->effectif_class_2 = tmp->effectif_class_2 + /* effectif_class_2 */

tmp = tmp->parent

}

/* 插入节点后,更新编号 */

point->child[i] = point->child[i-1] + 1

addNode_changeNoeud(point)/* 这个不好说,用于更新编号Noeud的,自己理解吧... */

}

由0到多个节点以节点指针连接起来的数据结构，称为链表，

链表结点通常是结构体(或类)，至少含有一个指向本结构体类型的指针

只含指向子节点不含指向父节点的链表为单向链表，只有从父向子遍历，

当节点同时含有指向父节点的指针时，就是双向链表，可以父到子的遍历也可以从子到父的遍历

指向子节点的指针只有一个时，就是单链表，遍历最为简单

有两个时为二叉树，两个以上的是多叉树，遍历就有点复杂

增加节点，就是把新的节点添加到链表中，使其成为链的一分子

删除节点就是把一个在链表中的节移除，使链表遍历时不会访问到这个被删除的元素

下面程序有演示添加和删除 *** 作:

//本来是回复另一个问题未没能完整帖上程序，这里竟然可以发个完整版就做学习参考的例子吧

//要求用链表

//给出两个整数数列，先要将其合并为一个数列，并且合并后整个数列有序(从小到大)

#include<stdio.h>

typedef struct node{node* nextint data} Node

void Sort_Select(Node**phead) //简单排序之选择法(因为链表结构,想简单冒泡都不成咧)

{

Node *pSelect,*pSelectPre,*p1,*p2,*p2_pre,*newHead,*newEnd

newHead = newEnd =NULL

for(p1=*pheadp1)

{

for(pSelectPre=NULL,pSelect=p2_pre=p1,p2=p1->nextp2p2_pre=p2,p2=p2->next) //选择最小元素

if(pSelect->data >p2->data)

{

pSelect = p2

pSelectPre = p2_pre//单链表，不能直接访问当前结点的父结点，只好用两指针跟踪了

}

//从旧链删除pSelect

if(!pSelectPre) //删头结点

p1 = p1->next

else

pSelectPre->next = pSelect->next

//追加到新链表尾部

if(!newEnd)//第一次

{

newEnd = newHead = pSelect

newEnd->next = NULL

}

else

{

newEnd->next = pSelect

newEnd = pSelect

newEnd->next = NULL

}

}

*phead = newHead

}

void main()

{

int iN,iM,i,j

Node *headN=NULL, *headM=NULL, *endN=NULL, *endM=NULL,*Ntmp

do{

printf("输入第一数列大小(1-5000):")

scanf("%d",&iN)

if(iN>5000||iN<1) printf("输入不合法，请重试\n")

}while(iN>5000||iN<1)

printf("输入第一数列的%d个整数:\n",iN)

for(i=0i<iNi++)

{

scanf("%d",&j)

Ntmp = (Node*)malloc(sizeof(Node))

Ntmp->data = j

Ntmp->next = NULL

if(!headN)

{

endN = headN = Ntmp//<<<第一个结点

}

else

{

endN->next = NtmpendN = Ntmp//<<<直接添在尾(未排序)

}

}

do{

printf("输入第二数列大小(1-5000):")

scanf("%d",&iM)

if(iM>5000||iM<1) printf("输入不合法，请重试\n")

}while(iM>5000||iM<1)

printf("输入第二数列的%d个整数:\n",iM)

for(i=0i<iMi++)

{

scanf("%d",&j)

Ntmp = (Node*)malloc(sizeof(Node))

Ntmp->data = j

Ntmp->next = NULL

if(!headM)

{

endM = headM = Ntmp

}

else

{

endM->next = NtmpendM = Ntmp

}

}

endN->next = headM//<<<合并到连表headN 就是这么简单

//endN = endMheadM=endM=NULL//<<<完成使命了不再需要也不必理它们

Sort_Select(&headN)//链表排序

printf("\n合并排序的结果:\n")

for(Ntmp=headNNtmpNtmp=Ntmp->next) printf("%d ",Ntmp->data)//<<<遍历链表

//释放内存 //程序就要退出系统，下面的内存释放已不是必需，系统能回收这些内存 不过为了好习惯

while(headN)

{

Ntmp = headN

headN = headN->next

free(Ntmp)

}

printf("\n")system("pause")//窗口可能会关，稍等方便查看结果

}

TreeNode.java

/*

 * Copyright Walker Studio

 * All Rights Reserved.

 * 

 * 文件名称： TreeNode.java

 * 摘 要：

 * 作 者： Walker

 * 创建时间： 2013-03-19

 */

package com.walker.commons.data.model

/**

 * 树节点

 * 

 * @author Walker

 * @version 1.0.0.0

 */

public class TreeNode 

{

/** 节点Id*/

private String nodeId

/** 父节点Id*/

private String parentId

/** 文本内容*/

private String text

/**

 * 构造函数

 * 

 * @param nodeId 节点Id

 */

public TreeNode(String nodeId)

{

this.nodeId = nodeId

}

/**

 * 构造函数

 * 

 * @param nodeId 节点Id

 * @param parentId 父节点Id

 */

public TreeNode(String nodeId, String parentId)

{

this.nodeId = nodeId

this.parentId = parentId

}

public String getNodeId() {

return nodeId

}

public void setNodeId(String nodeId) {

this.nodeId = nodeId

}

public String getParentId() {

return parentId

}

public void setParentId(String parentId) {

this.parentId = parentId

}

public String getText() {

return text

}

public void setText(String text) {

this.text = text

}

}

ManyTreeNode.java

/*

 * Copyright Walker Studio

 * All Rights Reserved.

 * 

 * 文件名称： ManyTreeNode.java

 * 摘 要：

 * 作 者： Walker

 * 创建时间： 2013-03-19

 */

package com.walker.commons.data.model

import java.util.ArrayList

import java.util.List

/**

 * 多叉树节点

 *

 * @author Walker

 * @verion 1.0.0.0

 */

public class ManyTreeNode 

{

/** 树节点*/

private TreeNode data

/** 子树集合*/

private List<ManyTreeNode> childList

/**

 * 构造函数

 * 

 * @param data 树节点

 */

public ManyTreeNode(TreeNode data)

{

this.data = data

this.childList = new ArrayList<ManyTreeNode>()

}

/**

 * 构造函数

 * 

 * @param data 树节点

 * @param childList 子树集合

 */

public ManyTreeNode(TreeNode data, List<ManyTreeNode> childList)

{

this.data = data

this.childList = childList

}

public TreeNode getData() {

return data

}

public void setData(TreeNode data) {

this.data = data

}

public List<ManyTreeNode> getChildList() {

return childList

}

public void setChildList(List<ManyTreeNode> childList) {

this.childList = childList

}

}

ManyNodeTree.java

/*

 * Copyright Walker Studio

 * All Rights Reserved.

 * 

 * 文件名称： ManyNodeTree.java

 * 摘 要：

 * 作 者： Walker

 * 创建时间： 2013-03-19

 */

package com.walker.commons.data.model

import java.util.ArrayList

import java.util.List

/**

 * 多叉树生成、遍历工具

 * 

 * @author Walker

 * @version 1.0.0.0

 */

public class ManyNodeTree 

{

/** 树根*/

private ManyTreeNode root

/**

 * 构造函数

 */

public ManyNodeTree()

{

root = new ManyTreeNode(new TreeNode("root"))

}

/**

 * 生成一颗多叉树，根节点为root

 * 

 * @param treeNodes 生成多叉树的节点集合

 * @return ManyNodeTree

 */

public ManyNodeTree createTree(List<TreeNode> treeNodes)

{

if(treeNodes == null || treeNodes.size() < 0)

return null

ManyNodeTree manyNodeTree =  new ManyNodeTree()

//将所有节点添加到多叉树中

for(TreeNode treeNode : treeNodes)

{

if(treeNode.getParentId().equals("root"))

{

//向根添加一个节点

manyNodeTree.getRoot().getChildList().add(new ManyTreeNode(treeNode))

}

else

{

addChild(manyNodeTree.getRoot(), treeNode)

}

}

return manyNodeTree

}

/**

 * 向指定多叉树节点添加子节点

 * 

 * @param manyTreeNode 多叉树节点

 * @param child 节点

 */

public void addChild(ManyTreeNode manyTreeNode, TreeNode child)

{

for(ManyTreeNode item : manyTreeNode.getChildList())

{

if(item.getData().getNodeId().equals(child.getParentId()))

{

//找到对应的父亲

item.getChildList().add(new ManyTreeNode(child))

break

}

else

{

if(item.getChildList() != null && item.getChildList().size() > 0)

{

addChild(item, child)

}

}

}

}

/**

 * 遍历多叉树 

 * 

 * @param manyTreeNode 多叉树节点

 * @return 

 */

public String iteratorTree(ManyTreeNode manyTreeNode)

{

StringBuilder buffer = new StringBuilder()

buffer.append("\n")

if(manyTreeNode != null) 

{

for (ManyTreeNode index : manyTreeNode.getChildList()) 

{

buffer.append(index.getData().getNodeId()+ ",")

if (index.getChildList() != null && index.getChildList().size() > 0 ) 

{

buffer.append(iteratorTree(index))

}

}

}

buffer.append("\n")

return buffer.toString()

}

public ManyTreeNode getRoot() {

return root

}

public void setRoot(ManyTreeNode root) {

this.root = root

}

public static void main(String[] args)

{

List<TreeNode> treeNodes = new ArrayList<TreeNode>()

treeNodes.add(new TreeNode("系统权限管理", "root"))

treeNodes.add(new TreeNode("用户管理", "系统权限管理"))

treeNodes.add(new TreeNode("角色管理", "系统权限管理"))

treeNodes.add(new TreeNode("组管理", "系统权限管理"))

treeNodes.add(new TreeNode("用户菜单管理", "系统权限管理"))

treeNodes.add(new TreeNode("角色菜单管理", "系统权限管理"))

treeNodes.add(new TreeNode("用户权限管理", "系统权限管理"))

treeNodes.add(new TreeNode("站内信", "root"))

treeNodes.add(new TreeNode("写信", "站内信"))

treeNodes.add(new TreeNode("收信", "站内信"))

treeNodes.add(new TreeNode("草稿", "站内信"))

ManyNodeTree tree = new ManyNodeTree()

System.out.println(tree.iteratorTree(tree.createTree(treeNodes).getRoot()))

}

}

---