数据结构 二叉树问题

#include
#include
#include

using namespace std;
class Nodes
{
public:

   int val;

   Nodes *left;

   Nodes *right;

   Nodes(int tmp =0):val(tmp),left(nullptr),right(nullptr)

   {


   }

};
Nodes * CreateTree( vector &nodes);
void LeftAndRight(vector &nodes,vector &leftrst,vector &rightrst);
void OutPut(Nodes *pppNode);
////////////////////////////////////////////////////////////////////////
int main(int argc, char *argv[])
{

   int nodeNum;

   cin>>nodeNum;


   vectorData;

   //int *rslt = new int[nodeNum]{0};

   int tmp;

   for(int i=0;i
   {

       cin>>tmp;

       Data.push_back(tmp);

   }

   Nodes *  pNodes{CreateTree( Data)};//根据值域构造树

   OutPut(pNodes);//根据树输出先根遍历的结果

   return 0;
}
////////////////////////////////////////////////////////////////////////
Nodes * CreateTree( vector &nodes)
{

   if(nodes.size() == 0)return nullptr;

   if(nodes.size() == 1)

   {

       Nodes *root{new Nodes(nodes.at(0))};

       return root;

   }

   if(nodes.size() == 2)

   {

       Nodes *root{new Nodes(nodes.at(0))};

       Nodes *leftnode{new Nodes(nodes.at(1))};

       root->left = leftnode;//如果只有2个节点一定是根节点和左节点，完全二叉树的定义

       return root;

   }

   if(nodes.size() == 3)

   {

       Nodes *root{new Nodes(nodes.at(0))};

       Nodes *leftnode{new Nodes(nodes.at(1))};

       Nodes *rightnode{new Nodes(nodes.at(2))};

       root->left = leftnode;

       root->right = rightnode;

       return root;

   }

   //如果大于三个节点就开始分解递推

   Nodes *root{new Nodes(nodes.at(0))};

   vectorleftnodes;//左子树的值域

   vectorrightnodes;//右子树的值域

   LeftAndRight(nodes,leftnodes,rightnodes);//从总值域里面分出左值域和右值域

   root->left = CreateTree( leftnodes);//根据值域构造左右子树

   root->right = CreateTree( rightnodes);



   return root;//返回整棵树
}
////////////////////////////////////////////////////////////////////////
void LeftAndRight(vector &nodes,vector &leftrst,vector &rightrst)
{//将值分为左子树的值和右子树的值

   int layer = static_cast(log2(static_cast(nodes.size())))  + 1;//树的层数

   for(int i=2;i<=layer;i++)

   {

       int layertotal = pow(2,i-2);//当前所在层上的所有节点数

       for(int j=0;j
       {

           if(pow(2,i-1)-1+j >nodes.size()-1){break;}//这一层上左边的节点存到左子树的值域里面

           leftrst.push_back(nodes.at(pow(2,i-1)-1+j));//因为不是满二叉树，所以有可能这一层上的节点数不是满的，所以需要额外检查一下超过总个数没有

       }

       for(int k=layertotal;k
       {

           if(pow(2,i-1)-1+k >nodes.size()-1){break;}//这一层上右边的节点存到右子树的值域里面

           rightrst.push_back(nodes.at(pow(2,i-1)-1+k));//因为不是满二叉树，所以有可能这一层上的节点数不是满的，所以需要额外检查一下超过总个数没有

       }

   }
}
void OutPut(Nodes *pppNode)
{

   if(pppNode == nullptr)

       return ;

   cout<val<<" ";//输出根节点的值

   OutPut(pppNode->left);//输出根节点的左子树的值序列

   OutPut(pppNode->right);//输出根节点的右子树的值序列

}
============分割线=====================

这不是最好的做法，最好的做法是直接输出结果，不用构造树。

其实只用void LeftAndRight（）这个函数就已经解决问题了，你可以自己试一下，我把数都存到vector里面了，其实这个时候直接输出就是结果了。

我是很久没写二叉树的代码了，所以练了一下构造树。

const int MaxSize = 1000;
void preorder(int *tree, int size, int root)
{
if(root >= size)
return;
int lchild = root * 2 + 1, rchild = root * 2 + 2;
printf("%d ", tree[root]);
preorder(tree, size, lchild);
preorder(tree, size, rchild);
}
void main( )
{
int tree[MaxSize], n, i, root = 0;
scanf("%d", &n);
for(i = 0; i < n; i++)
scanf("%d", &tree[i]);
printf("\n");
preorder(tree, n, root);
}