二叉树的创建及前序、中序、后序、层序遍历

二叉树

1.建立二叉树

1.先序中序遍历建立二叉树：
二叉树前序遍历序列中，第一个元素总是树的根节点的值。中序遍历序列中，左子树的节点的值位于根节点的值的左边，右子树的节点的值位于根节点的值的右边。
递归解法：
（1）如果前序遍历为空或中序遍历为空或节点个数小于等于0，返回NULL。
（2）创建根节点。前序遍历的第一个数据就是根节点的数据，在中序遍历中找到根节点的位置，可分别得知左子树和右子树的前序和中序遍历序列，重建左右子树。

2.中序后序遍历建立二叉树：
二叉树中序遍历序列中，左子树的节点的值位于根节点的值的左边，右子树的节点的值位于根节点的值的右边。后序遍历序列中，左子树的节点的值位于右子树节点的值的左边，右子树的节点的值位于根节点的值的左边。
递归解法：
（1）如果中序遍历为空或后序遍历为空或节点个数小于等于0，返回NULL。
（2）创建根节点。后序遍历的最后一个数据就是根节点的数据，在中序遍历中找到根节点的位置，可分别得知左子树和右子树的中序和后序遍历序列，重建左右子树。

typedef int dataType;
typedef struct _treenode
{
    dataType data;
    struct _treenode *lchild;
    struct _treenode *rchild;
}BinTree,*pBinTree;

pBinTree BinaryTreeCreate()//先序遍历创建树
{
    char d;
    pBinTree root = NULL;

    d = getchar();
    if(d == '#')//用 # 表示该结点为NULL
        root = NULL;
    else
    {
        root = (pBinTree)malloc(sizeof(BinTree));
        if(NULL == root)
        {
            perror("BinaryTreeCreate malloc error");
            return NULL;
        }
        root->data = d;
        root->lchild = BinaryTreeCreate();//递归方法创建左右子树
        root->rchild = BinaryTreeCreate();
    }

    return root;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

2.遍历二叉树

1.前序遍历
若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，然后再前序遍历右子树
2.中序遍历
若二叉树为空，则空操作返回，否则先中序遍历左子树，然后访问根结点，然后再中序遍历右子树
3.后续遍历
若二叉树为空，则空操作返回，否则先后续遍历左子树，然后后序遍历右子树，最后再访问根结点
4.层序遍历
若二叉树为空，则空操作返回，否则从树的第一层（根结点）开始访问，从上而下逐层遍历，在同一层，按照从左到右的顺序对结点逐个访问

//前序遍历
1

void PreOrder(pBinTree root)
{
    if(NULL == root)
        return ;
    printf("%c ",root->data);
    PreOrder(root->lchild);//先前序遍历左子树，递归实现逐个结点的先左后右的顺序，先从根结点的左子树切入，一直访问到左子树最底层的树叶
    PreOrder(root->rchild);//后前序遍历右子树
}
//中序遍历
void InOrder(pBinTree root)
{
    if (NULL == root)
        return;
    InOrder(root->lchild);
    printf("%c ", root->data);
    InOrder(root->rchild);

    return;
}
//后序遍历
void PostOrder(pBinTree root)
{
    if (NULL == root)
        return;
    PostOrder(root->lchild);
    PostOrder(root->rchild);
    printf("%c ", root->data);

    return;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

层序遍历需要用到队列的代码，这里可以参考前边的文章 ，需要修改队列的数据结构 http://blog.csdn.net/leumber/article/details/78259911

//层序遍历
void NoOrder(pBinTree root)
{
    BinTree p;
    pLinkQueue Q = LinkQueueCreat();//创建队列
    if(NULL == Q)
    {
        perror("LinkQueueCreat");
        return ;
    }
    LinkQueueEnter(Q,root);//将根结点入队
    while(!LinkQueueEmpty(Q))//判断队列是否为空
    {
        LinkQueueExit(Q,&p);//将队头的结点出队
        printf("%c ", p.data);
        if(p.lchild != NULL)
            LinkQueueEnter(Q,p.lchild);//分别将左右子树入队
        if(p.rchild != NULL)
            LinkQueueEnter(Q,p.rchild);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

main测试函数

int main()
{
    //二叉树
    pBinTree root = BinaryTreeCreate();

    PreOrder(root);
    printf("\r\n");
    InOrder(root);
    printf("\r\n");
    PostOrder(root);
    printf("\r\n");

    printf("NoOrder:\r\n");
    NoOrder(root);
    printf("\r\n");

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

测试结果

                     A
                  /     \
                 B       C
               /  \     / \
             D     E   F    G
            /         /      \
           H         I        J
            \       
             K      

abdh#k###e##cfi###g#j##
a b d h k e c f i g j
h k d b e a i f c g j
k h d e b i f j g c a
NoOrder:
a b c d e f g h i j k
请按任意键继续. . .
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17