手撕数据结构与算法——树(三指针描述一棵树）

?作者介绍：22级树莓人（计算机专业），热爱编程＜目前在c＋＋阶段，因为最近参加新星计划算法赛道(白佬)，所以加快了脚步，果然急迫感会增加动力>——目标Windows，MySQL，Qt，数据结构与算法，Linux，多线程，会持续分享学习成果和小项目的
?作者主页：king&南星
?专栏链接：数据结构

?欢迎各位→点赞? + 收藏? + 留言?​
?总结：希望你看完之后，能对你有所帮助，不足请指正！共同学习交流 ?

?文章目录

?树一、?概念与定义二、?定义与预备三、?创建结点函数四、?查找五、?插入六、?遍历

?树

一、?概念与定义

描述树结构：

和现实世界的树 反着画根节点 枝干 叶子节点同一层 兄弟 上层：父 叔叔 上层的上层：爷爷
下层：孩子 侄儿树的高度：几代人树退化成线性结构 ： 一叉树(链表) N代单传
图解：
现实中的树

数据结构中的树是和现实倒着的

详细解读：三个指针描述，一个指针指向父亲，一个指针指向兄弟，一个指针指向孩子，同时规则设定只有父亲的第一个孩子才可以有孩子

二、?定义与预备

先准备好头文件、结构体和函数声明

#define _CRT_SECURE_NO_WARNINGS 1#include<stdio.h>#include<stdlib.h>#include<stdbool.h>#include<assert.h>typedef struct treeNode{int data;                  //数据struct treeNode* pParent;  //指向父struct treeNode* pBrother; //指向第一个兄弟struct treeNode* pChild;   //指向第一个孩子}treeNode;#define SIZE sizeof(treeNode)//创建节点函数treeNode* createNode(int data);//在树中找一个节点，找到返回这个节点的地址，找不到返回NULLtreeNode* findNode( treeNode* root, int findData);//插入一个节点到树中//把insertData插入到*pRoot树中 如果isChild为真成为findData节点的孩子，否则成为findData节点的兄弟bool intsertNode( treeNode** pRoot, int findData, int insertData, bool isChild);//遍历void print_Tree(treeNode* root);

三、?创建结点函数

这里利用一个技巧，直接使用内存设置函数memset函数，把三个指针内存都设置为0

treeNode* createNode( int data ){treeNode* newNode = (treeNode*)malloc(SIZE);assert(newNode);memset(newNode, 0, SIZE);//内存都设置为0newNode->data = data;return newNode;}

四、?查找

在树中找一个节点，找到返回这个节点的地址，找不到返回NULL
先在while循环中遍历同一层的兄弟，直到他下一个兄弟为空，切换到下一层，如此循环下去，如果找到则返回地址，如果没找到则返回空

treeNode* findNode(treeNode* root, int findData) {if (NULL == root) return NULL;  //防呆treeNode* pTemp;treeNode* pnextChild = root;while (true){pTemp = pnextChild;if (NULL == pnextChild) break;while( true ){//遍历兄弟层if (NULL == pTemp) break;if (findData == pTemp->data) return pTemp;pTemp = pTemp->pBrother;}//切换到下一层(孩子)pnextChild = pnextChild->pChild;}return NULL;}

五、?插入

描述：插入一个节点到树中，把insertData插入到*pRoot树中 如果isChild为真成为findData节点的孩子，否则成为findData节点的兄弟

bool intsertNode(treeNode** pRoot, int findData, int insertData, bool isChild){if (NULL == pRoot) return false; //防呆if (NULL == *pRoot) //空树{*pRoot = createNode(insertData);return true;}treeNode* pFind = findNode(*pRoot, findData);  //查找if (NULL == pFind) return false;treeNode* pNew, * pTemp;//找到了if (isChild) //新节点成为pFind指向节点的孩子{//有孩子，新节点成为pFind节点孩子的最小兄弟if (pFind->pChild){pTemp = pFind->pChild;pNew = createNode(insertData);while (pTemp->pBrother) pTemp = pTemp->pBrother;pTemp->pBrother = pNew;pNew->pParent = pFind;return true;}//pFind指向的节点没有孩子else{//有父，pFind不是根节点if (pFind->pParent){//pFind是pFind->pPartent的第一个孩子if (pFind->pParent->pChild == pFind){pNew = createNode(insertData);pFind->pChild = pNew;pNew->pParent = pFind;return true;}else{//pFind不是pFind->pParent的第一个孩子//新节点只能成为 pFind->pParent->pChild的孩子intsertNode(&(pFind->pParent), pFind->pParent->pChild->data, insertData, true);}}//无父，pFind是根节点else{pNew = createNode(insertData);pFind->pChild = pNew;pNew->pParent = pFind;return true;}}}else //新节点成为pFind指向节点的兄弟{pTemp = pFind;while (pTemp->pBrother) pTemp = pTemp->pBrother;pNew = createNode(insertData);pTemp->pBrother = pNew;pNew->pParent = pFind->pParent;return true;}return false;}

六、?遍历

和查找函数异曲同工

void print_Tree(treeNode* root) {if (NULL == root) return NULL;  //防呆treeNode* pTemp;treeNode* pnextChild = root;int cnt = 1;while (true){pTemp = pnextChild;if (NULL == pnextChild) break;printf("第[%d]层：", cnt++);while (true){//遍历兄弟层if (NULL == pTemp) break;printf("%d ", pTemp->data);pTemp = pTemp->pBrother;}printf("\n");//切换到下一层(孩子)pnextChild = pnextChild->pChild;}}