首页 > 代码库 > 家谱图-二叉树
家谱图-二叉树
因为树有多种表示方式，也可以不用二叉树来表示，但是那样有局限性， 就比如一个节点有几个孩子，这个数目都是不确定的，如果用二叉树来表示，那样就比较清楚的显示出家谱中的人员组成，但是不能用孩子表示法，因为那样最多只能表示两个孩子，但是可以转化一下表示方法，用孩子兄弟表示方法来表示，那样，就可以有无限多个(理论上)孩子，就是一个节点有两个指针，一个指向第一个孩子，一个指向它的右兄弟，所以，这种二叉树可以表示好多方式，其实和那种二叉树一样，只是解释不一样了而已，在计算机中更是差不多，因为计算机没有这些逻辑，这些都是我们为了方便而想象出来的，家谱图主要实现的功能有增加节点，查询一个节点的子节点，删除一个节点(同时删除)它的子树。
1 #include <stdio.h> 2 #include <stdlib.h> 3 4 typedef char TElemType; 5 6 //孩子兄弟表示法 7 typedef struct Tree{ 8 TElemType data; 9 struct Tree *firstchild, *rightbro; 10 }CSNode, *PCSTree; 11 12 PCSTree ptr; 13 char data; 14 15 void createTree(PCSTree *T)//创建二叉树 16 { 17 TElemType data; 18 scanf("%c", &data); 19 getchar(); 20 if(data =http://www.mamicode.com/= ‘ ‘) 21 *T = NULL; 22 else 23 { 24 *T = (PCSTree)malloc(sizeof(CSNode)); 25 (*T) -> data =http://www.mamicode.com/ data; 26 printf("Please input %c‘s first child\n", data); 27 createTree(&(*T) -> firstchild); 28 printf("Please input %c‘s right brother\n", data); 29 createTree(&(*T) -> rightbro); 30 } 31 } 32 33 void preOrderTraverse(PCSTree T)//前续遍历 34 { 35 if(T == NULL) 36 return ; 37 printf("%c ", T -> data); 38 preOrderTraverse(T -> firstchild); 39 preOrderTraverse(T -> rightbro); 40 } 41 42 void findChild(PCSTree T, char data)//查找某个节点的孩子 43 { 44 if (T == NULL) 45 return ; 46 PCSTree p; 47 p = T->firstchild; 48 if (T->data =http://www.mamicode.com/= data) 49 { 50 if(p == NULL) 51 { 52 printf("No member!\n"); 53 return; 54 } 55 while (p->rightbro != NULL)//打印出来他所有的孩子 56 { 57 printf("%c ", p->data); 58 p = p->rightbro; 59 } 60 printf("%c\n", p->data); 61 return ; 62 } 63 else 64 { 65 findChild(T->firstchild, data);//如果找不到的话，继续找他的子节点 66 findChild(T->rightbro, data); 67 } 68 } 69 70 int addMember(PCSTree *T)//添加新成员 71 { 72 if(*T == NULL)//用于递归时判断退出条件 73 return 0; 74 PCSTree pt; 75 if ((*T)->data =http://www.mamicode.com/= data)//找到父节点 76 { 77 if ((*T)->firstchild != NULL) 78 { 79 pt = (*T)->firstchild; 80 while(pt->rightbro != NULL)//找到最右边的一个添加新节点 81 pt = pt->rightbro; 82 pt->rightbro = ptr; 83 return 1;//添加成功， 返回1 84 } 85 (*T)->firstchild = ptr; 86 return 1; 87 } 88 89 if (addMember(&(*T)->firstchild) == 1)//递归再找匹配的父节点 90 return 1; 91 if (addMember(&(*T)->rightbro) == 1) 92 return 1; 93 return 0; 94 } 95 96 void findAndFree(PCSTree *T)//找到传过来的某个节点并且将它释放掉，并且释放掉它所有的子节点 97 { 98 if(*T == NULL) 99 return;100 PCSTree p1, p2;101 p1 = (*T)->firstchild;102 p2 = (*T)->rightbro;103 findAndFree(&p1);104 findAndFree(&p2);105 free(*T);106 }107 108 int deleteMember(PCSTree *T)//删除节点函数(删除其子树)109 {110 PCSTree pt;111 if(*T == NULL)112 return 0;113 //类似链表中的删除，要删除当前元素，先要找到它的前一个114 if((*T)->firstchild == NULL && (*T)->rightbro == NULL)115 {116 if ((*T)->data =http://www.mamicode.com/= data)117 {118 free(*T);119 return 1;120 }121 return 0;122 }123 //如果是它的子节点124 if((*T)->firstchild != NULL && (*T)->firstchild->data =http://www.mamicode.com/= data)125 {126 pt = (*T)->firstchild;127 if (pt->rightbro != NULL)128 {129 (*T)->firstchild = pt->rightbro;130 }131 else132 (*T)->firstchild = NULL;133 if(pt->firstchild != NULL)134 findAndFree(&(pt->firstchild));135 free(pt);136 return 1;137 }138 //如果是它的右兄弟节点139 else if ((*T)->rightbro != NULL && (*T)->rightbro->data =http://www.mamicode.com/= data)140 {141 pt = (*T)->rightbro;142 if (pt->rightbro != NULL)143 {144 (*T)->rightbro = pt->rightbro;145 146 }147 else148 (*T)->rightbro = NULL;149 if(pt->firstchild != NULL)150 findAndFree(&(pt->firstchild));151 free(pt);152 return 1;153 }154 //如果都不是，继续递归 找155 if(deleteMember(&(*T)->firstchild))156 return 1;157 if(deleteMember(&(*T)->rightbro))158 return 1;159 return 0;160 }161 162 163 int main()164 {165 // freopen("in.txt", "r", stdin);166 PCSTree T;167 printf("Input root Node:\n");168 createTree(&T);//create binary tree169 printf("The previous traverse are:\n");170 preOrderTraverse(T);//previous traverse the tree171 printf("\n");172 char newdata;173 int choice;174 do{175 printf("1. find some node‘s kids 2. add member\n");176 printf("3. delete some node 4. previous traverse the tree\n");177 printf("0. exit\n");178 scanf("%d", &choice);179 switch(choice)180 {181 case 1:182 printf("\nPlease input you want find child name:\n");183 getchar();184 scanf("%c", &data);185 findChild(T, data);186 printf("\n");187 break;188 case 2:189 if(T == NULL)190 {191 printf("Input root node:\n");192 getchar();193 createTree(&T);194 }195 else196 {197 printf("Please input you want add data\n");198 printf("Format: father child\n");199 ptr = (PCSTree)malloc(sizeof(CSNode));200 ptr->firstchild = ptr->rightbro = NULL;201 getchar();202 scanf("%c %c", &data, &newdata);203 ptr->data =http://www.mamicode.com/ newdata;204 addMember(&T);205 preOrderTraverse(T);206 printf("\n");207 }208 break;209 case 3:210 if(T == NULL)211 {212 printf("No member\n");213 break;214 }215 printf("Please input you want delete node\n");216 getchar();217 scanf("%c", &data);218 if(data =http://www.mamicode.com/= T->data)219 {220 findAndFree(&T);221 T = NULL;222 }223 else224 deleteMember(&T);225 break;226 case 4:227 if(T != NULL)228 preOrderTraverse(T);229 else230 printf("No member");231 printf("\n");232 break;233 default:234 break;235 }236 }while(choice != 0);237 return 0;238 }
家谱图-二叉树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。