数据结构＆算法|Day5（三指针描述一颗树）学习|数据结构

一、树的基本概念 1.树的结构

三指针描述一颗树、无序二叉树、有序二叉树、二叉搜索树、完全二叉树、堆、平衡二叉树、23树、B B+、红黑二叉树

2.树的基础概念.

树子树节点
父节点孩子节点爷爷节点叔叔节点兄弟节点
根：树的第一个节点树根
叶子：没有孩子的节点树叶
枝干：不是根也不是叶子枝干
二叉树三叉树四叉树八叉树
叉：允许的最大分支数量
放开三胎之前二叉树
高度层数：几代(最短路径+1)

链表：
nextprev
二叉树：
leftright
三：
p1 p2 p3
四：
p1 p2 p3 p4
族谱：N叉树

二、设计:每个结点3个指针实现无序N叉树的增删改查

3个指针，一个指针指向父节点，一个指针指向兄弟节点，一个指针指向第一个孩子节点。其中兄弟节点指针便是这个设计的关键，它描述清楚了同层关系。

文章图片
如上图所示，具有3个指针的节点便描述清楚了一颗任意叉树的所有关系。

#include using namespace std; //三个指针描述一颗N查树template class MyTree { //树的节点类型 struct Node { Tdata; Node*pParent; Node*pBrother; Node*pChild; }; private: Node*pRoot; //树的成员指向根节点的指针public: MyTree(); ~MyTree(); //创建节点并返回 Node* createNode(const T& data); /* 插入节点到树中 insertData：要插入的节点的数据 findData：要插入的节点想要成为 findData节点的孩子或者兄弟 isBrother： true 成为兄弟 false 成为孩子 */ bool insertNode(const T& findData, const T& insertData, bool isBrother = true); //从树中查找数据为findData的节点找到了返回节点地址，否则返回NULL Node* findNode(const T& findData); //从树中删除第一个数据为delData的节点 bool deleteNode(const T& delData); }; template MyTree::MyTree() {pRoot = NULL; } template MyTree::~MyTree() {}

三、具体代码实现： 1.createNode（memset初始化）

typename MyTree::Node* MyTree::createNode(const T& data) { Node* pNew = new Node; if (NULL == pNew) return NULL; //防呆 memset(pNew, 0, sizeof(Node)); pNew->data = https://www.it610.com/article/data; return pNew; } /*

文章图片

2.findNode 遍历思路：首先设置两个箭头，一个箭头用来向下遍历，一个箭头用来向右遍历，先向右遍历完一层，然后向下遍历一个。

template //从树中查找数据为findData的节点找到了返回节点地址，否则返回NULL typename MyTree::Node* MyTree::findNode(const T& findData) { if (NULL == pRoot) return NULL; Node* pCurrent = pRoot; //当前层 Node* pTemp = NULL; //当前层的当前节点 while (pCurrent) {//层之间切换 pTemp = pCurrent; // while (pTemp) {//当前层往右 if (findData =https://www.it610.com/article/= pTemp->data)return pTemp; pTemp = pTemp->pBrother; }pCurrent = pCurrent->pChild; //层之间切换 } return NULL; }

3.insertNode

自己定规则：(此处仅大儿子有child)
/*Args: 说明
插入节点到树中
insertData：要插入的节点的数据
findData：要插入的节点想要成为 findData节点的孩子或者兄弟
isBrother： true 成为兄弟 false 成为孩子*/

如果树为空：直接成为根节点
如果树不为空：
-成为兄弟(is_brother)：
--找到了：
---本来有兄弟：成为最小兄弟
---本来没兄弟：成为兄弟
--没找到：成为根节点的最小兄弟
-成为孩子(is_child)：
--找到了：
---本来有孩子：成为最小孩子
---本来没孩子：成为孩子
--没找到：成为根节点的最小孩子

template bool MyTree::insertNode(const T& findData, const T& insertData, bool isBrother) { Node* pNew = createNode(insertData); if (NULL == pNew) return false; if (NULL == pRoot){//如果树为空：直接成为根节点 pRoot = pNew; return true; } Node* pInsert = findNode(findData); Node* pTemp = NULL; if (isBrother) {//成为兄弟： if (pInsert) {//找到了： cout << "找到了" << endl; //找到pInsert的最小兄弟 pTemp = pInsert; while (pTemp->pBrother) {//pTemp指向根节点的最后一个兄弟 pTemp = pTemp->pBrother; } //插入 pTemp->pBrother = pNew; pNew->pParent = pTemp->pParent; } else {//没找到//成为根节点的最小兄弟 pTemp = pRoot; //让pTemp指向根节点 while (pTemp->pBrother) {//pTemp指向根节点的最后一个兄弟 pTemp = pTemp->pBrother; } //新节点给pTemp的pBrother赋值 pTemp->pBrother = pNew; } } else {//成为孩子： if (pInsert) {//找到了： cout << "找到了" << endl; //找到pInsert的最小孩子 pTemp = pInsert; while (pTemp->pChild) { pTemp = pTemp->pChild; } //插入 pTemp->pChild = pNew; pNew->pParent = pTemp; } else {//没找到 //成为根节点的最小孩子 pTemp = pRoot; //让pTemp指向根节点 while (pTemp->pChild) {//pTemp指向根节点的最后一个孩子 pTemp = pTemp->pChild; } //新节点给pTemp的pChild赋值 pTemp->pChild = pNew; } } return true; }

4.deleteNode

函数功能：删除树中某个节点，删除成功，返回true，否则返回false
实现思路(规则)：先findNode找结点，找不到false
若结点是pRoot：
若pRoot有兄弟：
①兄弟成为pRoot+②原来的大儿子pchild给兄弟领养+③循环重置大儿子及其兄弟的pParent结点至新父节点(更新pParent)
【数据结构＆算法|Day5（三指针描述一颗树）】若pRoot没有兄弟：
①大儿子pChild成为根节点+②循环重置大儿子及其兄弟的pParent的指针（更新pParent）
若结点不是pRoot(删枝干or叶子)：
若delNode不是大儿子：
得到delNode的父节点->得大儿子结点并循环遍历本层至delNode的前一结点->删除delete即可。
若delNode是大儿子：
若delNode还有兄弟：
①让其第一个兄弟成为大儿子(pChild)+②delNode的儿子给兄弟领养+
③领养完之后，重置儿子们的pParent指针。
若delNode没有兄弟：
①delNode的孩子全部给父节点pParent领养+②循环重置孩子的pParent结点

template //从树中删除第一个数据为delData的节点 bool MyTree::deleteNode(const T& delData) { Node* pDel = findNode(delData); if (NULL == pDel) { return false; } Node* pTemp = NULL; if (pDel == pRoot) {//要删的节点是根节点 if (pDel->pBrother) {//有兄弟 //兄弟成为根 pRoot = pDel->pBrother; //pDel的孩子成为新的根节点的孩子 pTemp = pDel->pChild; pRoot->pChild = pTemp; //上指向下 while (pTemp) {//下指向上 pTemp->pParent = pRoot; pTemp = pTemp->pBrother; } } else {//没有兄弟 pRoot = pDel->pChild; pTemp = pDel->pChild; while (pTemp) {//下指向上 pTemp->pParent = NULL; //parent置为NULL pTemp = pTemp->pBrother; } } delete pDel; return true; } //删枝干或者叶子 Node* pFather = pDel->pParent; if (pDel != pFather->pChild) {//要删的节点不是其父节点的孩子 //找到pDel的前一个节点 pTemp = pFather->pChild; while (pTemp->pBrother != pDel)//让pTemp指向pDel的前一个节点 pTemp = pTemp->pBrother; pTemp->pBrother = pDel->pBrother; delete pDel; return true; } //要删的节点是其父节点的孩子 if (pDel->pBrother) {//有兄弟 //pDel的第一个兄弟成为它的父节点的孩子 pFather->pChild = pDel->pBrother; pDel->pBrother->pChild = pDel->pChild; //pDel的孩子成为 pDel->pBrother 的孩子 pTemp = pDel->pChild; while (pTemp) {//把自己的孩子全部给兄弟进行领养 pTemp->pParent = pDel->pBrother; pTemp = pTemp->pBrother; } } else {//没有兄弟 //pDel的孩子成为它的父节点的孩子(由父亲领养) pFather->pChild = pDel->pChild; //pDel的孩子们成为 pFather 的孩子 pTemp = pDel->pChild; while (pTemp) { pTemp->pParent = pFather; pTemp = pTemp->pBrother; } } delete pDel; return true; }