二叉树的基本操作

时间：2021-04-11 17:32:04

二叉树：

二叉树是树的特殊一种，具有如下特点：1、每个结点最多有两颗子树，结点的度最大为2。2、左子树和右子树是有顺序的，次序不能颠倒。3、即使某结点只有一个子树，也要区分左右子树。

满二叉树：

在一棵二叉树中，如果所有分支结点都有左孩子和右孩子结点，并且叶子结点都集中在二叉树的最下层，这样的树叫做满二叉树

完全二叉树：

若二叉树中最多只有最下面两层的结点的度数可以小于2，并且最下面一层的叶子结点都是依次排列在该层最左边的位置上，则称为完全二叉树

区别：

满二叉树是完全二叉树的特例，因为满二叉树已经满了，而完全并不代表满。所以形态你也应该想象出来了吧，满指的是出了叶子节点外每个节点都有两个孩子，而完全的含义则是最后一层没有满。

二叉树的五个重要性质：

  1. 在二叉树的第i层上最多有2 i-1 个节点 。（i>=1）
  2. 二叉树中如果深度为k,那么最多有2k-1个节点。(k>=1）
  3. n0=n2+1 n0表示度数为0的节点 n2表示度数为2的节点
  4. 在完全二叉树中，具有n个节点的完全二叉树的深度为[log2n]+1，其中[log2n]+1是向下取整。
  5. 若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点：
  1. 若 i=1，则该结点是二叉树的根，无双亲, 否则，编号为 [i/2] 的结点为其双亲结点;
  2. 若 2i>n，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点；
  3. 2i+1>n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子结点。

二叉树的基本操作：

base.h

//base.h
//-----公用的常量和类型----------

#include<iostream>
#include<stdlib.h>
#include<malloc.h>

using namespace std;

//函数结果状态码

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2

typedef int Status;
typedef char TElemType;

biTree.h

//biTree.h
//-----二叉树的基本函数实现------

//---------二叉树的链式存储表示------
typedef struct BiTNode{  //二叉树链表节点
    TElemType  date;  //数据域
    struct BiTNode *lchild, *rchild;  //左右孩子指针
}BiTNode, *BiTree;

//-----基本操作的函数原型说明------------

//构造空二叉树
Status InitBiTree(BiTree &T){
    if(!(T = (BiTNode *)malloc(sizeof(BiTNode))))//开辟节点空间
            exit(OVERFLOW);
    T == NULL;
    return OK;
}

//按先序次序输入二叉树中节点的值（一个字符），@字符表示空树
//构造二叉链表表示的二叉树T
Status CreateBiTree(BiTree &T){
    char ch;
    cin>>ch; //输入字符
    if(ch == '@') //判断输入的是否为@
        T = NULL;  //如果是@，T为空树
    else{
        if(!(T = (BiTNode *)malloc(sizeof(BiTNode))))//开辟节点空间
            exit(OVERFLOW);
        T->date = ch; //生成根节点
        CreateBiTree(T->lchild); //构造左子树
        CreateBiTree(T->rchild); //构造右子树
    }
    return OK;
}//CreateBitree

//销毁二叉树
Status DestroyBiTree(BiTree &T){
    if(T){
        DestroyBiTree(T->lchild);
        DestroyBiTree(T->rchild);
        free(T);
        T = NULL;
    }
    return OK;
}//DestroyBiTree

//判空
Status BiTreeEmpty(BiTree T){
    if(T)
        return FALSE;
    else
        return TRUE;
}//BiTreeEmpty

//递归求树的深度
int BiTreeDepth(BiTree T){
    int ldepth; //用来存放左子树的深度
    int rdepth; //右子树的深度
    if(!T) //树空
        return 0;
    ldepth = BiTreeDepth(T->lchild); //求左子树的深度
    rdepth = BiTreeDepth(T->rchild); //求右子树的深度
    return (ldepth > rdepth) ? (ldepth+1):(rdepth+1);
}//BiTreeDepth

//递归求叶子的个数
int BiTreeLeafCount(BiTree T){
    if(T == NULL)
        return 0;
    if(T->lchild == NULL && T->rchild == NULL)
        return 1;
    return BiTreeLeafCount(T->lchild) + BiTreeLeafCount(T->rchild);
}//BiTreeLeafCount

//求二叉树中节点个数
int NodeCount(BiTree T){
    if(T == NULL)
        return 0;
    return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
}//NodeCount

//求二叉树第K层的节点个数
int GetLevelNums(BiTree T, int k){
    if(T==NULL || k==0)
        return 0;
    if(k == 1)
        return 1;
    //左右子树k-1层节点数的和
    return GetLevelNums(T->lchild, k-1) + GetLevelNums(T->rchild, k-1);
}//GetLevelNums

//先序遍历二叉树
Status PreOrderTraverse(BiTree T){
    if(T){ //判T是否为空树
        cout<<T->date<<" "; //输出T节点的数据
        if(PreOrderTraverse(T->lchild)); //递归遍历左子树
            if(PreOrderTraverse(T->rchild)); //递归遍历右子树
        return ERROR;
    }else{
        return OK;
    }

}//PreOrderTraverse



//中序遍历二叉树
Status InOrderTraverse(BiTree T){
   if(T){
        if(PreOrderTraverse(T->lchild));
        cout<<T->date<<" ";
            if(PreOrderTraverse(T->rchild));
        return ERROR;
    }else{
        return OK;
    }
}//InOrderTraverse


//后序遍历二叉树
Status PostOrderTraverse(BiTree T){
    if(T){
        if(PreOrderTraverse(T->lchild));
            if(PreOrderTraverse(T->rchild));
             cout<<T->date<<" ";
        return ERROR;
    }else{
        return OK;
    }
}//PostOrderTraverse

main.cpp

#include "base.h"
#include "biTree.h"
#include "stack.h" 

//非递归中序遍历二叉树
Status InOrderTraverse_Stack(BiTree T){
    PLinkStack S; //定义一个栈S
    BiTree p = T; //定义一个二叉树节点p = T；
    InitStack_L(&S); //初始化栈S
    while( p || !StackEmpty_L(S)){ //结束条件为二叉树P空且栈S空
        if(p){   //判二叉树p是否为空
            Push_L(S, p);  //根指针进栈遍历左子树
            p = p->lchild; //遍历左子树
        }else{
            Pop_L(S, p); //根指针退栈
            cout<<p->date<<" "; //访问根节点的数据
            p = p->rchild; //遍历右子树
        }//else
    }//while
    return OK;
}//InOrderTraverse_Stack

int main(){

    BiTree T;
    cout<<"先序创建二叉树，请按先序输入二叉树各节点的值：（@字符表示空格）"<<endl;
    CreateBiTree(T);
    cout<<"判空：";
    if(BiTreeEmpty(T))
        cout<<"二叉树为空！"<<endl;
    else
        cout<<"二叉树不为空！"<<endl;
    cout<<"先序遍历二叉树：";
    PreOrderTraverse(T);
    cout<<endl;
    cout<<"中序遍历二叉树：";
    InOrderTraverse(T);
    cout<<endl;
    cout<<"后序遍历二叉树：";
    PostOrderTraverse(T);
    cout<<endl;
    cout<<"非递归中序遍历：";
    InOrderTraverse_Stack(T);
    cout<<endl;
    cout<<"二叉树的深度："<<BiTreeDepth(T)<<endl;
    cout<<"二叉树的叶子数："<<BiTreeLeafCount(T)<<endl;
    cout<<"二叉树的节点数："<<NodeCount(T)<<endl;
    cout<<"第2层的节点数："<<GetLevelNums(T, 2)<<endl;
    cout<<"初始化二叉树："<<endl;
    InitBiTree(T);
    cout<<"销毁二叉树："<<endl;
    return OK;
}

二叉树程序测试结果：

二叉树的基本操作

图：二叉树程序测试图

标签：

相关文章