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

• 树是N个结点的有限集合,N=0时称为空树,任意一颗非空树满足以下条件:
  
  1. 有且只有一个特定的称为根的结点
  2. 当N>1时,其他结点可分为m个互不相交的悠闲集合,其中每个集合本身又是一个棵树,并称为根节点的子树
• 树的定义是递归的,是一种递归的数据结构,树作为一种逻辑结构,同时也是一种分层结构,具有以下两特点:
  
  1. 树的根节点没有前驱结点,除根之外的所有结点有且只有一个前驱结点
  2. 树中所有结点可有零个或多个后继结点
• 树的基本术语
  
  1. 一个结点的子结点个数称为结点的度,树中结点的最大度数称为树的度
  2. 度大于0的称分支结点或非终端结点,度为0的称为叶子结点或终端结点
  3. 结点的层次: 从树根开始数,根节点为第一层,它的子结点为第二层,…
  4. 树的高度:树中最大层数
  5. 路径:两结点之间经过的结点序列
  6. 路径长度:路径上经过的边的个数
• 树的性质:
  
  1. 树中的结点数等于所有结点的度数加1
  2. 度为m的树中第i层至多有m^(i-1)个结点
  3. 高度为h的m叉树至多有(m^h-1)/(m-1)个结点
  4. 具有n个结点的m叉树的最小高度为logm(n(m-1)+1)向上取整
• 二叉树:结点度最大为2的有序树,称为二叉树
• 二叉树性质:
  
  1. 二叉树的第i层最多有2^(i-1)个结点
  2. 非空二叉树的叶子结点树=度为2的结点数+1
  3. 高度为H的二叉树至多有2^H-1个结点
  4. 具有n个结点的完全二叉树的高度为log2N+1(log2N向下取整)
• 特殊二叉树:
  
  • 满二叉树:除叶子结点外,度全为2的二叉树
  • 完全二叉树:结点编号全部连续的二叉树
• 二叉树的创建:可以用顺序表也可用链表,我这用的是后者,在创建二叉树之前,先要将普通二叉树转换为扩展二叉树,然后按照扩展二叉树的前序遍历序列把结点输入控制台
  
  • 怎么转换成扩展二叉树:就是将普通二叉树中的所有结点(包括叶结点)的度都变为2,即为了凑满,在结点原本左右孩子为空的地方输入一个特殊符号当做其孩子,我这为空的地方输入的是#
  • 转换成扩展二叉树时,得到它的前序遍历序列,按照这个序列输入控制台即可创建二叉树了
• 二叉树的四种遍历方式:
  
  1. 前序遍历(DLR):对于每颗子树的遍历顺序均为先访问根结点,再访问左孩子,最后访问右孩子
  2. 中序遍历(LDR):先左孩子,再根结点,最后右孩子
  3. 后序遍历(LRD):先左孩子,再右孩子,最后根结点
  4. 层次遍历:按树的层次遍历,一层访问完再访问下一层,每一层从左至右
• 这里给出前中后序都是基于递归实现的,而层次遍历是通过队列实现的这里给出我对递归的认识
• 递归像剥洋葱,假设我们剥了一层皮后还要洗干净这层皮,这一步才算完成,那么我们在剥完一次皮后,本来按步骤要去洗的,但剥完发现还有一层皮要剥,于是我们就先不洗了,而是立马把新出现的皮给剥了,之后同样看到皮就一路剥下去,每层皮洗的动作都先延后,直到剥完最后一层皮,发现没皮可剥了,那我们就把最后一层皮拿去洗,这样我们对最后一层皮的处理就彻底完成了,完成后这层皮后出现再你手里的就是倒数第二层皮,然后你那它去洗,则第二层皮的处理就完成了,紧接着去洗倒数第三层…依次类推,直到洗好第一层皮那么整个动作就完成了.

二叉树的链式创建及前中后序层次遍历代码实现

#include <iostream>
#include <stdlib.h>
#include <malloc.h>
#define maxSize 100
typedef struct BTnode { //二叉链表结点
    char data;
    struct BTnode *lchild;
    struct BTnode *rchild;
} BTnode;

void createBTnode(BTnode *&T) {//按前序遍历创建结点 
    char ch;
    scanf("%c",&ch);//这里要先把二叉树转换为扩展二叉树 ,然后把结点按前序遍历输入 
    if(ch=='#') {
        T=NULL;
    } else {
        T=(BTnode *)malloc(sizeof(BTnode)); 
        T->data=ch;
        createBTnode(*&T->lchild);
        createBTnode(*&T->rchild);
    }
}


void preOrderTraversal(BTnode *T) {//前序遍历输出结点 
    if(T!=NULL) {
        printf("%c ",T->data);
        preOrderTraversal(T->lchild);
        preOrderTraversal(T->rchild);
    }

}

void inOrderTraversal(BTnode *T){//中序遍历输出结点 
    if(T!=NULL){
        inOrderTraversal(T->lchild);
        printf("%c ",T->data);
        inOrderTraversal(T->rchild);
    }

} 

void postOrderTraversal(BTnode *T){//后序遍历输出结点 
    if(T!=NULL){
        postOrderTraversal(T->lchild);
        postOrderTraversal(T->rchild);
        printf("%c ",T->data);
    }

}

void level(BTnode *p){//二叉树的层次遍历 
    BTnode *bt[maxSize];
    BTnode *q;
    int front,rear;//建立循环队列 
    front=rear=0;//初始化队列 
    if(p!=NULL){
        rear=(rear+1)%maxSize;
        bt[rear]=p;//根结点入队 
        while(front!=rear){//队不为空时循环 
            front=(front+1)%maxSize;
            q=bt[front];//头结点出队 
            printf("%c ",q->data);//出队就打印 
            if(q->lchild!=NULL){//若出队结点有左孩子则左孩子入队 
                rear=(rear+1)%maxSize;
                bt[rear]=q->lchild;
            }
            if(q->rchild!=NULL){//若出队结点有右孩子则右孩子入队 
                rear=(rear+1)%maxSize;
                bt[rear]=q->rchild;
            }
        }
    }
}
int main() {
    BTnode *T;
    createBTnode(T);

    printf("前序遍历序列为: ");
    preOrderTraversal(T);
    printf("\n");

    printf("中序遍历序列为: ");
    inOrderTraversal(T);
    printf("\n");

    printf("后序遍历序列为: ");
    postOrderTraversal(T);
    printf("\n");

    printf("层次遍历序列为: ");
    level(T);
    printf("\n");
    return 0;
}
/*
    示例输入(注:输入的是扩展二叉树序列):ab#d##c##
*/