二叉树结构，三指针描述一棵树

树结构初识，三指针描述一棵树

文章目录

树结构初识，三指针描述一棵树

1. 三指针树

树    子树    节点

父节点孩子节点兄弟节点
二叉树结构，三指针描述一棵树

2. 三指针描述一棵树

2.1 三指针树节点类型

链表构成的树结构由三个指针来描述

每个节点类型都具有父亲节点，兄弟节点与孩子节点来表示他们在树中的位置
```
template <class T>
struct Node
{
	T	data;
	Node<T>* pParent;	//父亲
	Node<T>* pBrother;	//兄弟
	Node<T>* pChild;	//孩子
};
```
树类

对于一个类，他具有类的结构，构造函数析构函数，当然这对于树来说无关紧要，类具有私有成员 pRoot来描述树的根节点
2.2 查找树节点：
- 在插入树的时候，必须先要找到你所要插入的节点应该位于树的什么位置，首先要根据pFindData来定位你想要把InsertData插入到树的什么位置?
  
  例如，这是一个三指针树结构:
  
  查找示例：
  - 插入节点 2，规定2是1的孩子节点 : 首先要找到节点1 ，根据1 来确定2是1的孩子节点
  - 再来插入节点3 ，规定3是2的兄弟节点: 所以我们就要找到节点2，根据2来确定3是2的兄弟节点
  - 再来插入节点 4，规定4是3的兄弟节点: 同理，找到3来确定4是3的兄弟
  - 再来插入节点5，规定5是2的孩子节点: 同理，根据2来确定2是5的孩子
  - 再来插入一个6，但是规定6是0的兄弟节点，但是0不在树中，查找不到，则规定6自动成为根节点的兄弟节点
  - 再来插入一个7，但是规定7是0的孩子节点，但是0不在树中，查找不到，则规定7自动成为根节点的最小孩子节点
  - 同理，可知，当我们想要插入一个节点时，必须要规定它跟哪一个节点是什么关系（三指针的树结构，其他树不讨论）
  - 当我们想要让一个节点成为一个节点的兄弟，则查找到某一行（横着的）的节点
  - 当我们想要让一个节点成为一个节点的孩子，则查找到某一列（竖着的）的节点
  - 没有查找到的，自动成为根节点的孩子或者兄弟
- 查找代码如下:
```
//查找树节点
	Node<T>* Find_Node(const T& Finddata);
```
```
template<class T>
inline Node<T>* New_Tree<T>::Find_Node(const T& Finddata)
{
	if (pRoot == nullptr)
	{
		return nullptr;
	}
	Node<T>* pCur = pRoot;
	Node<T>* pTemp = nullptr;
    //从根节点开始查找
	while (pCur)
	{
		pTemp = pCur;
		while (pTemp)
		{
            //在某个地方找到了FindData的数据，则返回这个节点位置，
            //例如上图，插入2找1，插入3找2，插入4找3，插入5找2
			if (pTemp->data == Finddata)
			{

				return pTemp;
			}
            //把每个节点的兄弟作为列
			pTemp = pTemp->pBrother;
		}
        //把每个节点的孩子作为行
		pCur = pCur->pChild;
	}
	//没找到则返回空
	return nullptr;
}
```
2.3 插入树节点
1. 创建树的节点
```
//创建节点
Node<T>* Create_Node(const T& data);
```
  数据等于data，三个指针初始化为nullptr
```
template<class T>
inline Node<T>* New_Tree<T>::Create_Node(const T& data)
{
	Node<T>* pNew = new Node<T>;
	if (pNew == nullptr)
	{
		return nullptr;
	}
    //快捷初始化为空
	memset(pNew, 0, sizeof(Node<T>));
	pNew->data = data;
	return pNew;
}
```
2. 树的插入节点
  
  InsertData表示要插入的数据
  
  FindData表示要插入的节点想要成为 FindData节点的孩子或者兄弟
  
  isBrother表示要插入的节点的类型，属于兄弟还是孩子，设置兄弟节点为默认节点，函数的缺省。则自动成为兄弟节点
```
    //插入树节点
     void push(const T& Insertdata, const T& Finddata, bool isBrother)
```
  2.3.1 树的插入位置选择:（伪代码）
  - 根节点：（即插入的第一个节点）
  - 要插入一个兄弟节点：pFind查找要插入的前一个位置
    - pFind有效
      - 有原始的兄弟节点，成为最小兄弟节点
      - 没有原始兄弟，成为第一个兄弟
    - pFind无效（nullptr）例如上述 FindData=0
      - 没找到pFind，自动成为根节点的最小兄弟
  - 要插入一个孩子节点：pFind查找要插入的前一个位置
    - pFind有效
      - 有原始的孩子节点，成为最小孩子节点
      - 没有原始孩子，成为第一个孩子
    - pFind无效（nullptr）例如上述 FindData=0
      - 没找到pFind，自动成为根节点的最小孩子
  - 注意: 插入兄弟节点时，不一定非要选择相邻的位置，比如，你要在插入4当作3的兄弟（如上图），那么FindData不一定为3，也可以选择2，只要是同为兄弟节点，在同一行，都可以正确的插入，原因是都是插入到这一行的最小兄弟，所以肯定要有一个临时变量控制移动到最小兄弟处，然后再pTemp的兄弟指向pNew
插入为孩子节点时，也有一个临时变量，终究是移动到最小孩子处，所以FindData只要是同为孩子节点，即这一列的元素即可，pTemp移动到最小孩子，pTemp的孩子指向pNew

注意插入完成后，新插入的节点的父亲的关系的更新，新插入兄弟节点，则其父亲指向亲儿子的父亲节点，例如3，4的父亲和2一样为1；新插入孩子节点，则其父亲为其上一个节点，2的父亲为1，5的父亲为2；根节点的和其兄弟没有父亲nullptr

2.3.2 插入树代码示例

    template<class T>
       inline void New_Tree<T>::push(const T& Insertdata, const T& Finddata, bool isbrother)
       {
       	Node<T>* pNew = Create_Node(Insertdata);
       	if (pNew == nullptr)
       	{
       		cout << "节点创建失败!\n";
       		return;
       	}
       
       	//如果树为空
       	if (pRoot == nullptr)
       	{
       		pRoot = pNew;
       		return;
       	}
       	//查找要插入的节点在什么位置
       	Node<T>* pFind = Find_Node(Finddata);
       	Node<T>* pTemp = nullptr;
       	//要插入兄弟节点
       	if (isbrother)
       	{
       		//如果有原始兄弟节点
       		if (pFind)
       		{
       			//1. 找到pFind的最小兄弟节点
       			pTemp = pFind;
       			while (pTemp->pBrother)
       			{
       				pTemp = pTemp->pBrother;
       			}
       			//2. pNew插入到最小兄弟位置
       			pTemp->pBrother = pNew;
       			//3. pNew的父节点更新
       			pNew->pParent = pTemp->pParent;
       		}
       		else
       		{
       			//如果没有兄弟节点  直接成为根节点的兄弟
       			pTemp = pRoot;
       			while (pTemp->pBrother)
       			{
       				pTemp = pTemp->pBrother;
       			}
       			pTemp->pBrother = pNew;
       		}
       	}
       	else //要插入孩子节点  
       	{
       		//原始有孩子节点
       		if (pFind)
       		{
       			//1. 成为pFind的最小孩子节点
       			pTemp = pFind;
       			while (pTemp->pChild)
       			{
       				pTemp = pTemp->pChild;
       			}
       			pTemp->pChild = pNew;
       			pNew->pParent = pTemp;
       		}
       		else
       		{
       			//没有孩子节点，成为根节点的最小孩子
       			pTemp = pRoot;
       			while (pTemp->pChild)
       			{
       				pTemp = pTemp->pChild;
       			}
      			pTemp->pChild = pNew;
         		}
         	}
         }

2.4 树的删除节点

2.4.1 删除情况列举
1. 删除带兄弟的根节点，如删除1 ，pDel指向1节点，则让其亲兄弟节点变为根节点，亲兄弟节点的孩子节点指向pDel的亲孩子节点，同时要注意pDel的亲儿子的兄弟节点的父亲也要及时更新为新的根节点（20 节点）
1. 删除不带兄弟节点的根节点，删除根节点1，让其亲儿子的节点成为根节点，包括其自身及兄弟节点的父亲指向nullptr；
2. 删除兄弟节点: 删除亲儿子类型的兄弟节点，如删除3，则需要找到其父亲节点，并且判断其父亲节点的亲儿子节点不是pDel，否则可能会出现删除5的情况（如d情况）。让其父亲节点的亲儿子到达pDel的前一个节点（因为他们都是同一行的兄弟），跳跃删除
3. 删除兄弟节点: 删除根节点的兄弟节点，删除20，找到pDel的前一个节点，跳跃删除，同时注意pDel有没有孩子节点，其孩子节点成为其下一个兄弟的亲儿子节点，（不允许其孩子节点又有兄弟节点的情况出现）
4. 删除亲儿子类型节点（带兄弟），找到其父节点（注意区别情况c ），父节点的孩子节点成为pDel的第一个兄弟节点，pDel的孩子节点成为pDel的亲兄弟的孩子，同时pDel的孩子的兄弟节点父亲关系转变（pDel第一个兄弟）（如果有兄弟的话）
5. 删除亲儿子类型节点（不带兄弟），注意区别与上面的情况，没有兄弟，则直接更新孩子，同时还要注意孩子有没有兄弟，有的话父亲关系转变
2.4.2 删除代码

//删除树节点
void pop(const T& Deldata);

template<class T>
inline void New_Tree<T>::pop(const T& Deldata)
{
	Node<T>* pDel = Find_Node(Deldata);
	if (pDel == nullptr)
	{
		cout << "未找到此节点，删除失败\n";
		return;
	}

	Node<T>* pTemp = nullptr;
	//删除根节点
	if (pDel == pRoot)
	{
		//根节点有兄弟节点   情况 1
		if (pDel->pBrother)
		{
			pTemp = pDel->pChild;
			//1. 根的第一个兄弟成为新的根
			pRoot = pDel->pBrother;
			//2. pDel的儿子们成为新的根的儿子
			pRoot->pChild = pTemp;
			//3. pDel的儿子们的pParent指向新的父亲
			while (pTemp)
			{
				pTemp->pParent = pRoot;
				pTemp = pTemp->pBrother;
			}
		}
		else //根节点没有兄弟节点   情况 2
		{
			//1. 直接删除pRoot 并让它的孩子们指向空
			pRoot = pDel->pChild;
			pTemp = pDel->pChild;
			while (pTemp)
			{
				pTemp->pParent = nullptr;
				pTemp = pTemp->pBrother;
			}
		}
		delete pDel;
		return;
	}

	/*
	删除非根节点
	*/

	//横着有兄弟
	//1. 要删除的是根节点的兄弟  情况 4
	Node<T>* pFather = pDel->pParent;
	if (pDel->pParent == nullptr)
	{
		pTemp = pRoot;
		while (pTemp->pBrother != pDel)
		{
			pTemp = pTemp->pBrother;
		}
		pTemp->pBrother = pDel->pBrother;
		//节点有孩子 
		if (pDel->pChild)
		{
			pTemp = pRoot;
			//pDel的孩子成为pDel的最小兄弟的孩子
			while (pTemp->pBrother)
			{
				pTemp = pTemp->pBrother;
			}	//移动到最小兄弟
			pTemp->pChild = pDel->pChild;
			pDel->pChild->pParent = pTemp;
		}
		delete pDel;
		return;
	}
	//2. 要删除的是叶子节点的兄弟  情况 3
	if (pFather->pChild != pDel)
	{
		pTemp = pFather->pChild;
		while (pTemp->pBrother != pDel)
		{
			pTemp = pTemp->pBrother;
		}
		pTemp->pBrother = pDel->pBrother;
		delete pDel;
		return;
	}
	/*
	竖着的情况
	*/
	//竖着有兄弟   情况 5
	if (pDel->pBrother)
	{
		//1. pDel的第一个兄弟成为pFather的亲儿子
		pFather->pChild = pDel->pBrother;
		//2. pDel的儿子们成为pDel的亲兄弟的儿子
		pDel->pBrother->pChild = pDel->pChild;
		pTemp = pDel->pChild;
		//3. pDel的儿子们与pDel的亲兄弟确认父子关系
		while (pTemp)
		{
			pTemp->pParent = pDel->pBrother;
			pTemp = pTemp->pBrother;
		}
	}
	//竖着没兄弟	  情况 6
	else
	{
		//1. pDel的亲儿子成为pFather的亲儿子
		pFather->pChild = pDel->pChild;
		//2. pDel的亲儿子如果有兄弟们，则成为pFather的孩子
		pTemp = pDel->pChild;
		while (pTemp)
		{
			pTemp->pParent = pFather;
			pTemp = pTemp->pBrother;
		}
	}
	delete pDel;
	return;
}

3. 测试

树的遍历就不写了，可以通过加断点调试来观察树的结构

#include "Tree.h"
#include "My_Tree.h"
int main()
{
#if 1
	New_Tree<int> a;
	a.push(1, 0);
	a.push(2, 1, false);
	a.push(3, 2);
	a.push(33, 3,false);
	a.push(4, 3);
	a.push(5, 2, false);
	a.push(6, 5);
	a.push(7, 5,false);
	a.push(8, 7);
	a.push(9, 7);
	a.push(10, 7);
	a.push(11, 7,false);
	a.push(12, 5, false);
	a.push(13, 12);
	a.push(14, 13);
	a.pop(1);
	a.pop(3);
	a.pop(8);
	a.pop(12);
#endif
	return 0;
}

二叉树结构，三指针描述一棵树

三指针树是树结构的基础，尽管三指针没什么用，但是用它来锻炼思维还是不错的，方便以后的二叉树的学习

源代码下载: ~~

这里是本篇文章的源代码下载连接，大家也可以多多关注我的guthub，记录我的编程学习，共同进步！

秒客网

二叉树结构，三指针描述一棵树

文章目录

1. 三指针树

2. 三指针描述一棵树

2.1 三指针树节点类型

2.2 查找树节点：

2.3 插入树节点

2.3.1 树的插入位置选择:（伪代码）

2.3.2 插入树代码示例

2.4 树的删除节点

2.4.1 删除情况列举

2.4.2 删除代码

3. 测试

相关文章