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

#include <stdio.h> #include <stdlib.h> #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; }
Next=NULL; return head; } else{ ChildNode * p=(ChildNode *)malloc(sizeof(
//向树中插入节点 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'
FirstChild,CT->TreeNodeNum); InsertToTree(CT,CT->TreeNodeNum); } if(rightChild!=
->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(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); }

GitHub

Gitee