二叉树的面试题总结

二叉树的创建二叉树的高度二叉树某层节点的个数二叉树的镜像二叉树最远两个节点的距离二叉树的前中后层序递归非递归遍历判断二叉树是否是完全二叉树二叉树叶子节点的个数 #include<iostream> #include<stack> #include<queue> using namespace std; template<class T> struct BinaryTreeNode { T _data; BinaryTreeNode<T> *_pRight; BinaryTreeNode<T> *_pLeft; BinaryTreeNode(T data) : _data(data), _pRight(nullptr), _pLeft(nullptr) {} }; template<class T> class BinaryTree { private: typedef BinaryTreeNode<T> Node; public: BinaryTree() :_pRoot(nullptr) {} //创建二叉树 BinaryTree(const T *arr, const size_t size, const T invalid) { size_t index = 0; _CreateTree(_pRoot, arr, size, index, invalid); } void PreOrder() { cout << "前序遍历递归版" << endl; _PreOrder(_pRoot); cout << endl; } void PreOrder_Nor() { cout << "前序遍历栈版" << endl; _PreOrder_Nor(_pRoot); cout << endl; } void PostOrder() { cout << "后续遍历递归版" << endl; _PostOrder(_pRoot); cout << endl; } void PostOrder_Nor() { cout << "后序遍历栈版" << endl; _PostOrder_Nor(_pRoot); cout << endl; } ~BinaryTree() { _DestroyTree(_pRoot); } //判断是否是完全二叉树 bool IsCompleteBinaryTree() { return _IsCompleteBinaryTree(_pRoot); } //获取二叉树的镜像 void GetBinaryMirror() { return _GetBinaryMirror(_pRoot); } //获取二叉树的高度 size_t Height() { return _Height(_pRoot); } //得到二叉树叶子节点的个数 size_t GetLeefNode() { return _GetLeefNode(_pRoot); } //得到二叉树第K层的节点数目 size_t GetKLevelNode(size_t k) { cout << "树的第K层有多少节点" << endl; return _GetKLevelNode(_pRoot, k); } //得到二叉树中距离最远的两个结点之间的距离 int GetFarthestDistance() { int distance = 0; _GetFarthestDistance(_pRoot, distance); return distance; } private: //index记得给引用 void _CreateTree(Node *&pRoot, const T *arr, const size_t size, size_t &index, T invalid) { if ((index < size) && (arr[index] != invalid)) { pRoot = new Node(arr[index]); _CreateTree(pRoot->_pLeft, arr, size, ++index, invalid); _CreateTree(pRoot->_pRight, arr, size, ++index, invalid); } } void _PreOrder(Node *pRoot) { if (pRoot) { cout << pRoot->_data << " "; _PreOrder(pRoot->_pLeft); _PreOrder(pRoot->_pRight); } } void _PreOrder_Nor(Node *pRoot) { stack<Node*> st; Node *pCur = pRoot; while (pCur || !st.empty()) { while (pCur) { cout << pCur->_data << " "; st.push(pCur); pCur = pCur->_pLeft; } Node *pTop = st.top(); st.pop(); pCur = pTop->_pRight; } cout << endl; } void _PostOrder(Node *pRoot) { if (pRoot) { _PostOrder(pRoot->_pLeft); _PostOrder(pRoot->_pRight); cout << pRoot->_data << " "; } } void _PostOrder_Nor(Node *pRoot) { stack<Node *> st; Node *pCur = pRoot; Node *pFlag = nullptr; while (pCur || !st.empty()) { while (pCur) { st.push(pCur); pCur = pCur->_pLeft; } pCur = st.top(); if ((nullptr == pCur->_pRight) || (pFlag == pCur->_pRight)) { st.pop(); cout << pCur->_data << " "; pFlag = pCur; pCur = nullptr; } else if (pCur->_pRight) { pCur = pCur->_pRight; } } } void _DestroyTree(Node *pRoot) { if (pRoot) { _DestroyTree(pRoot->_pLeft); _DestroyTree(pRoot->_pRight); delete pRoot; pRoot = nullptr; } } /* 1. 层序遍历找到第一个度不为2的节点，把flag设置为true 2. 若该节点只有左孩子没有右孩子继续遍历，若继续遍历的节点度不为0返回false 3. 若该节点只有右孩子没有左孩子返回false 4. 若栈为空返回true */ bool _IsCompleteBinaryTree(Node *pRoot) { queue<Node *> q; q.push(pRoot); if (NULL == pRoot->_pLeft&&NULL == pRoot->_pRight) { return true; } bool flag = false; while (!q.empty()) { Node *pTop = q.front(); if (flag && ((pTop->_pLeft) || (pTop->_pRight))) return false; if (pTop->_pLeft) q.push(pTop->_pLeft); if (pTop->_pRight && (NULL == pTop->_pLeft)) return false; if (pTop->_pRight) q.push(pTop->_pRight); else flag = true; q.pop(); } return true; } //找到二叉树中距离最远的两个节点 int _GetFarthestDistance(Node* pRoot, int& distance) { if (NULL == pRoot) return 0; int left = _GetFarthestDistance(pRoot->_pLeft,distance); int right = _GetFarthestDistance(pRoot->_pRight, distance); if (left + right > distance) distance = left + right; return left > right ? left + 1 : right + 1; } //得到二叉树的镜像 //层序或者前序后序遍历节点交换左右孩子 void _GetBinaryMirror(Node *pRoot) { queue<Node *> q; q.push(pRoot); while (!q.empty()) { Node *pTop = q.front(); if (pTop) { swap(pTop->_pLeft, pTop->_pRight); } if (pTop->_pLeft) q.push(pTop->_pLeft); if (pTop->_pRight) q.push(pTop->_pRight); q.pop(); } } size_t _Height(Node *pRoot) { if (NULL == pRoot) return 0; size_t highLeft = 1 + _Height(pRoot->_pLeft); size_t highRight = 1 + _Height(pRoot->_pRight); return highLeft > highRight ? highLeft : highRight; } size_t _GetLeefNode(Node *pRoot) { if (pRoot == NULL) return 0; if (NULL == pRoot->_pLeft&&NULL == pRoot->_pRight) return 1; return _GetLeefNode(pRoot->_pLeft) + _GetLeefNode(pRoot->_pRight); } size_t _GetKLevelNode(Node *pRoot, size_t k) { if (k<1 || k>_Height(pRoot) || NULL == pRoot) return 0; if (k == 1 || NULL == pRoot->_pLeft || NULL == pRoot->_pRight) return 1; return _GetKLevelNode(pRoot->_pRight, k - 1) + _GetKLevelNode(pRoot->_pLeft, k - 1); } private: Node *_pRoot; }; void test() { char arr[] = { '1', '2', '4', '#', '#', '#', '3', '5', '#', '#', '6' }; char arr2[] = { '1', '2', '4', '#', '#', '9', '#', '#', '3', '5', '#', '#', '6' }; size_t sz = sizeof(arr) / sizeof(arr[0]); BinaryTree<char> b(arr, sz, '#'); size_t sz2 = sizeof(arr2) / sizeof(arr2[0]); BinaryTree<char> w(arr2, sz2, '#'); cout << b.GetFarthestDistance() << endl; b.PreOrder(); cout << "得到镜像" << endl; b.GetBinaryMirror(); b.PreOrder_Nor(); b.PostOrder(); b.PostOrder_Nor(); cout << w.GetKLevelNode(3) << endl; cout << "b是否是完全二叉树" << endl << b.IsCompleteBinaryTree() << endl; w.PostOrder_Nor(); cout << "w的距离最大" << endl; cout << w.GetFarthestDistance() << endl; cout << "树的高度是：" << endl << b.Height() << endl; cout << "w是否是完全二叉树" << endl << w.IsCompleteBinaryTree() << endl; system("pause"); } int main() { test(); system("pause"); }