©2020-2024 ioDraw All rights reserved
/************************************************************************/ /*
5、怎样编写一个程序，把一个有序整数数组放到二叉树中 */
/************************************************************************/
//不太明白，二叉树有没有建好 //二叉树建好了，那只要把数组的值放进去就可以了。中序遍历二叉树并赋值 //二叉树建好了 class BinaryNode {
public: BinaryNode(int data = 0, BinaryNode *left = NULL, BinaryNode* right =
NULL) : m_data(data), m_left(left), m_right(right) {} int m_data; BinaryNode *
m_left; BinaryNode * m_right; }; void arrToBinaryTreeRecursive(int * iArr,
BinaryNode* root, int length, int& begPos) { if(!root || begPos >= length) {
if(root && begPos >= length) begPos++; return; } arrToBinaryTreeRecursive(iArr,
root->m_left, length, begPos); if(begPos >= length) { cout <<"树的节点大于数组元素个数" <<
endl; begPos++; cout << "begpos = " << begPos << endl; return; } else
root->m_data = iArr[begPos++]; arrToBinaryTreeRecursive(iArr, root->m_right,
length, begPos); return; } //0成功，-1树的节点多余iarr，+1iarr节点多余树的节点 int
arrToBinaryTree(int * iArr, BinaryNode* root, int length) { if(!iArr || length
<= 0) return false; int begpos = 0; arrToBinaryTreeRecursive(iArr, root,
length, begpos); if(begpos > length) return -1; else if(begpos < length) return
1; else return 0; } //二叉树没建好，可以建立一个数组元素大小的满二叉树，放入数组元素 //或者边建立边赋值,
数组中间取一个值作为根节点，递归 //题目的意思应该是没建好二叉树吧! typedef BinaryNode* BinaryTree; BinaryNode*
buildBinaryTree( int * iArr, int l, int h) { if(l > h) return NULL; int mid =
(l + h) / 2; BinaryNode* root = new BinaryNode(iArr[mid]); root->m_left =
buildBinaryTree( iArr, l, mid - 1); root->m_right = buildBinaryTree( iArr, mid
+ 1, h); return root; } //中序二叉树 void inOrderBinaryTree(BinaryNode* root) {
if(root) { inOrderBinaryTree(root->m_left); cout << root->m_data << "\t";
inOrderBinaryTree(root->m_right); } } /*测试部分*/ //初始化数组 void initArr(int * iArr,
int size) { int range = 10 * size; //从[0, range)中选择size个不重复的随机数 int selected =
0; for(int i = 0; i < range; ++i) { if(rand() % (range - i) < size - selected)
iArr[selected++] = i; } qsort(iArr, size, sizeof(int), iCompare); } void
deleteTree(BinaryNode * root) { if(root) { deleteTree(root->m_left);
deleteTree(root->m_right); delete root; } } void testOfBuildTree() {
/*生成size个有序数组*/ const int size = 10; int iArr[size] ; initArr(iArr, size); cout
<< "iarr: " << endl; showArr(iArr, size); /*建立查询二叉树*/ BinaryNode * root =
buildBinaryTree(iArr, 0, size -1); cout << "binarytree:" << endl;
inOrderBinaryTree(root); /*二叉树存在，转化为二叉树*/ //数组多余二叉树或少于二叉树 cout << "test of arr
to binary tree: " << endl; //const int size1 = size +1; const int size1 = size
-1; int iArr1[size1]; initArr(iArr1, size1); showArr(iArr1, size1); int flag =
arrToBinaryTree(iArr1, root, size1); inOrderBinaryTree(root); if(flag < 0) cout
<< "树的节点多于数组节点!" << endl; else if(flag > 0) cout << "数组的节点多余树的节点" << endl;
//释放树, 后序释放 deleteTree(root); }