二叉树的各种操作总结（C/C++版）

水深无声 2022-05-14 16:29 162阅读 0赞

## 1.二叉树基本操作 ##

建二叉树，前、中、后序递归遍历，求深度或高度，前、中、后序搜索。  
见[数据结构——二叉树及其基本操作][Link 1]

## 2.二叉树非递归遍历 ##

前、中、后序非递归遍历。  
见[经典算法之非递归算法实现二叉树前、中、后序遍历][Link 2]

## 3.二叉树层序遍历 ##

见[经典算法之层序遍历二叉树][Link 3]

## 4.前序线索二叉树 ##

见[数据结构——前序线索二叉树及其前序遍历][Link 4]

## 5.中序线索二叉树 ##

见[数据结构——中序线索二叉树及其中序遍历][Link 5]

## 6.后序线索二叉树 ##

待补充，过段时间写。

## 7.Huffman树 ##

见[哈夫曼树及哈夫曼编码详解【完整版代码】][Link 6]

## 8.判断二叉树是不是二叉搜索树 ##

通过中序遍历（从小到大的顺序）来判断是否是一个搜索二叉树。

#include<stdio.h>
    #include<math.h>
    #define INT_MAX 0x7fffffff
    #define INT_MIN 0x80000000
    //INT_MAX = 2147483647
    //INT_MIN = -2147483648
    typedef struct BtNode
    {
        
    	int data;
    	struct BtNode *lchild;
    	struct BtNode *rchild;
    }BtNode,*BtTree;
    //以下的算法都如果没有特殊说明，都统一用这个结构体

bool isSearchBTree(BtNode *root,int &intMin)
    {
        
    	if(root==NULL)
    		return true;//空树时满足
    	if(isSearchBTree(root->lchild,intMin))
    	{
        
    		if(root->data>=intMin)
    		{
        
    			intMin=root->data
    			if(isSearchBTree(root->rchild,intMin))
    				return true;
    			else
    				return false;//右孩子不满足
    		}
    		else
    			return false;//根不满足
    	}
    	else
    		return false;//左孩子不满足
    }

## 9.判断二叉树是不是完全二叉树 ##

完全二叉树，要求在最后一层的右侧才可以存在空节点。  
层序遍历，一旦一个节点含有空子树后，之后所有的节点必须只含有NULL。

#define maxSize 100
    #define INT_MAX 0x7fffffff
    #define INT_MIN 0x80000000
    //INT_MAX = 2147483647
    //INT_MIN = -2147483648
    typedef struct BtNode
    {
        
    	int data;
    	struct BtNode *lchild;
    	struct BtNode *rchild;
    }BtNode,*BtTree;

bool isCompleteBTree(BtNode *root)
    {
        
    	if(root==NULL)
    		return true;
    	BtNode *queue[maxSize];
    	int front=0,rear=0;
    	BtNode *p;
    	bool isBtNodeNull=false;
    	rear=(rear+1)%maxSize;
    	queue[rear]=root;
    	while(front!=rear)
    	{
        
    		front=(front+1)%maxSize;
    		p=queue[front];
    		if(isBtNodeNull)
    		{
        
    			if(p->lchild||p->rchild)
    				return false;
    		}
    		else
    		{
        
    			if(p->lchild&&p->rchild)
    			{
        //左右非空
    				rear=(rear+1)%maxSize;
    				queue[rear]=p->lchild;
    
    				rear=(rear+1)%maxSize;
    				queue[rear]=p->rchild;
    
    			}
    			else if(p->lchild&&p->rchild==NULL)
    			{
        //左非空，右空
    				isBtNodeNull=true;
    				
    				rear=(rear+1)%maxSize;
    				queue[rear]=p->lchild;
    			}
    			else if(p->lchild==NULL&&p->rchild)
    			{
        //左空，右非空
    				return false;
    			}
    			else
    			{
        //左右为空
    				isBtNodeNull=true;
    			}
    		}
    
    	}
    	return true;
    }

## 10.判断两棵二叉树是否结构相同 ##

递归实现：先判断根是否相同，再判断左子树和右子树是否相同

bool isBtTreeSame(BtNode *root1,BtNode *root2)
    {
        
    	if(root1==NULL&&root2=NULL)
    		return true;
    	if(root1!=root2)
    		return false;
    	bool lchildResult=isBtTreeSame(root1->lchild,root2->lchild);
    	bool rchildResult=isBtTreeSame(root1->rchild,root2->rchild);
    	return lchildResult&&rchildResult;
    }

## 11.判断二叉树是不是平衡二叉树 ##

只有每一个子树都是平衡树，才能保证它是平衡二叉树。因此，先判断左右子树是否是平衡的并记录左右子树的深度，再判断树是否平衡。  
后序遍历，先判断左右子树是否是平衡的，再判断树是否平衡。

bool isAVLTree(BtNode *root,int &depth)
    {
        
    	if(root==NULL)
    	{
        
    		depth=0;
    		return true;
    	}
    	int leftDepth,rightDepth;
    	if(isAVLTree(root->lchild,leftDepth)&&isAVLTree(root->rchild,rightDepth))
    	{
        
    		if(abs(leftDepth-rightDepth)<=1)
    		{
        
    			depth=max(leftDepth,rightDepth)+1;
    			return true;
    		}
    	}
    	return false;
    }

## 12.求二叉排序树中两个结点的最近公共祖先 ##

利用二叉排序树的特点，中序遍历是非递减序列，左子树结点值小于根，根结点值小于右子树。

#include<stdio.h>
    #include<math.h>
    #include<malloc.h>
    #include<list>
    using namespace std;
    #define maxSize 7
    typedef struct BTNode
    {
        
    	int data;
    	struct BTNode *lchild;
    	struct BTNode *rchild;
    }BTNode,*BTree;
    //创建一棵二叉树
    BTree createTree() 
    {
        
    	BTree pA = (BTNode *)malloc(sizeof(BTNode));
    	BTree pB = (BTNode *)malloc(sizeof(BTNode));
    	BTree pC = (BTNode *)malloc(sizeof(BTNode));
    	BTree pD = (BTNode *)malloc(sizeof(BTNode));
    	BTree pE = (BTNode *)malloc(sizeof(BTNode));
    	BTree pF = (BTNode *)malloc(sizeof(BTNode));
    
    	pA->data = 4;
    	pB->data = 5;
    	pC->data = 2;
    	pD->data = 1;
    	pE->data = 3;
    	pF->data = 6;
    
    	pA->lchild = pC;
    	pA->rchild = pB;
    	pC->lchild = pD;
    	pC->rchild = pE;
    	pB->rchild = pF;
    	pB->lchild = NULL;
    	pD->lchild = pD->rchild = NULL;
    	pE->lchild = pE->rchild = NULL;
    	pF->lchild = pF->rchild = NULL;
    
    	return pA;
    
    }
    
    BTNode *findLowestCommonAncestoe(BTree T,int v1,int v2)
    {
        
    	while(T)
    	{
        
    		if((T->data>v1)&&(T->data>v2))
    			T=T->lchild;
    		else if((T->data<v1)&&(T->data<v2))
    			T=T->rchild;
    		else
    			return T;
    	}
    	return NULL;
    }
    int main() 
    {
        
    	BTree pTree = createTree();
    	int v1=3,v2=1;
    	if(findLowestCommonAncestoe(pTree,v1,v2))
    	{
        
    		BTNode *p=findLowestCommonAncestoe(pTree,v1,v2);
    		printf("%d\n",p->data);
    	}
    	else
    		printf("可能是没有公共结点\n");
    	return 0;
    }

## 13.求二叉树的叶子结点个数 ##

int leafNodeNum(BTNode *root)
    {
        
    	if(root==NULL)
    		return 0;
    	if(root->lchild==NULL&&root->rchild==NULL)
    		return 1;
    	else
    		return leafNodeNum(root->lchild)+leafNodeNum(root->rchild);
    }

## 14.求二叉树的直径 ##

树中任意两结点之间都存在一条路径，两结点的距离即定义为路径的长度。距离最远的两结点的距离定义为树的直径。  
树的直径是树中某一结点的左右子树的高度之和，但不一定是根结点，反例易举。

int BTreeHeight(BTree T,int *maxHeightSum)
    {
        
    //这个函数实际就是求二叉树的高度，只不过多一个参数记录某一结点的
    //左右子树的高度之和的最大值
    	if(!T)return 0;
    	int leftHeight=BTreeHeight(T->lchild,maxHeightSum);
    	int rightHeight=BTreeHeight(T->rchild,maxHeightSum);
    	(*maxHeightSum)=max(leftHeight+rightHeight,*maxHeightSum);
    	return max(leftHeight,rightHeight)+1;
    }
    int findRadOfTree(BTree T)
    {
        
    	int maxHeightSum=0;
    	BTreeHeight(T,&maxHeightSum);
    	return maxHeightSum;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhcmRzZXB0ZW1iZXI_size_16_color_FFFFFF_t_70]

[Link 1]: https://blog.csdn.net/wardseptember/article/details/78872111
[Link 2]: https://blog.csdn.net/wardseptember/article/details/78883843
[Link 3]: https://blog.csdn.net/wardseptember/article/details/78879360
[Link 4]: https://blog.csdn.net/wardseptember/article/details/78900959
[Link 5]: https://blog.csdn.net/wardseptember/article/details/78891412
[Link 6]: https://blog.csdn.net/wardseptember/article/details/80717653
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhcmRzZXB0ZW1iZXI_size_16_color_FFFFFF_t_70]: /images/20220503/639e623c9d8e44e8a3f56baf06bddc83.png