二叉树

二叉树的创建和遍历都可以通过递归实现

三种遍历方式的记忆：
前序遍历 根节点==》左节点==》右节点
中序遍历 左节点==》根节点==》右节点
后序遍历 左节点==》右节点==》根节点

无论哪种方式，总是先左在右。

<pre><code>
//创建二叉树
void init(Root& root)
{
string str;
cin >> str;
if( str == "end")
return;
else
{
root = new Node();
root->data = str;
init(root->left);
init(root->right);
}
}
</code></pre>

<pre><code>
//遍历二叉树
//前序遍历
void print_1(Root& root)
{
if(root == NULL)
return ;
cout << root->data;
print_1(root->left);
print_1(root->right);
}
//中序遍历
void print_2(Root& root)
{
if(root == NULL)
return ;
print_2(root->left);
cout << root->data;
print_2(root->right);
}

//后序遍历
void print_3(Root& root)
{
if(root == NULL)
return ;
print_3(root->left);
print_3(root->right);
cout << root->data;
}
</code></pre>