二叉树
二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（leftsubtree）和“右子树”（rightsubtree）。二叉树常被用于实现二叉查找树和二叉堆。
遍历顺序
遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。
设L、D、R分别表示遍历左子树、访问根结点和遍历右子树，则对一棵二叉树的遍历有三种情况：DLR（称为先根次序遍历），LDR（称为中根次序遍历），LRD（称为后根次序遍历）。
先序遍历
首先访问根，再先序遍历左（右）子树，最后先序遍历右（左）子树。
中序遍历
首先中序遍历左（右）子树，再访问根，最后中序遍历右（左）子树。
后序遍历
首先后序遍历左（右）子树，再后序遍历右（左）子树，最后访问根。
二叉树节点定义如下：
structBinaryTreeNode
{
intm_nValue;
BinaryTreeNodem_pLeft;
BinaryTreeNodem_pRight;
};
题目列表：
1.求二叉树中的节点个数
2.求二叉树的深度
3.前序遍历，中序遍历，后序遍历
4.分层遍历二叉树（按层次从上往下，从左往右）
5.将二叉查找树变为有序的双向链表
6.求二叉树第K层的节点个数
7.求二叉树中叶子节点的个数
8.判断两棵二叉树是否结构相同
9.判断二叉树是不是平衡二叉树
10.求二叉树的镜像
11.求二叉树中两个节点的最低公共祖先节点
12.求二叉树中节点的最大距离
13.由前序遍历序列和中序遍历序列重建二叉树
14.判断二叉树是不是完全二叉树
详细解答：
1.求二叉树中的节点个数
递归解法：
（1）如果二叉树为空，节点个数为0
（2）如果二叉树不为空，二叉树节点个数=左子树节点个数+右子树节点个数+1
参考代码如下：
[cpp]viewplaincopy
intGetNodeNum(BinaryTreeNodepRoot)
{
if(pRoot==NULL)//递归出口--结束递归
return0;
returnGetNodeNum(pRoot->m_pLeft)+GetNodeNum(pRoot->m_pRight)+1;
}
2.求二叉树的深度
递归解法：
（1）如果二叉树为空，二叉树的深度为0
（2）如果二叉树不为空，二叉树的深度=max(左子树深度，右子树深度)+1
参考代码如下：
[cpp]viewplaincopy
classtest{
intGetDepth(BinaryTreeNodepRoot)
{
if(pRoot==NULL)//递归出口
return0;
intdepthLeft=GetDepth(pRoot->m_pLeft);//左子树的深度
intdepthRight=GetDepth(pRoot->m_pRight);//右子树的深度
//二叉树的深度，取左右中大的那个值。+1为根节点
returndepthLeft>depthRight?(depthLeft+1):(depthRight+1);
}
};
3.前序遍历，中序遍历，后序遍历
前序遍历递归解法：
（1）如果二叉树为空，空操作
（2）如果二叉树不为空，访问根节点，前序遍历左子树，前序遍历右子树
参考代码如下：
[cpp]viewplaincopy
voidPreOrderTraverse(BinaryTreeNodepRoot)
{
if(pRoot==NULL)
return;
Visit(pRoot);//访问根节点
PreOrderTraverse(pRoot->m_pLeft);//前序遍历左子树
PreOrderTraverse(pRoot->m_pRight);//前序遍历右子树
}
中序遍历递归解法
（1）如果二叉树为空，空操作。
（2）如果二叉树不为空，中序遍历左子树，访问根节点，中序遍历右子树
参考代码如下：
[cpp]viewplaincopy
voidInOrderTraverse(BinaryTreeNodepRoot)
{
if(pRoot==NULL)
return;
InOrderTraverse(pRoot->m_pLeft);//中序遍历左子树
Visit(pRoot);//访问根节点
InOrderTraverse(pRoot->m_pRight);//中序遍历右子树
}
后序遍历递归解法
（1）如果二叉树为空，空操作
（2）如果二叉树不为空，后序遍历左子树，后序遍历右子树，访问根节点
参考代码如下：
[cpp]viewplaincopy
voidPostOrderTraverse(BinaryTreeNodepRoot)
{
if(pRoot==NULL)
return;
PostOrderTraverse(pRoot->m_pLeft);//后序遍历左子树
PostOrderTraverse(pRoot->m_pRight);//后序遍历右子树
Visit(pRoot);//访问根节点
}
4.分层遍历二叉树（按层次从上往下，从左往右）
相当于广度优先搜索，使用队列实现。队列初始化，将根节点压入队列。当队列不为空，进行如下操作：弹出一个节点，访问，若左子节点或右子节点不为空，将其压入队列。
[cpp]viewplaincopy
voidLevelTraverse(BinaryTreeNodepRoot)
{
if(pRoot==NULL)
return;
queueq;
q.push(pRoot);
while(!q.empty())
{
BinaryTreeNodepNode=q.front();//front
q.pop();
Visit(pNode);//访问结点 if(pNode->m_pLeft!=NULL)
q.push(pNode->m_pLeft);
if(pNode->m_pRight!=NULL)
q.push(pNode->m_pRight);
}
return;
}
5.将二叉查找树变为有序的双向链表
要求不能创建新节点，只调整指针。
递归解法：
（1）如果二叉树查找树为空，不需要转换，对应双向链表的第一个节点是NULL，最后一个节点是NULL
（2）如果二叉查找树不为空：
如果左子树为空，对应双向有序链表的第一个节点是根节点，左边不需要其他操作；
如果左子树不为空，转换左子树，二叉查找树对应双向有序链表的第一个节点就是左子树转换后双向有序链表的第一个节点，同时将根节点和左子树转换后的双向有序链表的最后一个节点连接；
如果右子树为空，对应双向有序链表的最后一个节点是根节点，右边不需要其他操作；
如果右子树不为空，对应双向有序链表的最后一个节点就是右子树转换后双向有序链表的最后一个节点，同时将根节点和右子树转换后的双向有序链表的第一个节点连接。
参考代码如下：
[cpp]viewplaincopy
/
参数：
pRoot:二叉查找树根节点指针
pFirstNode:转换后双向有序链表的第一个节点指针
pLastNode:转换后双向有序链表的最后一个节点指针
/
voidConvert(BinaryTreeNodepRoot,
BinaryTreeNode&pFirstNode,BinaryTreeNode&pLastNode)
{
BinaryTreeNodepFirstLeft,pLastLeft,pFirstRight,pLastRight;
if(pRoot==NULL)
{
pFirstNode=NULL;
pLastNode=NULL;
return;
}
if(pRoot->m_pLeft==NULL)
{
//如果左子树为空，对应双向有序链表的第一个节点是根节点
pFirstNode=pRoot;
}
else
{
Convert(pRoot->m_pLeft,pFirstLeft,pLastLeft);
//二叉查找树对应双向有序链表的第一个节点就是左子树转换后双向有序链表的第一个节点
pFirstNode=pFirstLeft;
//将根节点和左子树转换后的双向有序链表的最后一个节点连接
pRoot->m_pLeft=pLastLeft;
pLastLeft->m_pRight=pRoot;
}
if(pRoot->m_pRight==NULL)
{
//对应双向有序链表的最后一个节点是根节点
pLastNode=pRoot;
}
else
{
Convert(pRoot->m_pRight,pFirstRight,pLastRight);
//对应双向有序链表的最后一个节点就是右子树转换后双向有序链表的最后一个节点
pLastNode=pLastRight;
//将根节点和右子树转换后的双向有序链表的第一个节点连接
pRoot->m_pRight=pFirstRight;
pFirstRight->m_pLeft=pRoot;
}
return;
}
6.求二叉树第K层的节点个数
递归解法：
（1）如果二叉树为空或者k<1返回0
（2）如果二叉树不为空并且k==1，返回1
（3）如果二叉树不为空且k>1，返回左子树中k-1层的节点个数与右子树k-1层节点个数之和
参考代码如下：
[cpp]viewplaincopy
intGetNodeNumKthLevel(BinaryTreeNodepRoot,intk)
{
if(pRoot==NULL||k<1)
return0;
if(k==1)
return1;
intnumLeft=GetNodeNumKthLevel(pRoot->m_pLeft,k-1);//右子树中k-1层结点的个数
intnumRight=GetNodeNumKthLevel(pRoot->m_pRight,k-1);//左子树中k-1层结点的个数
returnnumLeft+numRight;
}
7.求二叉树中叶子节点的个数
递归解法：
（1）如果二叉树为空，返回0
（2）如果二叉树不为空且左右子树为空，返回1
（3）如果二叉树不为空，且左右子树不同时为空，返回左子树中叶子节点个数加上右子树中叶子节点个数
参考代码如下：
[cpp]viewplaincopy
intGetLeafNodeNum(BinaryTreeNodepRoot)
{
if(pRoot==NULL)
return0;
if(pRoot->m_pLeft==NULL&&pRoot->m_pRight==NULL)
return1;
intnumLeft=GetLeafNodeNum(pRoot->m_pLeft);//左子树中叶子节点的个数
intnumRight=GetLeafNodeNum(pRoot->m_pRight);//右子树中叶子节点的个数
return(numLeft+numRight);
}
8.判断两棵二叉树是否结构相同
不考虑数据内容。结构相同意味着对应的左子树和对应的右子树都结构相同。
递归解法：
（1）如果两棵二叉树都为空，返回真
（2）如果两棵二叉树一棵为空，另一棵不为空，返回假
（3）如果两棵二叉树都不为空，如果对应的左子树和右子树都同构返回真，其他返回假
参考代码如下
[cpp]viewplaincopy
boolStructureCmp(BinaryTreeNodepRoot1,BinaryTreeNodepRoot2)
{
if(pRoot1==NULL&&pRoot2==NULL)
returntrue;
if(pRoot1==NULL||pRoot2==NULL)//有一个为空，一个不为空，返回假
returnfalse;
boolresultLeft=StructureCmp(pRoot1->m_pLeft,pRoot2->m_pLeft);//比较对应左子树
boolresultRight=StructureCmp(pRoot1->m_pRight,pRoot2->m_pRight);//比较对应右子树
return(resultLeft&&resultRight);
}
9.判断二叉树是不是平衡二叉树
递归解法：
（1）如果二叉树为空，返回真
（2）如果二叉树不为空，如果左子树和右子树都是AVL树并且左子树和右子树高度相差不大于1，返回真，其他返回假
参考代码：
[cpp]viewplaincopy
boolIsAVL(BinaryTreeNodepRoot,int&height)
{
if(pRoot==NULL)//空树，返回真
{
height=0;
returntrue;
}
intheightLeft;
boolresultLeft=IsAVL(pRoot->m_pLeft,heightLeft);
intheightRight;
boolresultRight=IsAVL(pRoot->m_pRight,heightRight);
if(resultLeft&&resultRight&&abs(heightLeft-heightRight)<=1)//左子树和右子树都是AVL，并且高度相差不大于1，返回真
{
height=max(heightLeft,heightRight)+1;
returntrue;
}
else
{
height=max(heightLeft,heightRight)+1;
returnfalse;
}
}
10.求二叉树的镜像
递归解法：
（1）如果二叉树为空，返回空
（2）如果二叉树不为空，求左子树和右子树的镜像，然后交换左子树和右子树
参考代码如下：
[cpp]viewplaincopy
BinaryTreeNodeMirror(BinaryTreeNodepRoot)
{
if(pRoot==NULL)//返回NULL
returnNULL;
BinaryTreeNodepLeft=Mirror(pRoot->m_pLeft);//求左子树镜像
BinaryTreeNodepRight=Mirror(pRoot->m_pRight);//求右子树镜像
//交换左子树和右子树
pRoot->m_pLeft=pRight;
pRoot->m_pRight=pLeft;
returnpRoot;
}
11.求二叉树中两个节点的最低公共祖先节点
递归解法：
（1）如果两个节点分别在根节点的左子树和右子树，则返回根节点
（2）如果两个节点都在左子树，则递归处理左子树；如果两个节点都在右子树，则递归处理右子树
参考代码如下：
[cpp]viewplaincopy
boolFindNode(BinaryTreeNodepRoot,BinaryTreeNodepNode)
{
if(pRoot==NULL||pNode==NULL)
returnfalse;
if(pRoot==pNode)
returntrue;
boolfound=FindNode(pRoot->m_pLeft,pNode);
if(!found)
found=FindNode(pRoot->m_pRight,pNode);
returnfound;
}
BinaryTreeNodeGetLastCommonParent(BinaryTreeNodepRoot,
BinaryTreeNodepNode1,
BinaryTreeNodepNode2)
{
if(FindNode(pRoot->m_pLeft,pNode1))
{
if(FindNode(pRoot->m_pRight,pNode2))
returnpRoot;
else
returnGetLastCommonParent(pRoot->m_pLeft,pNode1,pNode2);
}
else
{
if(FindNode(pRoot->m_pLeft,pNode2))
returnpRoot;
else
returnGetLastCommonParent(pRoot->m_pRight,pNode1,pNode2);
}
}
递归解法效率很低，有很多重复的遍历，下面看一下非递归解法。
非递归解法：
先求从根节点到两个节点的路径，然后再比较对应路径的节点就行，最后一个相同的节点也就是他们在二叉树中的最低公共祖先节点
参考代码如下：
[cpp]viewplaincopy
boolGetNodePath(BinaryTreeNodepRoot,BinaryTreeNodepNode,
list&path)
{
if(pRoot==pNode)
{
path.push_back(pRoot);
returntrue;
}
if(pRoot==NULL)
returnfalse;
path.push_back(pRoot);
boolfound=false;
found=GetNodePath(pRoot->m_pLeft,pNode,path);
if(!found)
found=GetNodePath(pRoot->m_pRight,pNode,path);
if(!found)
path.pop_back();
returnfound;
}
BinaryTreeNodeGetLastCommonParent(BinaryTreeNodepRoot,BinaryTreeNodepNode1,BinaryTreeNodepNode2)
{
if(pRoot==NULL||pNode1==NULL||pNode2==NULL)
returnNULL;
listpath1;
boolbResult1=GetNodePath(pRoot,pNode1,path1);
listpath2;
boolbResult2=GetNodePath(pRoot,pNode2,path2);
if(!bResult1||!bResult2)
returnNULL;
BinaryTreeNodepLast=NULL;
list::const_iteratoriter1=path1.begin();
list::const_iteratoriter2=path2.begin();
while(iter1!=path1.end()&&iter2!=path2.end())
{
if(iter1==iter2)
pLast=iter1;
else
break;
iter1++;
iter2++;
}
returnpLast;
}
在上述算法的基础上稍加变化即可求二叉树中任意两个节点的距离了。
12.求二叉树中节点的最大距离
即二叉树中相距最远的两个节点之间的距离。
递归解法：
（1）如果二叉树为空，返回0，同时记录左子树和右子树的深度，都为0
（2）如果二叉树不为空，最大距离要么是左子树中的最大距离，要么是右子树中的最大距离，要么是左子树节点中到根节点的最大距离+右子树节点中到根节点的最大距离，同时记录左子树和右子树节点中到根节点的最大距离。
参考代码如下：
[cpp]viewplaincopy
intGetMaxDistance(BinaryTreeNodepRoot,int&maxLeft,int&maxRight)
{
//maxLeft,左子树中的节点距离根节点的最远距离
//maxRight,右子树中的节点距离根节点的最远距离
if(pRoot==NULL)
{
maxLeft=0;
maxRight=0;
return0;
}
intmaxLL,maxLR,maxRL,maxRR;
intmaxDistLeft,maxDistRight;
if(pRoot->m_pLeft!=NULL)
{
maxDistLeft=GetMaxDistance(pRoot->m_pLeft,maxLL,maxLR);
maxLeft=max(maxLL,maxLR)+1;
}
else
{
maxDistLeft=0;
maxLeft=0;
}
if(pRoot->m_pRight!=NULL)
{
maxDistRight=GetMaxDistance(pRoot->m_pRight,maxRL,maxRR);
maxRight=max(maxRL,maxRR)+1;
}
else
{
maxDistRight=0;
maxRight=0;
}
returnmax(max(maxDistLeft,maxDistRight),maxLeft+maxRight);
}
13.由前序遍历序列和中序遍历序列重建二叉树
二叉树前序遍历序列中，第一个元素总是树的根节点的值。中序遍历序列中，左子树的节点的值位于根节点的值的左边，右子树的节点的值位
于根节点的值的右边。
递归解法：
（1）如果前序遍历为空或中序遍历为空或节点个数小于等于0，返回NULL。
（2）创建根节点。前序遍历的第一个数据就是根节点的数据，在中序遍历中找到根节点的位置，可分别得知左子树和右子树的前序和中序遍
历序列，重建左右子树。
[cpp]viewplaincopy
BinaryTreeNodeRebuildBinaryTree(intpPreOrder,intpInOrder,intnodeNum)
{
if(pPreOrder==NULL||pInOrder==NULL||nodeNum<=0)
returnNULL;
BinaryTreeNodepRoot=newBinaryTreeNode;
//前序遍历的第一个数据就是根节点数据
pRoot->m_nValue=pPreOrder[0];
pRoot->m_pLeft=NULL;
pRoot->m_pRight=NULL;
//查找根节点在中序遍历中的位置，中序遍历中，根节点左边为左子树，右边为右子树
introotPositionInOrder=-1;
for(inti=0;i
if(pInOrder[i]==pRoot->m_nValue)
{
rootPositionInOrder=i;
break;
}
if(rootPositionInOrder==-1)
{
throwstd::exception("Invalidinput.");
}
//重建左子树
intnodeNumLeft=rootPositionInOrder;
intpPreOrderLeft=pPreOrder+1;
intpInOrderLeft=pInOrder;
pRoot->m_pLeft=RebuildBinaryTree(pPreOrderLeft,pInOrderLeft,nodeNumLeft);
//重建右子树
intnodeNumRight=nodeNum-nodeNumLeft-1;
intpPreOrderRight=pPreOrder+1+nodeNumLeft;
intpInOrderRight=pInOrder+nodeNumLeft+1;
pRoot->m_pRight=RebuildBinaryTree(pPreOrderRight,pInOrderRight,nodeNumRight);
returnpRoot;
}
同样，有中序遍历序列和后序遍历序列，类似的方法可重建二叉树，但前序遍历序列和后序遍历序列不同恢复一棵二叉树，证明略。
14.判断二叉树是不是完全二叉树
若设二叉树的深度为h，除第h层外，其它各层(1～h-1)的结点数都达到最大个数，第h层所有的结点都连续集中在最左边，这就是完全
二叉树。
有如下算法，按层次（从上到下，从左到右）遍历二叉树，当遇到一个节点的左子树为空时，则该节点右子树必须为空，且后面遍历的节点左
右子树都必须为空，否则不是完全二叉树。
[cpp]viewplaincopy
boolIsCompleteBinaryTree(BinaryTreeNodepRoot)
{
if(pRoot==NULL)
returnfalse;
queueq;
q.push(pRoot);
boolmustHaveNoChild=false;
boolresult=true;
while(!q.empty())
{
BinaryTreeNodepNode=q.front();
q.pop();
if(mustHaveNoChild)//已经出现了有空子树的节点了，后面出现的必须为叶节点（左右子树都为空）
{
if(pNode->m_pLeft!=NULL||pNode->m_pRight!=NULL)
{
result=false;
break;
}
}
else
{
if(pNode->m_pLeft!=NULL&&pNode->m_pRight!=NULL)
{
q.push(pNode->m_pLeft);
q.push(pNode->m_pRight);
}
elseif(pNode->m_pLeft!=NULL&&pNode->m_pRight==NULL)
{
mustHaveNoChild=true;
q.push(pNode->m_pLeft);
}
elseif(pNode->m_pLeft==NULL&&pNode->m_pRight!=NULL)
{
result=false;
break;
}
else
{
mustHaveNoChild=true;
}
}
}
returnresult;
}
|
|
