树是一种比较重要的数据结构,尤其是二叉树。二叉树是一种特殊的树,在二叉树中每个节点最多有两个子节点,一般称为左子节点和右子节点(或左孩子和右孩子),并且二叉树的子树有左右之分,其次序不能任意颠倒。二叉树是递归定义的,因此,与二叉树有关的题目基本都可以用递归思想解决,当然有些题目非递归解法也应该掌握,如非递归遍历节点等等。本文努力对二叉树相关题目做一个较全的整理总结,希望对找工作的同学有所帮助。
二叉树节点定义如下:
struct BinaryTreeNode{ int m_nValue; BinaryTreeNode* m_pLeft; BinaryTreeNode* m_pRight;};
题目列表:
详细解答
1. 求二叉树中的节点个数
递归解法:(1)如果二叉树为空,节点个数为0(2)如果二叉树不为空,二叉树节点个数 = 左子树节点个数 + 右子树节点个数 + 1参考代码如下:- int GetNodeNum(BinaryTreeNode * pRoot)
- {
- if(pRoot == NULL) // 递归出口
- return 0;
- return GetNodeNum(pRoot->m_pLeft) + GetNodeNum(pRoot->m_pRight) + 1;
- }
- int GetDepth(BinaryTreeNode * pRoot)
- {
- if(pRoot == NULL) // 递归出口
- return 0;
- int depthLeft = GetDepth(pRoot->m_pLeft);
- int depthRight = GetDepth(pRoot->m_pRight);
- return depthLeft > depthRight ? (depthLeft + 1) : (depthRight + 1);
- }
- void PreOrderTraverse(BinaryTreeNode * pRoot)
- {
- if(pRoot == NULL)
- return;
- Visit(pRoot); // 访问根节点
- PreOrderTraverse(pRoot->m_pLeft); // 前序遍历左子树
- PreOrderTraverse(pRoot->m_pRight); // 前序遍历右子树
- }
- void InOrderTraverse(BinaryTreeNode * pRoot)
- {
- if(pRoot == NULL)
- return;
- InOrderTraverse(pRoot->m_pLeft); // 中序遍历左子树
- Visit(pRoot); // 访问根节点
- InOrderTraverse(pRoot->m_pRight); // 中序遍历右子树
- }
- void PostOrderTraverse(BinaryTreeNode * pRoot)
- {
- if(pRoot == NULL)
- return;
- PostOrderTraverse(pRoot->m_pLeft); // 后序遍历左子树
- PostOrderTraverse(pRoot->m_pRight); // 后序遍历右子树
- Visit(pRoot); // 访问根节点
- }
4.分层遍历二叉树(按层次从上往下,从左往右)
相当于广度优先搜索,使用队列实现。队列初始化,将根节点压入队列。当队列不为空,进行如下操作:弹出一个节点,访问,若左子节点或右子节点不为空,将其压入队列。
- void LevelTraverse(BinaryTreeNode * pRoot)
- {
- if(pRoot == NULL)
- return;
- queue<BinaryTreeNode *> q;
- q.push(pRoot);
- while(!q.empty())
- {
- BinaryTreeNode * pNode = q.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;
- }
要求不能创建新节点,只调整指针。 递归解法: (1)如果二叉树查找树为空,不需要转换,对应双向链表的第一个节点是NULL,最后一个节点是NULL (2)如果二叉查找树不为空:
如果左子树为空,对应双向有序链表的第一个节点是根节点,左边不需要其他操作;
如果左子树不为空,转换左子树,二叉查找树对应双向有序链表的第一个节点就是左子树转换后双向有序链表的第一个节点,同时将根节点和左子树转换后的双向有序链 表的最后一个节点连接;
如果右子树为空,对应双向有序链表的最后一个节点是根节点,右边不需要其他操作;
如果右子树不为空,对应双向有序链表的最后一个节点就是右子树转换后双向有序链表的最后一个节点,同时将根节点和右子树转换后的双向有序链表的第一个节点连 接。参考代码如下:
- /******************************************************************************
- 参数:
- pRoot: 二叉查找树根节点指针
- pFirstNode: 转换后双向有序链表的第一个节点指针
- pLastNode: 转换后双向有序链表的最后一个节点指针
- ******************************************************************************/
- void Convert(BinaryTreeNode * pRoot,
- BinaryTreeNode * & pFirstNode, BinaryTreeNode * & pLastNode)
- {
- BinaryTreeNode *pFirstLeft, *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;
- }
- int GetNodeNumKthLevel(BinaryTreeNode * pRoot, int k)
- {
- if(pRoot == NULL || k < 1)
- return 0;
- if(k == 1)
- return 1;
- int numLeft = GetNodeNumKthLevel(pRoot->m_pLeft, k-1); // 左子树中k-1层的节点个数
- int numRight = GetNodeNumKthLevel(pRoot->m_pRight, k-1); // 右子树中k-1层的节点个数
- return (numLeft + numRight);
- }
- int GetLeafNodeNum(BinaryTreeNode * pRoot)
- {
- if(pRoot == NULL)
- return 0;
- if(pRoot->m_pLeft == NULL && pRoot->m_pRight == NULL)
- return 1;
- int numLeft = GetLeafNodeNum(pRoot->m_pLeft); // 左子树中叶节点的个数
- int numRight = GetLeafNodeNum(pRoot->m_pRight); // 右子树中叶节点的个数
- return (numLeft + numRight);
- }
- bool StructureCmp(BinaryTreeNode * pRoot1, BinaryTreeNode * pRoot2)
- {
- if(pRoot1 == NULL && pRoot2 == NULL) // 都为空,返回真
- return true;
- else if(pRoot1 == NULL || pRoot2 == NULL) // 有一个为空,一个不为空,返回假
- return false;
- bool resultLeft = StructureCmp(pRoot1->m_pLeft, pRoot2->m_pLeft); // 比较对应左子树
- bool resultRight = StructureCmp(pRoot1->m_pRight, pRoot2->m_pRight); // 比较对应右子树
- return (resultLeft && resultRight);
- }
- bool IsAVL(BinaryTreeNode * pRoot, int & height)
- {
- if(pRoot == NULL) // 空树,返回真
- {
- height = 0;
- return true;
- }
- int heightLeft;
- bool resultLeft = IsAVL(pRoot->m_pLeft, heightLeft);
- int heightRight;
- bool resultRight = IsAVL(pRoot->m_pRight, heightRight);
- if(resultLeft && resultRight && abs(heightLeft - heightRight) <= 1) // 左子树和右子树都是AVL,并且高度相差不大于1,返回真
- {
- height = max(heightLeft, heightRight) + 1;
- return true;
- }
- else
- {
- height = max(heightLeft, heightRight) + 1;
- return false;
- }
- }
- BinaryTreeNode * Mirror(BinaryTreeNode * pRoot)
- {
- if(pRoot == NULL) // 返回NULL
- return NULL;
- BinaryTreeNode * pLeft = Mirror(pRoot->m_pLeft); // 求左子树镜像
- BinaryTreeNode * pRight = Mirror(pRoot->m_pRight); // 求右子树镜像
- // 交换左子树和右子树
- pRoot->m_pLeft = pRight;
- pRoot->m_pRight = pLeft;
- return pRoot;
- }
- bool FindNode(BinaryTreeNode * pRoot, BinaryTreeNode * pNode)
- {
- if(pRoot == NULL || pNode == NULL)
- return false;
- if(pRoot == pNode)
- return true;
- bool found = FindNode(pRoot->m_pLeft, pNode);
- if(!found)
- found = FindNode(pRoot->m_pRight, pNode);
- return found;
- }
- BinaryTreeNode * GetLastCommonParent(BinaryTreeNode * pRoot,
- BinaryTreeNode * pNode1,
- BinaryTreeNode * pNode2)
- {
- if(FindNode(pRoot->m_pLeft, pNode1))
- {
- if(FindNode(pRoot->m_pRight, pNode2))
- return pRoot;
- else
- return GetLastCommonParent(pRoot->m_pLeft, pNode1, pNode2);
- }
- else
- {
- if(FindNode(pRoot->m_pLeft, pNode2))
- return pRoot;
- else
- return GetLastCommonParent(pRoot->m_pRight, pNode1, pNode2);
- }
- }
- bool GetNodePath(BinaryTreeNode * pRoot, BinaryTreeNode * pNode,
- list<BinaryTreeNode *> & path)
- {
- if(pRoot == pNode)
- {
- path.push_back(pRoot);
- return true;
- }
- if(pRoot == NULL)
- return false;
- path.push_back(pRoot);
- bool found = false;
- found = GetNodePath(pRoot->m_pLeft, pNode, path);
- if(!found)
- found = GetNodePath(pRoot->m_pRight, pNode, path);
- if(!found)
- path.pop_back();
- return found;
- }
- BinaryTreeNode * GetLastCommonParent(BinaryTreeNode * pRoot, BinaryTreeNode * pNode1, BinaryTreeNode * pNode2)
- {
- if(pRoot == NULL || pNode1 == NULL || pNode2 == NULL)
- return NULL;
- list<BinaryTreeNode*> path1;
- bool bResult1 = GetNodePath(pRoot, pNode1, path1);
- list<BinaryTreeNode*> path2;
- bool bResult2 = GetNodePath(pRoot, pNode2, path2);
- if(!bResult1 || !bResult2)
- return NULL;
- BinaryTreeNode * pLast = NULL;
- list<BinaryTreeNode*>::const_iterator iter1 = path1.begin();
- list<BinaryTreeNode*>::const_iterator iter2 = path2.begin();
- while(iter1 != path1.end() && iter2 != path2.end())
- {
- if(*iter1 == *iter2)
- pLast = *iter1;
- else
- break;
- iter1++;
- iter2++;
- }
- return pLast;
- }
参考代码如下:
- int GetMaxDistance(BinaryTreeNode * pRoot, int & maxLeft, int & maxRight)
- {
- // maxLeft, 左子树中的节点距离根节点的最远距离
- // maxRight, 右子树中的节点距离根节点的最远距离
- if(pRoot == NULL)
- {
- maxLeft = 0;
- maxRight = 0;
- return 0;
- }
- int maxLL, maxLR, maxRL, maxRR;
- int maxDistLeft, 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;
- }
- return max(max(maxDistLeft, maxDistRight), maxLeft+maxRight);
- }
- BinaryTreeNode * RebuildBinaryTree(int* pPreOrder, int* pInOrder, int nodeNum)
- {
- if(pPreOrder == NULL || pInOrder == NULL || nodeNum <= 0)
- return NULL;
- BinaryTreeNode * pRoot = new BinaryTreeNode;
- // 前序遍历的第一个数据就是根节点数据
- pRoot->m_nValue = pPreOrder[0];
- pRoot->m_pLeft = NULL;
- pRoot->m_pRight = NULL;
- // 查找根节点在中序遍历中的位置,中序遍历中,根节点左边为左子树,右边为右子树
- int rootPositionInOrder = -1;
- for(int i = 0; i < nodeNum; i++)
- if(pInOrder[i] == pRoot->m_nValue)
- {
- rootPositionInOrder = i;
- break;
- }
- if(rootPositionInOrder == -1)
- {
- throw std::exception("Invalid input.");
- }
- // 重建左子树
- int nodeNumLeft = rootPositionInOrder;
- int * pPreOrderLeft = pPreOrder + 1;
- int * pInOrderLeft = pInOrder;
- pRoot->m_pLeft = RebuildBinaryTree(pPreOrderLeft, pInOrderLeft, nodeNumLeft);
- // 重建右子树
- int nodeNumRight = nodeNum - nodeNumLeft - 1;
- int * pPreOrderRight = pPreOrder + 1 + nodeNumLeft;
- int * pInOrderRight = pInOrder + nodeNumLeft + 1;
- pRoot->m_pRight = RebuildBinaryTree(pPreOrderRight, pInOrderRight, nodeNumRight);
- return pRoot;
- }
- bool IsCompleteBinaryTree(BinaryTreeNode * pRoot)
- {
- if(pRoot == NULL)
- return false;
- queue<BinaryTreeNode *> q;
- q.push(pRoot);
- bool mustHaveNoChild = false;
- bool result = true;
- while(!q.empty())
- {
- BinaryTreeNode * pNode = 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);
- }
- else if(pNode->m_pLeft != NULL && pNode->m_pRight == NULL)
- {
- mustHaveNoChild = true;
- q.push(pNode->m_pLeft);
- }
- else if(pNode->m_pLeft == NULL && pNode->m_pRight != NULL)
- {
- result = false;
- break;
- }
- else
- {
- mustHaveNoChild = true;
- }
- }
- }
- return result;
- }