<> The child linked list representation represents a binary tree
The child linked list representation of binary tree is as the name suggests , Is to use a linked list to store and represent all the children of each binary tree node .
Compared with the commonly used pointer method to represent the children of binary tree nodes , The child linked list representation replaces the original pointer with a pointer to the head node of a linked list or the first child node in the linked list leftchild and rightchild Pointer to , The advantage of this representation is that when the tree is not a binary tree , It is a multi tree, especially when the number of children of some nodes is uncertain and very large , Defining multiple pointers to each child node to represent a child must not work , At this time, it will be very reasonable to use the child list to represent these uncertain and numerous children , But here we try to use the child linked list representation to represent a binary tree .
Child linked list representation of binary tree C The code is as follows ：
#include <stdio.h> #include <stdlib.h> #define MAX_TREENODE_NUM 100
// Defines the node of the child linked list of the binary tree typedef struct ChildNode { int Child; struct ChildNode *Next; }
ChildNode; // Defines the nodes of a binary tree typedef struct DataNode { char Data; struct ChildNode *
FirstChild; }DataNode; // Define binary tree typedef struct ChildTree { DataNode Nodes[
MAX_TREENODE_NUM]; int Root; int TreeNodeNum; }ChildTree; int path[
MAX_TREENODE_NUM]; // Initialization tree void InitChildTree(ChildTree **CT) { (*CT)=(ChildTree
*)malloc(sizeof(ChildTree)); (*CT)->Root=1; (*CT)->TreeNodeNum=0; return; }
// Add the child's index position to the child's linked list 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; } }
// Insert node into tree void InsertToTree(ChildTree *CT,int index) { DataNode *p; char
leftChild,rightChild; p=&CT->Nodes[index]; p->FirstChild=NULL; printf(
" Input node %c My left child ：\n",p->Data) ; scanf("%c",&leftChild); getchar(); printf(
" Input node %c My right child ：\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); } } // Create child linked list tree
ChildTree*CreateTree() { char root; ChildTree *t; printf(" Please enter the root node ：\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; } // Calculate the number of leaf nodes 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; }
Here, our child linked list does not directly store the child's entity nodes , Instead, save the node representing the child's index position . At the same time, the entity nodes of the binary tree are also stored in an array .
If we want to judge whether the node containing a data element is a leaf node , And return the path from the root node to the node on the premise that it is a leaf node , Then we use the following DFS The algorithm is judged and implemented ：
// Deep search traversal binary tree 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); } } } // Judge whether the specified character is a leaf node 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 Is a leaf node \n"); printf(
"\n The path is as follows ：\n"); for(i=1;;i++) { printf("%c ",ct->Nodes[path[i]].Data); if(path[i]
==target) break; } } else printf("\n Not a leaf node \n"); } main() { int leaves_num; char
element; ChildTree *ct=CreateTree(); leaves_num=LeavesNum(ct); printf(
"\n The number of leaf nodes is %d\n",leaves_num); printf("\n Please enter the node to judge ：\n"); scanf("%c",&element);
JudgeLeaves(ct,element); }
Yes DFS The algorithm is explained , Parameters passed in element The elements contained in the target node we need to find , and target Is the index position of the target node in the array ,book Array is used to record the current node path ,index Indicates the index position of the current node in the array ,step Indicates that at present book Number of nodes passed in the array , And we pass a global array path To record the final result path .
Should DFS The algorithm is very simple , First, get the current binary tree node through the passed in parameters , And judge whether the element in the node is the target element , If yes, further judge whether it is a leaf node , If so, the book The result of the array record is copied to the final result path path among , And assign the index position of the target element to target, Find end . If the element in this node is not the element we are looking for , Also, add the current node first book In the path of the array , Then judge whether the two children of the binary tree node are empty , If it is not empty, the index positions of the two child nodes will be taken out respectively, and the child nodes that are not empty will be further modified respectively DFS, Until all searches are completed .
Technology