二叉树的构造与遍历

本文用于二叉树的遍历与构造：

/*
二叉树的构造及遍历

遍历

1
/   \
2     3
/  \   /  \
4567
/  \  /
8 9 10

先序：
1 根  2 左  3 右  （1,2,3,4,5都是根（父节点））
上述序列：1 2 4 8 9 5 10 3 6 7

中序：
1 左 2 根 3 右
序列：8 4 9 2 10 5 1 6 3 7


后序：
1 左 2 右 3 根
序列：8 9 4 10 5 2 6 7 3 1









*/

//二叉树链式存储的实现
#include<iostream>
#include<cstring>
#include <vector>
using namespace std;

struct TreeNode
{
char val;
TreeNode *left;
TreeNode *right;
TreeNode(char x) :val(x), left(nullptr), right(nullptr) {}
};


class Tree
{
private:
int n;//用于记录树节点的总个数
int n1;//输入的字符个数
TreeNode *temp[1000];//用于临时替换的
public:
TreeNode *Root;//根
Tree() //初始化树
{
TreeNode *p;
char str[1000];
int parent = 1, child = 0;
cout << "请输入字符（例如1#2#3#4#5）:";
cin.getline(str,1000);

n1 = strlen(str);
n = 0;

for (int i = 0; i < n1; i++)
{
if (str[i] != '#')
{
p = nullptr;
n++;
p = new TreeNode(str[i]);
}
child++;
temp[child] = p;
if (child == 1) { Root = p; }
else
{
if ((p != nullptr) && (child % 2 == 0))
{
temp[parent]->left = p;
}
if ((p != nullptr) && (child % 2 == 1))
{
temp[parent]->right = p;
}
if (child % 2 == 1) //in fact, i+1 can replace child 
{
parent++;
}
}
}
}

~Tree() //释放内存空间
{
for (int i = 0; i < n1; i++)
{
if (temp[i] != nullptr)
delete temp[i];
}
}

void Num_n()
{
cout << " 该二叉树的节点个数：" << n << endl;
}

void preor(TreeNode * t) //先序遍历
{
if (t != nullptr)
{
cout << t->val << ",";
preor(t->left);
preor(t->right);
}
}

void midor(TreeNode * t) //中序遍历
{
if (t != nullptr)
{

midor(t->left);
            cout << t->val << ",";
midor(t->right);
}
}

void posor(TreeNode * t) //后序遍历
{
if (t != nullptr)
{

posor(t->left);

posor(t->right);
            cout << t->val << ",";

}
}

};


int main()
{
Tree tree;
tree.Num_n();
cout << "先序遍历：";
tree.preor(tree.Root);
cout << endl;
cout << "中序遍历：";
tree.midor(tree.Root);
cout << endl;
cout << "后序遍历：";
tree.posor(tree.Root);
cout << endl;

system("pause");
return 0;
}