欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-05-20 13:51:38
...
  • 树是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##
*/