第一题：
//判断二叉树是否为完全二叉树，完全二叉树的定义为，前n-1层都是满的，第n层如有空缺，//则是缺在右边即，第n层的最右边的节点，它的左边是满的，右边是空的//方法一：//这个问题的描述已经提示了解法，采用广度优先遍历，从根节点开始，入队列，如果队列不为空，//循环，遇到第一个没有左儿子，或者右儿子的节点设置标志位，如果之后在遇到有左或者右儿子的//节点那么，这不是一颗完全二叉树//这个方法需要遍历整棵树，复杂度为O(n),n为节点的总个数#pragma oncestruct Node{ int _data; struct Node* _left; struct Node* _right; Node(int data) :_data(data) , _left(NULL) , _right(NULL) {}};//class BinaryTree//{//public:// BinaryTree(int *array,const int size,const int invalid)// :_root(NULL)// {// int index=0;// _root = _Create(array, size, invalid,index);// }//protected:// Node* _Create(int *array, const int size, const int invalid, int &index)// {// assert(array);// if (index < size&&a[index] != invalid)// {// Node *cur = new Node(a[index]);// cur->_letf = _Create(array, size, invalid, ++index);// cur->_right = _Create(array, size, invalid, ++index);// return cur;// }// return NULL;// }//protected:// Node *_root;//};Node* _Create(int *array, const int size, const int invalid, int &index) { assert(array); if (index < size&&array[index] != invalid) { Node *cur = new Node(array[index]); cur->_left = _Create(array, size, invalid, ++index); cur->_right = _Create(array, size, invalid, ++index); return cur; } return NULL; }//实现广度遍历需要队列queue myqueue;//第n层最右节点的标志bool leftMost = false;bool ProcessChild(Node *child){ if (child) { if (!leftMost) { myqueue.push(child); } else { return false; } } else { leftMost = true; } return true;}bool IsCompleteBinaryTree(Node *root){ //空树也是完全二叉树 if (!root) { return true; } //首先根节点入队列 myqueue.push(root); while (!myqueue.empty()) { Node* node = myqueue.front(); myqueue.pop(); //处理左节点 if (!ProcessChild(node->_left)) { return false; } if (!ProcessChild(node->_right)) { return false; } } //广度优先遍历完毕，是完全二叉树 return true;} int depth(Node *root){ if (root == NULL) return 0; int leftdepth = depth(root->_left); int rightdepth = depth(root->_right); return(leftdepth > rightdepth ? leftdepth : rightdepth) + 1;}void question1Test(){ //int array[13] = { 10, 6, 4, '#', '#', 8, '#', '#', 14, 12, '#', '#', 16 }; int array[11] = { 10, 6, 4, '#', '#', 8, '#', '#', 14, '#', 16 }; int index = 0; Node* root = _Create(array, sizeof(array) / sizeof(int), '#',index); cout << IsCompleteBinaryTree(root) << endl;} 第二题
//题目：将二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的节点，//只能调整树中节点指针的指向//解析：进行中序遍历，改变指针方向struct Node{ int _data; Node* _left; Node* _right; Node(int data) :_data(data) , _left(NULL) , _right(NULL) {}};class BinaryTree{public: BinaryTree(int *array, const int size, const int invalid) :_root(NULL) { int index = 0; _root = _Create(array, size, invalid,index); } Node* _Create(int *array, const int size, const int invalid, int &index) { assert(array); if (index < size&&array[index] != invalid) { Node *cur = new Node(array[index]); cur->_left = _Create(array, size, invalid, ++index); cur->_right = _Create(array, size, invalid, ++index); return cur; } return NULL; } void Tree_To_Dlist() { Node *prev = NULL; _Tree_To_Dlist(_root,prev); while (_root->_left) { _root = _root->_left; } } void Print_DList() { Node *cur = _root; while (cur) { cout << cur->_data << endl; cur = cur->_right; } }protected: void _Tree_To_Dlist(Node*root,Node*& prev) { if (root == NULL) return; _Tree_To_Dlist(root->_left,prev); root->_left = prev; if (prev) { prev->_right = root; } prev = root; _Tree_To_Dlist(root->_right, prev); /*stack q; Node* cur = _root; while (cur) { q.push(cur); _root = cur; cur = cur->_left; } Node* prev = NULL; while ((cur != NULL) || (!q.empty())) { while (cur) { q.push(cur); cur = cur->_left; } while (!q.empty()) { cur = q.top(); q.pop(); cur->_left = prev; if (prev != NULL) { prev->_right = NULL; } prev = cur; if (cur->_right) { cur = _root->_right; } } }*/ }protected: Node *_root;};void question2Test(){ int array[13] = { 10, 6, 4, '#', '#', 8, '#', '#', 14, 12, '#', '#', 16 }; //int array[11] = { 10, 6, 4, '#', '#', 8, '#', '#', 14, '#', 16 }; int index = 0; BinaryTree bt(array, sizeof(array) / sizeof(int), '#'); bt.Tree_To_Dlist(); bt.Print_DList();}