数据结构之一对多，树“

树:

定义:一个树至多有一个根节点,每一个路径的终端都叫终端节点,也叫叶子结点。既不是根也不是叶子节点叫中间节点,节点与节点连接的线叫边。从底下往上看叫高度,从上往低看叫深度。
PS:树整体高度和深度取最大值。
度:看当前节点有n个子节点就叫n度。

二叉树(Binary Tree)

定义:树里的每个节点至多允许有两个节点。

满二叉树

定义:每一层都是满节点(2个节点)除最后一层的二叉树。

完全二叉树

定义:只允许最后一层有空缺,且空缺的方式从右向左的二叉树。
ps:满二叉树是完全二叉树的一种特殊形势。

平衡二叉树

定义:树中任意节点,左右子树高度差不超过1。
ps:完全二叉树一定是平衡二叉树。

排序二叉树

定义:左孩子的值比父亲小,右节点的值比父节点的大。

二叉树的性质

• $k$层满二叉树,叶子节点的个数是$ 2^{k-1} $
• $k$层满二叉树,总节点个数为$2^{k}-1$
• 对于任意一个二叉树而言,度为0的节点比度为2的节点少一个。($n_0=n_2+1$),PS:对于一个完全二叉树而言,度为1的节点至多有一个。
• 一个有$n$个节点的完全二叉树,它的深度是$ K=\lfloor log2^{n}\rfloor +1$(向下取整) 例如:3.33 取3
• 对一个有$n$个节点的完全二叉树,按照从上到下,从左到右的顺序从1开始,开始编号,

1. $i=1$时是根节点。
2. $2i<=n $ ,$i$有左子树,否则没有。
3. $2i+1<=n$时,$i$有右子树,否则没有。

• 从$1$ ~ $\displaystyle\frac{n}2 $之间的节点都是父节点,$\displaystyle\frac{n}2 $都是向下取整。

  二叉树的遍历

• 深度（递归版）

1. 前序遍历:根左右
2. 中序遍历:左根右
3. 后序遍历:左右根

• 广度遍历(层序遍历):从上到下,从左到右

  #include<stdio.h>
  #include<stdlib.h>
  typedef struct Node
  {
  	int nValue;
  	struct Node *pLeft;
  	struct Node *pRight;
  
  }BinaryTree;
  typedef struct node3
  {
  BinaryTree *nValue;
  struct node3 *pNext;
  }MyQueue;
  
  typedef struct node4
  {
  int nCount;
  MyQueue* pHead;
  MyQueue *pTail;
  }Queue;
  BinaryTree * CreateTree();
  void RecPreOrderTraversal(BinaryTree *pRoot)
  {
  	if(pRoot == NULL)return;
  	//前序遍历 根左右
  	printf("%d ",pRoot->nValue);
  	RecPreOrderTraversal(pRoot->pLeft);
  	RecPreOrderTraversal(pRoot->pRight);
  }
  void RecInOrderTraversal(BinaryTree *pRoot)
  {
  	if(pRoot == NULL)return;
  	//中序遍历 左根右
  	RecInOrderTraversal(pRoot->pLeft);
  	printf("%d ",pRoot->nValue);
  	RecInOrderTraversal(pRoot->pRight);
  }
  void RecLastOrderTraversal(BinaryTree *pRoot)
  {
  	if(pRoot == NULL)return;
  	//后序遍历 左右根
  	RecLastOrderTraversal(pRoot->pLeft);
  	RecLastOrderTraversal(pRoot->pRight);
  	printf("%d ",pRoot->nValue);
  }
  void q_Init(Queue **pQueue)
  {
  	if(pQueue == NULL)return;
  	*pQueue = (Queue*)malloc(sizeof(Queue));
  	(*pQueue)->nCount = 0;
  	(*pQueue)->pHead = NULL;
  	(*pQueue)->pTail = NULL;
  }
  
  void q_Push(Queue *pQueue,BinaryTree *nNum)
  {
  	MyQueue *pTemp = NULL;
  	if(pQueue == NULL)return;
  
  	pTemp = (MyQueue*)malloc(sizeof(MyQueue));
  	pTemp->nValue = nNum;
  	pTemp->pNext = NULL;
  
  	if(pQueue->pHead == NULL)
  	{
  	pQueue->pHead = pTemp;
  	}
  	else
  	{
  	pQueue->pTail->pNext = pTemp;
  	}
  
  	pQueue->pTail = pTemp;
  	pQueue->nCount++;
  
  }
  BinaryTree* q_Pop(Queue *pQueue)
  {
  	MyQueue *pDel = NULL;
  	BinaryTree  *Temp = NULL;
  	if(pQueue == NULL || pQueue->pHead == NULL)return NULL;
  
  	pDel = pQueue->pHead;
  	Temp = pDel->nValue;
  
  	pQueue->pHead = pQueue->pHead->pNext;
  	free(pDel);
  	pDel = NULL;
  	pQueue->nCount--;
  
  	if(pQueue->nCount == 0)
  	{
  	pQueue->pTail = NULL;
  	}
  
  	return Temp;
  }
  
  int q_IsEmpty(Queue *pQueue)
  {
  	if(pQueue == NULL )return -1;
  	return pQueue->nCount ? 0:1;
  }
  void EveryTravelsalTree(BinaryTree *Tree)
  {
  	//层序遍历
  	Queue *M_Queue = NULL;
  	BinaryTree *Temp = NULL;
  	if(Tree == NULL)return;
  	q_Init(&M_Queue);
  	q_Push(M_Queue,Tree);
  	while(!q_IsEmpty(M_Queue))
  	{
  		Temp = q_Pop(M_Queue);
  		printf("%d ",Temp->nValue);
  		if(Temp->pLeft != NULL)
  		{
  			q_Push(M_Queue,Temp->pLeft);
  		}
  		if (Temp->pRight != NULL)
  		{
  			q_Push(M_Queue,Temp->pRight);
  		}	
  	}
  }

例二叉树

前序:X Y F X R B K G D
中序:X B R Y Z F D G K
后序:X Y F Z R B K G D

二叉树的创建

手动创建二叉树,最慢最基础零技术的创建方法

#include<stdio.h>
#include<stdlib.h>
typedef struct Node
{
	int nValue;
	struct Node *pLeft;
	struct Node *pRight;

}BinaryTree;
BinaryTree * CreateTree()
{
	BinaryTree *pRoot = NULL;
	pRoot = (BinaryTree*)malloc(sizeof(BinaryTree));
	pRoot ->nValue = 1;
	//根的左2
	pRoot->pLeft = (BinaryTree*)malloc(sizeof(BinaryTree));
	pRoot->pLeft->nValue = 2;
	//左的左4
	pRoot->pLeft->pLeft = (BinaryTree*)malloc(sizeof(BinaryTree));
	pRoot->pLeft->pLeft->nValue = 4;
	pRoot->pLeft->pLeft->pLeft = NULL;
	pRoot->pLeft->pLeft->pRight = NULL;
	//左的右5
	pRoot->pLeft->pRight = (BinaryTree*)malloc(sizeof(BinaryTree));
	pRoot->pLeft->pRight->nValue = 5;
	pRoot->pLeft->pRight->pLeft = NULL;
	pRoot->pLeft->pRight->pRight = NULL;
	//根的右3
	pRoot->pRight = (BinaryTree*)malloc(sizeof(BinaryTree));
	pRoot->pRight->nValue = 3;
	pRoot->pRight->pRight = NULL;
	//右的左6
	pRoot->pRight->pLeft = (BinaryTree*)malloc(sizeof(BinaryTree));
	pRoot->pRight->pLeft->nValue = 6;
	pRoot->pRight->pLeft->pLeft = NULL;
	pRoot->pRight->pLeft->pRight = NULL;
	return pRoot;
}

递归创建二叉树(反序列创建二叉树)

根据层序遍历特点来创建二叉树

void DynamicRecPreOrder(BinaryTree **Temp)
{
	//前序动态创建二叉树,叫递归创建二叉树或者反序列化创建二叉树
	int j;
	scanf_s("%d",&j);	
	if(Temp==NULL)return;
	if(j == 0)return;
	*Temp = (BinaryTree*)malloc(sizeof(BinaryTree));
	(*Temp)->nValue = j;
	(*Temp)->pLeft = NULL;
	(*Temp)->pRight = NULL;
	DynamicRecPreOrder(&((*Temp)->pLeft));
	DynamicRecPreOrder(&((*Temp)->pRight));

	return;
}

动态创建二叉树(用数组的形势)

根据二叉树的性质5

BinaryTree *DynamicArryCreateTree(int Temp[],int Num)
{
	BinaryTree *Templ = NULL;
	int i = 0;
	int m = 0;
	Templ = (BinaryTree*)malloc(sizeof(BinaryTree)*Num);
	for(;i<Num;i++)
	{
		Templ[i].nValue = Temp[i];
		Templ[i].pLeft = NULL;
		Templ[i].pRight = NULL;
	}
	for (m = 0; m <= (Num/2) - 1 ; m++)
	{
		if(2*m+1<Num)
		{
		Templ[m].pLeft = &Templ[2*m+1];
		}
		if(2*m+2<Num)
		{
		Templ[m].pRight = &Templ[2*m+2];
		}
	}

		return Templ;
}

二叉树的循环高级遍历（非递归）

叙述流程

1. 申请栈stack
2. 检验参数
3. (前序:打印节点)节点入栈
4. 判断节点是否有左
   • 有,重复3 4
   • 没有,下一步(中序:打印节点)
5. 栈顶弹出,弹出栈顶是否为空
   • 是,结束
   • 无,重复5
6. 判断弹出节点是否有右
   • 有,把右变成当前节点,之后重复3 4
   • 无,重复5

用循环实现前序遍历

void OnRecTraversal(BinaryTree* Temp)
{
	Stack *m_Stack = NULL;
	if(Temp == NULL)return;
	s_Init(&m_Stack);
	while(1)
	{
		while (Temp)
		{
			printf("%d\n",Temp->nValue);
			s_Push(m_Stack,Temp);
			Temp = Temp->pLeft;
		}
		//栈顶弹出
		Temp = s_Pop(m_Stack);
		//判断节点是否为空
		if(Temp == NULL)return;
		//向右处理
		Temp = Temp->pRight;
	}
}

用循环实现中序遍历

void MidTraversal(BinaryTree* Temp)
{
	Stack *m_Stack = NULL;
	if(Temp == NULL)return;
	s_Init(&m_Stack);
	while(1)
	{
		while (Temp)
		{
			s_Push(m_Stack,Temp);
			Temp = Temp->pLeft;
		}
		//栈顶弹出
		Temp = s_Pop(m_Stack);
		//判断节点是否为空
		if(Temp == NULL)return;
		printf("%d\n",Temp->nValue);
		//向右处理
		Temp = Temp->pRight;
	}
}

用循环实现后序遍历

void RecLastOrderTraversal(BinaryTree* Temp)
{
	Stack *m_Stack = NULL;
	BinaryTree* pTemp = 0;
	if(Temp == NULL)return;
	s_Init(&m_Stack);
	while(1)
	{	
		while (Temp)
		{		
			s_Push(m_Stack,Temp);
			Temp = Temp->pLeft;
		}
		if(m_Stack->pTop == NULL)return;
		if(m_Stack->pTop->nValue->pRight == NULL||m_Stack->pTop->nValue->pRight == pTemp)
		{
			pTemp = s_Pop(m_Stack);
			printf("%d\n",pTemp->nValue);
		}else
		{
			Temp = m_Stack->pTop->nValue->pRight;
		}
	}
	return;
}

在二叉树中插入一个结点

首先先写一个查找的API

在一个二叉树中查找一个结点

BinaryTree * Chop(BinaryTree *pRoot,int nNum)
{
	Queue *pQueue = NULL;
	BinaryTree *pTemp = NULL;
	if(pRoot == NULL)return NULL;
	
	q_Init(&pQueue);

	//根入队
	q_Push(pQueue,pRoot);

	while(!q_IsEmpty(pQueue))
	{
		pTemp = q_Pop(pQueue);
		
		if(pTemp->nValue == nNum)
		{
			//记得清空队列
			return pTemp;
		}

		//左右非空入队
		if(pTemp->pLeft != NULL)
		{
			q_Push(pQueue,pTemp->pLeft);
		}
		if(pTemp->pRight != NULL)
		{
			q_Push(pQueue,pTemp->pRight);
		}
	}
	return NULL;
}

在一个二叉树中插入一个结点,传入方向,值

//传入树，放在那个节点的下面，放入得值，放入的方向
void InsertNode(BinaryTree **pRoot,int nNum,int nValue,int nDirection)
{
	BinaryTree *pNode = NULL;
	BinaryTree *pTemp = NULL;
	if(pRoot == NULL || *pRoot == NULL)return;

	//查找
	pNode = Chop(*pRoot,nNum);

	//检测
	//不存在
	if(pNode == NULL)
	{
		printf("值不存在~~~\n");
		return;
	}

	//存在
	pTemp = (BinaryTree*)malloc(sizeof(BinaryTree));
	pTemp->nValue = nValue;
	pTemp->pLeft = NULL;
	pTemp->pRight = NULL;

	//被插入方向
	if(nDirection == LEFT)
	{
		pTemp->pLeft = pNode->pLeft;
		pNode->pLeft = pTemp;
		return;
	}
	if(nDirection == RIGHT)
	{
		pTemp->pRight = pNode->pRight;
		pNode->pRight = pTemp;
		return;
	}
}

创建一个排序二叉树

创建流程

1. 将值放入结点
2. 检测树是否为空树,若是空结点,则新结点即为根,结束
3. 若树为非空树
   比较结点值大小
   若值比结点值大,则向右子树方向走

• 空树:放入结点

• 非空树:向右走,重复3步骤

  若值比结点值小,则向左子树方向走

  • 空树:放入结点
  • 非空树:向左走,重复3步骤

  值相同的话,违背排序二叉树的步骤,释放新建结点空间,结束

  void InsertNode(BinaryTree **pRoot,int nNum)
  {
  	BinaryTree *pTemp = NULL;
  	BinaryTree *pMark = NULL;
  
  	if(pRoot == NULL)return;
  
  	pTemp = (BinaryTree*)malloc(sizeof(BinaryTree));
  	pTemp->nValue = nNum;
  	pTemp->pLeft = NULL;
  	pTemp->pRight = NULL;
  
  	//空树
  	if(*pRoot == NULL)
  	{
  		*pRoot = pTemp;
  		return;
  	}
  
  	//标记根
  	pMark = *pRoot;
  
  	while(1)
  	{
  		//新来的节点值小
  		if(nNum < pMark->nValue)
  		{
  			//左空
  			if(pMark->pLeft == NULL)
  			{
  				pMark->pLeft = pTemp;
  				return;
  			}
  
  			//非空 向左走
  			pMark = pMark->pLeft;
  		}
  		//新来的节点值大
  		else if(nNum > pMark->nValue)
  		{
  			//右空
  			if(pMark->pRight == NULL)
  			{
  				pMark->pRight = pTemp;
  				return;
  			}
  
  			//非空 向右走
  			pMark = pMark->pRight;
  		}
  
  		//新来值已经存在  违背性质  结束
  		else
  		{
  			free(pTemp);
  			pTemp = NULL;
  			return;
  		}
  	}
  }
  
  
  BinaryTree *CreateSrtTree(int arr[],int nLength)
  {
  	BinaryTree *pRoot = NULL;
  	int i;
  	if(arr == NULL || nLength <=0)return NULL;
  
  	for(i = 0;i<nLength;i++)
  	{
  		InsertNode(&pRoot,arr[i]);
  	}
  	return pRoot;
  }

从排序二叉树中删除一个结点

删除的流程

1. 叶子节点,直接删除
2. 有一个孩子(即只有一个左子树或者右子树),删除当前结点,用孩子代替它
3. 有两个孩子,找到其右的最左或者左的最右的结点,将找到的结点的值覆盖删除结点的值,之后进行步骤1,2

   在一个排序二叉树查找一个结点的代码

   //参数：树，被查找的值，被删除节点的地址，被删除节点的父亲
   void Search(BinaryTree *pTree,int nNum,BinaryTree **pDel,BinaryTree **pDelFather)
   {
   	if(pTree == NULL)return;
   
   	while(pTree)
   	{
   		//找到  记住被删除位置 结束
   		if(pTree->nValue == nNum)
   		{
   			*pDel = pTree;
   			return;
   		}
   
   		//查找的值比当前节点的小 记住被删除节点的父亲 而后向左走
   		else if(pTree->nValue > nNum)
   		{
   			*pDelFather = pTree;
   			pTree = pTree->pLeft;
   		}
   		//查找的值比当前节点的大 记住被删除节点的父亲 而后向右走
   		else
   		{
   			*pDelFather = pTree;
   			pTree = pTree->pRight;
   		}
   	}
   
   	//查找结束 没找到 清空标记删除节点父亲的指针
   	*pDelFather = NULL;
   	return ;
   }

在排序二叉树删除一个节点代码

void DelOneChild(BinaryTree **pRoot, BinaryTree *pDel,BinaryTree *pDelFather)
{
	if(pRoot == NULL)return;

	//被删除节点是根
	if(pDelFather == NULL)
	{
		*pRoot = pDel->pLeft ? pDel->pLeft:pDel->pRight;
		free(pDel);
		pDel = NULL;
		
		return;
	}

	//检测被删除节点是父亲的左还是右
	if(pDel == pDelFather->pLeft)
	{
		//将被删除节点非空的孩子与pdelfather关联 
		pDelFather->pLeft = pDel->pLeft ? pDel->pLeft:pDel->pRight;
		free(pDel);
		pDel = NULL;
		return;
	}
	if(pDel == pDelFather->pRight)
	{
		pDelFather->pRight = pDel->pLeft ? pDel->pLeft:pDel->pRight;
		free(pDel);
		pDel = NULL;
		return;
	}

}

void DelNode(BinaryTree **pTree,int nNum)
{
	BinaryTree *pDel = NULL;
	BinaryTree *pDelFather = NULL;
	BinaryTree *pMark =NULL;
	if(pTree == NULL || *pTree == NULL)return;

	//查找
	Search(*pTree,nNum,&pDel,&pDelFather);

	//没找到
	if(pDel == NULL)return;

	//找到
	//有两个孩子 向右找最小的
	if(pDel->pLeft!= NULL && pDel->pRight != NULL)
	{
		pMark = pDel;

		//移动到右
		pDelFather = pDel;
		pDel = pDel->pRight;

		//找右的最左
		while(pDel->pLeft)
		{
			pDelFather = pDel;
			pDel = pDel->pLeft;
		}

		//值覆盖
		pMark->nValue = pDel->nValue;
	}

	//删除有一个孩子的或者没孩子的
	DelOneChild(pTree,pDel,pDelFather);

}

排序二叉树转换成一个排序双向链表

流程

1. 根据中序遍历特点,左根右
2. 将二叉树左看成链表的上指针,将二叉树的右看链表的下指针.
3. 在中序遍历输出的位置,将二叉树变成链表式连接

   代码

   void SortTreeToList(BinaryTree *pRoot, BinaryTree **pHead,BinaryTree **pTail)
   {
   	if(pRoot == NULL)return;
   	if(pHead == NULL || pTail == NULL)return;
   
   	//找到左侧
   	SortTreeToList(pRoot->pLeft,pHead,pTail);
   
   	//尾添加节点
   	if(*pHead == NULL)
   	{
   		*pHead = pRoot;
   	}
   	else
   	{
   		//双向指向关联
   		//left = 上一个pre
   		//right = 下一个next
   		(*pTail)->pRight = pRoot;
   		pRoot->pLeft = *pTail;
   	}
   	*pTail = pRoot;
   
   	//找到右侧
   	SortTreeToList(pRoot->pRight,pHead,pTail);
   }

平衡二叉树的两种旋转

普通二叉树深度:后序遍历查栈里元素的个数

将差一步的平衡二叉树变成平衡二叉树

右旋

在原有的二叉树里,添加一个父亲的指针
在左子树的左子树添加一个结点F,进行右旋
A交支点长的一边B - D - F掰下来

两个步骤:
记:A->pLeft = pMark
先处理儿子:

• A ->Father->left = pmark
• pmark->right = A
• pmark = pmark->right
  父亲:
• pmark ->father = A->father
• A->father = pmark
• pmark->right->father = A

  左旋

  与右旋相反

  创建一个不平衡二叉树

  void CreateBiTree(BinaryTree **root)
  {
  	if(root == NULL)return;
  	(*root) = (BinaryTree*)malloc(sizeof(BinaryTree));
  	(*root)->nValue = 1;
  	(*root)->pFather = NULL;
  
  	//左子树
  	(*root)->pLeft = (BinaryTree*)malloc(sizeof(BinaryTree));
  	(*root)->pLeft->nValue = 2;
  	(*root)->pLeft->pFather = *root;
  
  	//右子树
  	(*root)->pRight = NULL;
  
  	//左的左
  	(*root)->pLeft->pLeft = (BinaryTree*)malloc(sizeof(BinaryTree));
  	(*root)->pLeft->pLeft->nValue = 3;
  	(*root)->pLeft->pLeft->pFather = (*root)->pLeft;
  
  	//左的左的左
  	(*root)->pLeft->pLeft->pLeft = (BinaryTree*)malloc(sizeof(BinaryTree));
  	(*root)->pLeft->pLeft->pLeft->nValue = 5;
  	(*root)->pLeft->pLeft->pLeft->pFather = (*root)->pLeft->pLeft;
  	(*root)->pLeft->pLeft->pLeft->pLeft = NULL;
  	(*root)->pLeft->pLeft->pLeft->pRight = NULL;
  
  	//左的左的右
  	(*root)->pLeft->pLeft->pRight = (BinaryTree*)malloc(sizeof(BinaryTree));
  	(*root)->pLeft->pLeft->pRight ->nValue = 6;
  	(*root)->pLeft->pLeft->pRight ->pFather = (*root)->pLeft->pLeft;
  	(*root)->pLeft->pLeft->pRight ->pLeft = NULL;
  	(*root)->pLeft->pLeft->pRight ->pRight = NULL;
  
  	//左的右
  	(*root)->pLeft->pRight = (BinaryTree*)malloc(sizeof(BinaryTree));
  	(*root)->pLeft->pRight->nValue = 4;
  	(*root)->pLeft->pRight->pFather = (*root)->pLeft;
  	(*root)->pLeft->pRight->pLeft = NULL;
  	(*root)->pLeft->pRight->pRight = NULL;
  }

右旋,左旋代码

void RightRotate(BinaryTree **pTree)
{
    BinaryTree *pMark = NULL;

    if(pTree == NULL)return;

    //右旋标记左侧
    pMark = (*pTree)->pLeft;

    //处理儿子关系
    (*pTree)->pLeft = pMark->pRight;
    pMark->pRight = *pTree;

    //支点父亲是否存在
    if((*pTree)->pFather != NULL)
    {
        //将支点的左和支点的父亲关联起来
        ((*pTree)->pFather->pLeft == *pTree)?((*pTree)->pFather->pLeft  = pMark):((*pTree)->pFather->pRight= pMark);
    }

    //关联父亲
    //支点的左是否存在
    if((*pTree)->pLeft != NULL)
    {
        (*pTree)->pLeft->pFather = *pTree;
    }

    pMark->pFather = (*pTree)->pFather;
    (*pTree)->pFather = pMark;

    //支点是根节点 旋转之后根节点更改
    if(pMark->pFather == NULL)
    {
        *pTree = pMark;
    }
}

void LeftRotate(BinaryTree **pTree)
{
    BinaryTree *pMark = NULL;

    if(pTree == NULL)return;

    //右旋标记左侧
    pMark = (*pTree)->pRight;

    //处理儿子关系
    (*pTree)->pRight = pMark->pLeft;
    pMark->pLeft = *pTree;

    //支点父亲是否存在
    if((*pTree)->pFather != NULL)
    {
        //将支点的左和支点的父亲关联起来
        ((*pTree)->pFather->pLeft == *pTree)?((*pTree)->pFather->pLeft  = pMark):((*pTree)->pFather->pRight= pMark);
    }

    //关联父亲
    //支点的左是否存在
    if((*pTree)->pRight != NULL)
    {
        (*pTree)->pRight->pFather = *pTree;
    }

    pMark->pFather = (*pTree)->pFather;
    (*pTree)->pFather = pMark;

    //支点是根节点 旋转之后根节点更改
    if(pMark->pFather == NULL)
    {
        *pTree = pMark;
    }
}