二叉树的定义

二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树

二叉树的性质

二叉树遍历

二叉树有三种遍历方式，分别为先序遍历、中序遍历、后序遍历

先序遍历：

    （1）先访问根节点。

    （2）再访问左子树。

    （3）最后访问右子树。

中序遍历：

    （1）先访问左子树。

    （2）再访问根节点。

    （3）最后访问右子树。

后序遍历：

    （1）先访问左子树。

    （2）再访问右子树。

    （3）最后访问根节点。

比如如下的二叉树

先序遍历结果为 ABCDEFG

中序遍历结果为 CBEDAFG

后序遍历结果为 CEDBGFA

二叉树结构

typedef struct binarytreenode
{
    int data;
    struct binarytreenode *Lnode;
    struct binarytreenode *Rnode;
} BiTNode,*BiTree;

创建二叉树

void CreateBiTree(BiTree *T)
{
    char ch;
    scanf("%c",&ch);
    if(ch == '#')
    {
        *T = NULL;
    }
    else
    {
        *T = (BiTree)malloc(sizeof(BiTNode));
        if(!*T){return;}
        (*T)->data = ch;
        CreateBiTree(&(*T)->Lnode);
        CreateBiTree(&(*T)->Rnode);
    }
}

三种遍历

//二叉树的先序遍历
void PreOrderTraverse(BiTree T)
{
    if(T == NULL) return;
    printf("%c ",T->data);
    PreOrderTraverse(T->Lnode);
    PreOrderTraverse(T->Rnode);
}

//二叉树的中序遍历
void InOrderTraverse(BiTree T)
{
    if(T == NULL) return;
    InOrderTraverse(T->Lnode);
    printf("%c ",T->data);
    InOrderTraverse(T->Rnode);
}

//二叉树的后序遍历
void PostOrderTraverse(BiTree T)
{
    if(T == NULL) return;
    PostOrderTraverse(T->Lnode);
    PostOrderTraverse(T->Rnode);
    printf("%c ",T->data);
}

//二叉树的层次遍历
void LevelOrderTraverse(BiTree T)
{
    if(T == NULL) return;
    Q_Push(T);      //取树的第一个节点加入队列
    while(!Q_empty()){  //树不为空时
        BiTree tmp = Q_Pop(T); //删除队列的第一个元素
        printf("%c ",tmp->data);
        if(tmp->Lnode)
            Q_Push(tmp->Lnode); //取队列的左子树
        if(tmp->Rnode)
            Q_Push(tmp->Rnode);//取队列的右子树
    }
}

层次遍历

/* 完整代码 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define MaxSize 100
 
struct tree {
    int data;
    struct tree* left;
    struct tree* right;
};
 
typedef struct queue{
    struct tree* numQ[MaxSize];
    int front;
    int rear;
}Queue;
 
Queue Q;
 
void initilize() { //初始化队列
    Q.front = 0;
    Q.rear = 0;
}
 
void Push(struct tree* root) { //入队
    Q.numQ[++Q.rear] = root;
}
 
struct tree* Pop() { //出队
    return Q.numQ[++Q.front];
}
 
int empty() { //判断对列是否为空
    return Q.rear == Q.front;
}
 
struct tree* creatTree (struct tree* root) {
    int value;
    scanf("%d", &value);
    if (value == -1)
        return NULL;
    root = (struct tree*)malloc(sizeof(struct tree));
    root->data = value;
    printf("请输入%d的左子树：", root->data);
    root->left = creatTree(root->left);
    printf("请输入%d的右子树：", root->data);
    root->right = creatTree(root->right);
    return root;
}
 
void LevelOrderTraversal (struct tree* root) { //二叉树的层次遍历
    struct tree* temp;
    Push(root);
    while (!empty()) {
        temp = Pop();
        printf("%d ", temp->data);  //输出队首结点
        if (temp->left)     //把Pop掉的结点的左子结点加入队列
            Push(temp->left);
        if (temp->right)    把Pop掉的结点的右子结点加入队列
            Push(temp->right);
    }
}
 
int main() {
    printf("请输入头节点：");
    struct tree* root = creatTree(root);
    
    initilize();  //初始化队列
    
    LevelOrderTraversal(root);
    putchar('\n');
    
    return 0;
}

完整代码

//#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

#define MaxSize 100

using namespace std;

typedef struct binarytreenode
{
    int data;
    struct binarytreenode *Lnode;
    struct binarytreenode *Rnode;
} BiTNode,*BiTree;

typedef struct queue{
    BiTree numQ[MaxSize];
    int front;
    int rear;
}Queue;

Queue Q;

void Q_initilize()
{
    Q.front = 0;
    Q.rear = 0;
}

void Q_Push(BiTree root)
{
    Q.numQ[++Q.rear] = root;
}

BiTree Q_Pop(BiTree root)
{
    return Q.numQ[++Q.front] ;
}

int Q_empty() { //判断对列是否为空
    return Q.rear == Q.front;
}

void CreateBiTree(BiTree *T)
{
    char ch;
    scanf("%c",&ch);
    if(ch == '#')
    {
        *T = NULL;
    }
    else
    {
        *T = (BiTree)malloc(sizeof(BiTNode));
        if(!*T){return;}
        (*T)->data = ch;
        CreateBiTree(&(*T)->Lnode);
        CreateBiTree(&(*T)->Rnode);
    }
}

//二叉树的先序遍历
void PreOrderTraverse(BiTree T)
{
    if(T == NULL) return;
    printf("%c ",T->data);
    PreOrderTraverse(T->Lnode);
    PreOrderTraverse(T->Rnode);
}
//二叉树的中序遍历
void InOrderTraverse(BiTree T)
{
    if(T == NULL) return;
    InOrderTraverse(T->Lnode);
    printf("%c ",T->data);
    InOrderTraverse(T->Rnode);
}
//二叉树的后序遍历
void PostOrderTraverse(BiTree T)
{
    if(T == NULL) return;
    PostOrderTraverse(T->Lnode);
    PostOrderTraverse(T->Rnode);
    printf("%c ",T->data);
}
//二叉树的层次遍历
void LevelOrderTraverse(BiTree T)
{
    if(T == NULL) return;
    Q_Push(T);
    while(!Q_empty()){
        BiTree tmp = Q_Pop(T);
        printf("%c ",tmp->data);
        if(tmp->Lnode)
            Q_Push(tmp->Lnode);
        if(tmp->Rnode)
            Q_Push(tmp->Rnode);
    }
}

int main()
{
    BiTree T;
    CreateBiTree(&T);
    printf("前序遍历结果为 :\n");
    PreOrderTraverse(T);

    printf("\n\n中序遍历结果为 :\n");
    InOrderTraverse(T);

    printf("\n\n后序遍历结果为 :\n");
    PostOrderTraverse(T);

    printf("\n\n层次遍历结果为 :\n\n");
    LevelOrderTraverse(T);
    return 0;
}

补充：

（1）建立二叉树时，这里是以前序遍历的方式，输入的是扩展二叉树，也就是要告诉计算机什么是叶结点，否则将一直递归，当输入“#”时，指针指向NULL，说明是叶结点。

（2）输入的时候一定要注意因为有缓冲区的原因，用scanf输入的话，一定要把所有要输入的数据一次性输入，再回车

（3）不要输入一个数据回车一次，这样就永远也走不出递归函数了，界面一直停留在输入界面，或者想一个一个输入用cin

如图为扩展二叉树：（前序遍历为：ABC##DE###F#G##）