孩子链表表示法表示二叉树

二叉树的孩子链表表示法顾名思义，就是用链表去存储和表示每一个二叉树节点的全部孩子。
相比较一般常用的指针法表示二叉树节点的孩子而言，孩子链表表示法用指向一个一个链表的头节点或者是链表中第一个孩子节点的指针来替代原来的分别指向leftchild和rightchild的指针，该种表示方法的好处在于当该树并非二叉树，而是多叉树特别当一些节点的孩子数目不确定且非常多时，定义多个指向每个孩子节点的指针来表示孩子肯定是行不通的，这时用孩子链表去表示这些数目不确定且繁多的孩子时将会非常合理，不过这里我们先试着用孩子链表表示法去表示一棵二叉树。

二叉树的孩子链表表示法C代码如下：

#include 
#include 
#define MAX_TREENODE_NUM 100
//定义二叉树的孩子链表的节点 
typedef struct ChildNode
{
	int Child;
	struct ChildNode *Next;
}ChildNode;
//定义二叉树的节点 
typedef struct DataNode
{
	char Data;
	struct ChildNode * FirstChild;
}DataNode;
//定义二叉树 
typedef struct ChildTree
{
	DataNode Nodes[MAX_TREENODE_NUM];
	int Root;
	int TreeNodeNum;
}ChildTree;
int path[MAX_TREENODE_NUM];
//初始化树 
void InitChildTree(ChildTree **CT)
{
	(*CT)=(ChildTree *)malloc(sizeof(ChildTree));
	(*CT)->Root=1;
	(*CT)->TreeNodeNum=0;
	return;
}
//向孩子链表中加入孩子的索引位置 
ChildNode* AddToList(ChildNode * head,int child)
{
	if(head==NULL)
	{
		head=(ChildNode *)malloc(sizeof(ChildNode));
		head->Child=child;
		head->Next=NULL;
		return head;
	}
	else{
	    ChildNode * p=(ChildNode *)malloc(sizeof(ChildNode));
	    p->Child=child;
	    p->Next=NULL;
		head->Next=p;
		return head;
	}
}
//向树中插入节点 
void InsertToTree(ChildTree *CT,int index)
{
    DataNode *p;
    char leftChild,rightChild;
    p=&CT->Nodes[index];
    p->FirstChild=NULL;
   	printf(\"输入节点%c的左孩子：\\n\",p->Data) ;
   	scanf(\"%c\",&leftChild);
   	getchar(); 
   	printf(\"输入节点%c的右孩子：\\n\",p->Data) ;
   	scanf(\"%c\",&rightChild);
   	getchar(); 
   if(leftChild!=\'0\')
   {
   	CT->Nodes[++(CT->TreeNodeNum)].Data=leftChild;
   	p->FirstChild=AddToList(p->FirstChild,CT->TreeNodeNum);
   	InsertToTree(CT,CT->TreeNodeNum);
   }
   if(rightChild!=\'0\')
   {
   	CT->Nodes[++(CT->TreeNodeNum)].Data=rightChild;
   	p->FirstChild=AddToList(p->FirstChild,CT->TreeNodeNum);
   	InsertToTree(CT,CT->TreeNodeNum);
   }   
}
//创建孩子链表树 
ChildTree *CreateTree()
{
	char root;
	ChildTree *t;
	printf(\"请输入根节点：\\n\");
	scanf(\"%c\",&root);
    getchar(); 
    if(root!=\'0\')
    {
	InitChildTree(&t);
	t->Nodes[t->Root].Data=root;
	t->Nodes[t->Root].FirstChild=NULL;
	t->TreeNodeNum++;
	InsertToTree(t,t->Root);
    }
    return t;
}
//计算叶子节点个数
int LeavesNum(ChildTree *CT)
{
	int i,j,k,num=0;
	for(i=1;i<=CT->TreeNodeNum;i++)
	{
		if(CT->Nodes[i].FirstChild==NULL) num++;
	}
	return num;
}

这里我们的孩子链表并没有直接去存孩子的实体节点，而是通过存表示孩子索引位置的节点。同时二叉树的实体节点也是通过存贮在一个数组中实现的。
如果我们要判断包含某一个数据元素的节点是不是叶子节点，并且在其为叶子节点的前提下返回从根节点到该节点的路径，那么我们使用如下DFS算法进行判断并实现：

//深搜遍历二叉树
dfs(ChildTree *t,int book[],int step,int index,int element,int * target)
{
	int child1,child2,i;
	DataNode * p=&(t->Nodes[index]);
	book[step]=index;
	if(p->Data==element)
	{
	  if(p->FirstChild==NULL) 
	  {
		*target=index;
		for(i=1;i<=step;i++) path[i]=book[i];
	  }
		return ;
	}
	if(p->FirstChild!=NULL)
	{
	 child1=p->FirstChild->Child;
	 dfs(t,book,step+1,child1,element,target);
     	if(p->FirstChild->Next!=NULL)
	    {
		 child2=p->FirstChild->Next->Child;
		 dfs(t,book,step+1,child2,element,target);
	    }
    }
}
//判断指定字符是否为叶子节点
 void JudgeLeaves(ChildTree * ct,char element)
{
    int book[MAX_TREENODE_NUM]={0};
    int target=0,i;
	getchar(); 
    dfs(ct,book,1,1,element,&target);
    if(target!=0)
    {
    	printf(\"\\n是叶子节点\\n\");
    	printf(\"\\n路径如下：\\n\");
    	for(i=1;;i++)
    	{
    		printf(\"%c \",ct->Nodes[path[i]].Data);
    		if(path[i]==target) break;
		}
	}
	else printf(\"\\n不是叶子节点\\n\");
 } 
main()
{
	int leaves_num;
	char element;
	ChildTree *ct=CreateTree();
	leaves_num=LeavesNum(ct);
	printf(\"\\n叶子节点的个数为%d\\n\",leaves_num);
	printf(\"\\n请输入要判断的节点：\\n\");
	scanf(\"%c\",&element);
	JudgeLeaves(ct,element);
}

对该DFS算法加以解释，传入的参数element为我们需要寻找的目标节点包含的元素，而target为目标节点在数组中的索引位置，book数组用来记录当前经过的节点路径，index表示当前节点在数组中的索引位置，step表示目前book数组中走过了的节点个数，而我们通过一个全局数组path来记录最终的结果路径。
该DFS算法思路很简单，就是先通过传入的参数获取当前二叉树节点，并判断该节点中的元素是否为目标元素，如果是则进一步判断是不是叶子节点，如果是则将book数组记录的结果复制到最终的结果路径path当中，并将目标元素索引位置通过指针赋值给target，查找结束。如果该节点中的元素并不是我们要找的元素，同样先将当前节点加入book数组的路径当中，然后分别判断该二叉树节点的两个孩子是否为空，如果不为空就分别将两个孩子节点的索引位置取出并分别对不为空的孩子节点进一步进行DFS，直到全部查找结束为止。