本文共 11435 字,大约阅读时间需要 38 分钟。
转载来自:
struct BinaryTreeNode{ int m_nValue; BinaryTreeNode* m_pLeft; BinaryTreeNode* m_pRight;};
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); // 访问根节点}
void LevelTraverse(BinaryTreeNode * pRoot){ if(pRoot == NULL) return; queueq; 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;}
如果左子树为空,对应双向有序链表的第一个节点是根节点,左边不需要其他操作;
如果左子树不为空,转换左子树,二叉查找树对应双向有序链表的第一个节点就是左子树转换后双向有序链表的第一个节点,同时将根节点和左子树转换后的双向有序链 表的最后一个节点连接;
如果右子树为空,对应双向有序链表的最后一个节点是根节点,右边不需要其他操作;
如果右子树不为空,对应双向有序链表的最后一个节点就是右子树转换后双向有序链表的最后一个节点,同时将根节点和右子树转换后的双向有序链表的第一个节点连 接。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(TreeNode * 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; }}
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& 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 path1; bool bResult1 = GetNodePath(pRoot, pNode1, path1); list path2; bool bResult2 = GetNodePath(pRoot, pNode2, path2); if(!bResult1 || !bResult2) return NULL; BinaryTreeNode * pLast = NULL; list ::const_iterator iter1 = path1.begin(); list ::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; queueq; 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;}