二叉树面试题

1.根据前序遍历序列和中序遍历序列求一棵二叉树。

那么我们就是很容易的写出完整代码。

[html]  view plain  copy   template<typename T>   struct BinaryTreeNode   {       T _data;       BinaryTreeNode<T>* _left;       BinaryTreeNode<T>* _right;       BinaryTreeNode(const T& data = T())          :_data(data)          ,_left(NULL)          ,_right(NULL)       {}   };   template<typename T>   class RebuildTree   {      typedef BinaryTreeNode<T> Node;   public:       RebuildTree(T* pre,T* in,size_t size)       {          assert(pre && in);          _root = new Node(pre[0]);          _CreateTree(pre,in,size,_root);       }       void PreOrder()       {          _PreOrder(_root);       }   protected:       void _CreateTree(T* pre,T* in,size_t size,Node*& root)       {          if(size <= 0)              return;          if(root == NULL)              root = new Node(pre[0]);          int index = 0;          for(index = 0; index < size; ++index)          {              if(pre[0] == in[index])//根节点                  break;          }          int leftNum = index;          int rightNum = size - leftNum - 1;           _CreateTree(pre+1,in,leftNum,root->_left);          _CreateTree(pre+index+1,in + index + 1,rightNum,root->_right);       }       void _PreOrder(Node* root)       {          if(NULL == root)              return;          cout<<root->_data<<" ";          _PreOrder(root->_left);          _PreOrder(root->_right);       }   private:       Node* _root;   };   void TestRebuildTree()   {       int pre[] = {1,2,3,4,5,6};       int in[] = {3,2,4,1,6,5};       RebuildTree<int> rt(pre,in,6);       rt.PreOrder();  

}   2.判断一棵二叉树是否是完全二叉树。 思路：层序遍历（将空节点也入队），如果遇到空节点时，队列中还有非空结点，那么就说明不是完全二叉树；如果队列中没有非空结点，那么就是完全二叉树。     bool _IsComplete_2()       {           if(_bt._root == NULL)               return false;           queue<Node*> q;           q.push(_bt._root);           while(!q.empty())           {               Node* top = q.front();               if(top != NULL)               {                   q.pop();                   q.push(top->_left);                   q.push(top->_right);               }               else                   break;           }           //计算队列中非空节点的个数           int i = 0;           while(i++ < q.size())           {               if(q.front() != NULL)                   return false;               else                   q.pop();           }           return true;       }   4.求两个结点的最低公共祖先。 分析：对于这样的问题，就要考虑到各种情况。 1)二叉搜索树的情况：根据二叉搜索树的性质（左孩子的值小于根节点的值，右孩子的值大于根节点的值），如果给定的两个结点的值都大于当前子树的根节点的值，那么这两个结点必然都位于当前子树的右子树上；如果给定的两个结点的值都小于当前子树的根节点，那么这两个结点都在当前子树的左子树上；如果给定的两个结点的值一个大于当前子树的根节点的值，一个小于当前子树的根节点的值，那么当前的子树的根节点就是所要找的最低公共祖先。 完整代码： template<typename T>   class CommonParent   {       typedef TreeNode<T> Node;   public:       CommonParent(T* array,size_t size,const T& invalid)          :_bt(array,size,invalid)       {}       //是二叉搜索树的情况       Node*  LeastCommonParent(const T& a, const T& b)       {          if(_bt._root == NULL || (_bt.Find(a)&& _bt.Find(b)))          {              return  NULL;          }          Node* cur = _bt._root;          //当前子树的根的值比两个节点的值都要大，说明两个节点都在当前根的左子树上          if(cur->_data > a && cur->_data > b)          {              cur = cur->_left;          }          //当前子树的根的值比两个节点的值都要小，说明两个节点都在当前根的右子树上          else if(cur->_data < a && cur->_data < b)          {              cur = cur->_right;          }          else              return cur;       }   private:       BinaryTree<T> _bt;   };   void TestCommonParent_1()   {       int array[] = {8,7,5,'#','#','#',12,11,'#','#',18};       CommonParent<int> cp(array,11,'#');       TreeNode<int>* ret = cp.LeastCommonParent(7,20);       if(ret == NULL)          cout<<"没有公共祖先";       else          cout<<ret->_data<<endl;   }   2)非搜索树的情况： a、树中有指向父节点的指针：从给定的两个结点开始，反向遍历，找到路径。。然后求出两个链表的第一个公共结点。 b、树中没有指向父节点的指针：从根节点分别找出给定结点的路径，然后求出两个链表的最后一个交点。这样做的话，就需要遍历树一次，遍历两个链表。下边提供一种新的高效的方法~~ 代码： bool GetNodePath1(Node *root,int data,list<Node*>&path) { if (root == NULL) return NULL; path.push_back(root); if (root->_value == data) return true; else { bool found = false; found = GetNodePath(root->_lchild,data,path); if (!found) { found = GetNodePath(root->_rchild,data,path); } if (!found) path.pop_back(); return found; } } Node* GetLastComNode2( list<Node*>l1, list<Node*>l2) { list<Node*>::iterator it1 = l1.begin(); list<Node*>::iterator it2 = l2.begin(); Node* Plist = NULL; while ((it1 != l1.end()) && (it2 !=l2.end())) { if (*it1 == *it2) Plist = *it1; it1++; it2++; } return Plist; } Node* GetComParent(int data1,int data2) { if (!GetNodePath1(_root, data1, path1)) { IsExistData1 = false; return NULL; } if (!GetNodePath1(_root, data1, path2)) { IsExistData2 = false; return NULL; } return GetLastComNode2(path1,path2); } 5.将二叉搜索树改为有序的双向链表。 分析：二叉搜索树的中序遍历就是一个升序序列。像前边线索化二叉树那样，如果可以让一个结点的left指向其中序遍历的前一个结点（当该结点不是第一个结点的时候），将该结点的right指向其后序遍历的下一个结点。遍历完了之后，我们还是需要沿着树的方向，一直向左走，找到链表的第一个结点。 代码： [cpp]  view plain  copy   void _ToList(Node* root,Node*& prev)       {           if (root == NULL)               return;           _ToList(root->_left,prev);           root->_left = prev;           if (prev)               prev->_right = root;            prev = root;           _ToList(root->_right,prev);       }   给出完整代码 #include<assert.h> template<class T> struct TreeNode { TreeNode(const T& value = T()) :_value(value) , _lchild(0) , _rchild(0) {} T _value; TreeNode <T>*_lchild; TreeNode <T>*_rchild; int nMaxLeft; int nMaxRight; }; bool IsExistData1 = true; bool IsExistData2 = true; template<class T> class Binarytree { public: typedef TreeNode<T> Node; Binarytree() :_root(NULL) {} Binarytree(const T*a,size_t size,const T&invalid) { assert(a); size_t index = 0; _root = CreatTree(a,size,invalid,index); } Binarytree(const Binarytree<T> &b) { _root = _Copy(b._root); } Binarytree& operator=(const Binarytree<T> &b) { if (this != &b) { Node* tmp = _Copy(b._root); Destroy(_root); _root = tmp; } return *this; } ~Binarytree() { Destroy(_root); _root = NULL; } void _prevPrint() { cout << "先序遍历"<<" "; preorder(_root); cout << endl; } void levePrint() { cout << " 层序遍历" << " "; leveorder(_root); } size_t _size() { return Size(_root); } size_t _depth() { return depth(_root); } size_t _Getleaf() { return Getleaf(_root); } size_t _Getllevesize(int k) { return getklevesize(_root,k); } bool _IsComplete_2() { if (_root == NULL) return false; queue<Node*> q; q.push(_root); while (!q.empty()) { Node* top = q.front(); if (top != NULL) { q.pop(); q.push(top->_lchild); q.push(top->_rchild); } else break; } //计算队列中非空节点的个数 int i = 0; while (i++ < q.size()) { if (q.front() != NULL) return false; else q.pop(); } return true; } list<Node*> path1; list<Node*> path2; bool _IsComplete() { if (_root == NULL) return false; queue<Node*>q; q.push(_root); while (!q.empty()) { Node*top = q.front(); if (top != NULL) { q.pop(); q.push(top->_lchild); q.push(top->_rchild); } else break; } int i = 0; while (i < q.size()) { if (q.front() != NULL) return false; q.pop(); i++; } return true; } //求两个节点最近的父节点 bool GetNodePath1(Node *root,int data,list<Node*>&path) { if (root == NULL) return NULL; path.push_back(root); if (root->_value == data) return true; else { bool found = false; found = GetNodePath(root->_lchild,data,path); if (!found) { found = GetNodePath(root->_rchild,data,path); } if (!found) path.pop_back(); return found; } } Node* GetLastComNode2( list<Node*>l1, list<Node*>l2) { list<Node*>::iterator it1 = l1.begin(); list<Node*>::iterator it2 = l2.begin(); Node* Plist = NULL; while ((it1 != l1.end()) && (it2 !=l2.end())) { if (*it1 == *it2) Plist = *it1; it1++; it2++; } return Plist; } Node* GetComParent(int data1,int data2) { if (!GetNodePath1(_root, data1, path1)) { IsExistData1 = false; return NULL; } if (!GetNodePath1(_root, data1, path2)) { IsExistData2 = false; return NULL; } return GetLastComNode2(path1,path2); } bool GetNodePath(Node* root,int data,list<Node*>&path) { if (root == NULL) return false; path.push_back(root); if (root->_value == data) return true; else { bool found = false; found= GetNodePath(root->_lchild,data,path); if (!found) found=GetNodePath(root->_rchild, data, path); if (!found) path.pop_back(); return found; } } Node*GetLastComNode(const list< Node*> &list1, const list<Node*> &list2) { list<Node *>::const_iterator it1 = list1.begin(); list<Node *>::const_iterator it2 = list2.begin(); Node *pLast = NULL; while (it1 != list1.end() && it2 != list2.end()) { if (*it1 == *it2) pLast = *it1; break; it1++; it2++; } return pLast; } //3.组合1,2，返回公共结点； Node *GetLastCommParent(Node *root, int data1, int data2) { if (NULL == root) return NULL; //得到路径 if (!GetNodePath(root, data1, path1)) { IsExistData1 = false; return NULL; } if (!GetNodePath(root, data2, path2)) { IsExistData2 = false; return NULL; } //得到最低公共祖先； return GetLastComNode(path1, path2); } Node* GetCommentParent(int data1,int data2) { return GetLastCommParent(_root,data1,data2); } void _ToList(Node* root, Node*& prev) { if (root == NULL) return; _ToList(root->_lchild, prev); root->_lchild = prev; if (prev) prev->_rchild = root; prev = root; _ToList(root->_rchild, prev); } Node* Tolist() { Node*prev = NULL; _ToList(_root,prev); while (prev) { if (prev->_lchild == NULL) return prev; prev = prev->_lchild; } } protected: void Destroy(Node *&root) { if (root) { Destroy(root->_lchild); Destroy(root->_rchild); delete root; root = NULL; } } void leveorder(Node* root) { queue<Node*> q; if (root) { q.push(root); } while (!q.empty()) { Node* front = q.front(); q.pop(); cout << front->_value << " "; if (front->_lchild) { q.push(front->_lchild); } if (front->_rchild) { q.push(front->_rchild); } } } void preorder(Node *root) { if (root) { cout << root->_value << " "; preorder(root->_lchild); preorder(root->_rchild); } } Node* CreatTree(const T*a,size_t size,const T& invalid,size_t &index) { assert(a); Node*root = NULL; if (a[index]!=invalid&&(index<size)) { root = new Node(a[index]); root->_lchild = CreatTree(a, size, invalid, ++index); root->_rchild = CreatTree(a, size, invalid, ++index); } return root; } Node* _Copy(Node *root) { Node*tmp = NULL; if (root) { tmp = new Node(root->_value); tmp->_lchild = _Copy(root->_lchild); tmp->_rchild = _Copy(root->_rchild); } return tmp; } size_t Size(Node*root) { size_t count = 0; if (root == NULL) { return 0; } else { count = Size(root->_lchild) + Size(root->_rchild) + 1; } return count; } size_t depth(Node* root) { if (root==NULL) { return 0; } return depth(root->_lchild) > depth(root->_rchild) ? (depth(root->_lchild) + 1) : (depth(root->_rchild) + 1); } size_t Getleaf(Node*root) { if (root == NULL) return 0; if (root->_lchild == NULL&&root->_rchild == NULL) return 1; else return Getleaf(root->_lchild) + Getleaf(root->_rchild); } size_t getklevesize(Node*root,size_t k) { assert(k>=1); size_t count = 0; if (root == NULL) return 0; if (k == 1) { count++; } else { count=getklevesize(root->_lchild, k-1) + getklevesize(root->_rchild,k-1); } return count; } protected: Node* _root; }; int main() { int arr1[] = {30,10,9,'#','#',11,'#','#',50,49,'#','#',51,'#','#'}; int arr[] = {1,2,3,'#','#','#',5,6,'#','#','#'}; char invalid = '#'; Binarytree<int> b(arr1,sizeof(arr)/arr[0],invalid); b._prevPrint(); cout << endl; b.levePrint(); cout << endl; cout << b._size(); cout << endl; cout << b._depth(); cout << endl; cout << b._Getleaf(); cout << endl; cout<<b._Getllevesize(2); cout << endl; if (b._IsComplete()) { printf("是完全二叉树\n"); } //if (IsExistData1 == true && IsExistData2==true) //cout << b.GetComParent(5,6)->_value<<" "; TreeNode<int>* Prev = NULL; Prev=b.Tolist(); TreeNode<int>* Prev1 = Prev; while (Prev1->_rchild != NULL) { cout << Prev1->_value << " "; Prev1 = Prev1->_rchild; } cout << endl; }