/*
关于非线性的数据结构当然树形结构最重要，而树里面又属二叉树最重要，
所以在后面将列出二叉树的各种使用方法，包括基本的遍历，和我在一些
资料上看到的关于二叉树的面试题型。至于一些很高级的树形结构，如平
衡树，还有线索树等，就暂时不写出来，先完成最基本的，再一点点的加
*/
#include <stdio.h>
#include <stdlib.h>
//typedef void * ElemType;
typedef int ElemType;
typedef struct TreeNode
{
ElemType m_nValue;
struct TreeNode *m_pLeft;
struct TreeNode *m_pRight;
}BinaryTreeNode;
/*
二叉树主要的难点是遍历
基本上所有的算法都是基于二叉树的遍历的
至于创建二叉树就需要在输入的时候把线性的结构转换成非线性的
用输入的方式创建二叉树
*/
//将输入独立起来，
BinaryTreeNode * CreateTree(BinaryTreeNode *bTree)
{
int input;
scanf("%d", &input);//按先序建立二叉树
if (input == 0)
{
bTree = NULL;//置为NULL后结束
return bTree;
}
bTree = (BinaryTreeNode *)malloc(sizeof(BinaryTreeNode));
bTree->m_nValue = input;
bTree->m_pLeft = CreateTree(bTree->m_pLeft);
bTree->m_pRight = CreateTree(bTree->m_pRight);
return bTree;
}
//三种递归遍历方法
void Preorder(BinaryTreeNode *bTree)//这个是先序遍历，先根，左子树，右子树
{
if (bTree != NULL)
{
printf("%d ", bTree->m_nValue);
Preorder(bTree->m_pLeft);
Preorder(bTree->m_pRight);
}
}
void Inorder(BinaryTreeNode *bTree)//中序遍历，左子树，根，右子树
{
if (bTree != NULL)
{
Inorder(bTree->m_pLeft);
printf("%d ", bTree->m_nValue);
Inorder(bTree->m_pRight);
}
}
void Postorder(BinaryTreeNode *bTree)//后序遍历，左子树，右子树，根
{
if (bTree != NULL)
{
Postorder(bTree->m_pLeft);
Postorder(bTree->m_pRight);
printf("%d ", bTree->m_nValue);
}
}
int main()
{
BinaryTreeNode *bTree;
bTree = (BinaryTreeNode *)malloc(sizeof(BinaryTreeNode));
bTree = CreateTree(bTree);
printf("先序遍历结果为：\n");
Preorder(bTree);
printf("\n");
printf("中序遍历结果为：\n");
Inorder(bTree);
printf("\n");
printf("后序序遍历结果为：\n");
Postorder(bTree);
printf("\n");
return 0;
system("pause");
}
