数据结构二叉树问题

n个结点的完全二叉树按顺序存储在一维数组中，设计一个算法，实现对此二叉树的先序遍历。

输入描述

首先输入整数n,随后输入n个正整数

输出描述

二叉树先序遍历的结果，输出数据之间空一格。

输入样例

4
2 4 3 1

输出样例

2 ...n个结点的完全二叉树按顺序存储在一维数组中，设计一个算法，实现对此二叉树的先序遍历。

输入描述

首先输入整数n,随后输入n个正整数

输出描述

二叉树先序遍历的结果，输出数据之间空一格。

输入样例

4
2 4 3 1

输出样例

2 4 1 3展开

qq906237201 · 2018-4-30 02:31:01

#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>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

laughlee7468 · 2018-4-30 02:31:00

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);
printf("\n");
preorder(tree, n, root);
}

数据结构 二叉树问题

2 个回复

数据结构二叉树问题