数据结构与算法(14)-二叉树

1. 二叉树的实现分析

问题思考：如何存储一棵完全二叉树？
结果：使用一个数组，按照二叉树中每个节点的位置进行存储即可


完全二叉树的存储图示.png

如果不是一颗完全二叉树则在使用数组存储的时候就要将没有节点的位置置空，如下图所示，当一棵树是斜树的时候就会浪费很多存储空间，所以如果是斜树使用链式存储会更好一些，如果是一颗完全二叉树则使用数组存储是非常完美的。


一般树的存储图示.png

2. 二叉树的顺序存储实现

2.1 准备条件

我们在实现顺序存储的二叉树的时候，只需要一个数组即可，所以我们设计一个数组来存储二叉树。

代码实现：

#include <stdio.h>
#include "stdlib.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXSIZE 100 /* 存储空间初始分配量 */
#define MAX_TREE_SIZE 100 /* 二叉树的最大结点数 */

typedef int Status;        /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int CElemType;      /* 树结点的数据类型，目前暂定为整型 */
typedef CElemType SqBiTree[MAX_TREE_SIZE]; /* 0号单元存储根结点  */
CElemType Nil = 0;   /*设整型以0为空 或者以 INT_MAX(65535)*/

// 节点的层和每层中的位置
typedef struct {
    int level; //结点层
    int order; //本层的序号(按照满二叉树给定序号规则)
} Position;

2.2 初始化并创建二叉树

初始化一个二叉树则需要将存储这个二叉树的所有节点置空即可，与清空一致。

代码实现：

/// 初始化一个二叉树
/// @param T 树
Status InitBiTree(SqBiTree T) {
    // 将所有节点置空
    for (int i = 0; i<MAX_TREE_SIZE; i++) {
        T[i] = Nil;
    }
    return OK;
}

// 在顺序存储中清空和初始化的操作是一样的
#define ClearBiTree InitBiTree

我们这里的创建一个二叉树就是能够自动给树创建一些节点，方便后续的测试，这里默认添加10个节点，在添加的时候做了一个判断，当前节点不为空，但其父节点为空则直接报错（根节点除外），其实我们这里判断这个有点多余，我们是按照完全二叉树的样子去创建的，但是如果在我们手动输入的时候难免会有错，所以多加些判断。

代码实现：

/// 创建一个树（按照完全二叉树初始化）
/// @param T 树
Status CreateBiTree(SqBiTree T) {
    int i = 0;
    while (i<10) {// 添加10个节点
        T[i] = i+1;
        // 如果该节点不是根节点，但有值，而且其父节点没值，则报错（防止手动插入的时候犯错）
        if (i!=0 && T[i] != Nil && T[(i+1)/2-1] == Nil) {
            printf("出现无双亲的非根结点%d\n",T[i]);
            exit(0);
        }
        i++;
    }
    // 将其余节点置空
    while (i<MAX_TREE_SIZE) {
        T[i] = Nil;
        i++;
    }
    
    return OK;
}

2.3 判断二叉树是否为空树

树最重要的就是根，没有根就没有树，所以二叉树的根节点为空则二叉树就是空树。
代码实现：

// 判断树是否为空，只需要判断根节点即可，根节点都没有指定为空
Status BiTreeIsEmpty(SqBiTree T) {
    
    if (T[0] == Nil) {
        return TRUE;
    } else {
        return FALSE;
    }
}

2.4 计算二叉树的深度

要想计算二叉树的深度就要找到最后一个节点，所以我们在顺序存储结构中通过从后往前遍历的方法找到的第一个有值的节点就是该二叉树的最后一个节点。

根据二叉树的节点规则，当2的当前深度的次幂超过刚才找到的位置时就找到了该二叉树的深度。
代码实现：

/// 二叉树的深度
/// @param T 树
int BiTreeDepth(SqBiTree T){
    int j = -1;
    // 如果树为空则返回-1
    if (BiTreeIsEmpty(T)) { return j; }
    
    int i;
    for (i = MAX_TREE_SIZE-1; i>=0; i--) {
        if (T[i] != Nil) {
            break;
        }
    }
    
    do {
        j++;
    } while (pow(2, j) <= i); //计算2的次幂
    
    return 0;
}

2.5 给定位置赋值

赋值操作首先要根据层号和序号找到需要赋值的位置，然后需要判断该位置是否合法，合法后给该位置赋值。

代码实现：

/// 给特定位置的节点赋值
/// @param T 树
/// @param p 位置
/// @param e 值
Status setValue(SqBiTree T, Position p, CElemType e) {
    
    // 找到位置
    int i = (int)pow(2, p.level-1) + p.order - 2;
    
    // 判断要赋值的位置的父节点是否为空
    if (T[(i+1)/2-1] == Nil && e != Nil) {
        return ERROR;
    }
    
    // 判断要赋值的位置的子节点是否有值
    if ((T[i*2+1] != Nil || T[i*2+1] != Nil) && e !=Nil) {
        return ERROR;
    }
    
    // 赋值
    T[i] = e;
    
    return OK;
}

2.6 获取根节点的值和指定位置的值

  • 根节点
    代码实现： 
/// 获取跟节点的值
/// @param T 树
/// @param e 值存储
Status Root(SqBiTree T,CElemType *e){
    if (BiTreeIsEmpty(T)) {
        return ERROR;
    }
    
    *e = T[0];
    return OK;
}
  • 其他节点

根据传入的层号和该层序号找到此值的位置，返回即可

代码实现：

/// 获取给定位置的值
/// @param T 树
/// @param p 位置
CElemType getValue(SqBiTree T, Position p) {
    
    // 打印层
    printf("要获取的层号是：%d\n", (int)pow(2, p.level-1));
    // 打印序号
    printf("该层的序号是 %d\n", p.order);
    // 返回
    return T[(int)pow(2, p.level-1)+p.order-2];
}

2.7 获取某节点的父节点

获取双亲节点只需找到该节点，按照二叉树节点的规则，返回其双亲节点即可

/// 获取某个节点的父节点
/// @param T 树
/// @param e 节点值
CElemType GetParent(SqBiTree T, CElemType e){
    // 判断树是否为空
    if (T[0] == Nil) { return Nil; }
    // 遍历找到值所对应的节点，根节点没有双亲节点，所以从1开始
    for (int i = 1; i<MAXSIZE; i++) {
        if (T[i] == e) {
            return T[(i+1)/2 - 1];
        }
    }
    
    return Nil;
}

2.8 获取某节点的孩子节点（左右）

很简单，只需找到相应节点，然后根据规则查找左右孩子即可。

代码实现：

/// 获取某个节点的左孩子
/// @param T 树
/// @param e 节点值
CElemType getLeftChild(SqBiTree T, CElemType e) {
    // 树空判断
    if (T[0]==Nil) { return Nil; }
    
    // 找到e的位置
    for (int i=0; i<MAXSIZE-1; i++) {
        if (T[i]==e) {
            return T[i*2+1];
        }
    }
    
    return  Nil;
}

/// 获取某个节点的右孩子
/// @param T 树
/// @param e 节点值
CElemType getRightChild(SqBiTree T, CElemType e) {
    // 树空判断
    if (T[0]==Nil) { return Nil; }
    
    // 找到e的位置
    for (int i=0; i<MAXSIZE-1; i++) {
        if (T[i]==e) {
            return T[i*2+2];
        }
    }
    
    return  Nil;
}

2.9 获取某节点的兄弟节点（左右）

首先根据节点值找到节点，如果是找做兄弟则该节点必须是个右节点，反之也是。


/// 获取某个节点的左兄弟
/// @param T 树
/// @param e 节点值
CElemType GetLeftSibling(SqBiTree T, CElemType e){
    
    // 树空判断
    if (T[0]==Nil) { return Nil; }
    
    // 找到e的位置
    for (int i=1; i<MAXSIZE-1; i++) {
        // 值相等，并且找到的位置是右孩子，不然没有左兄弟
        if (T[i]==e && i%2==0) {
            return T[i-1];
        }
    }
    
    return Nil;
}

/// 获取某个节点的右兄弟
/// @param T 树
/// @param e 节点值
CElemType GetRightSibling(SqBiTree T, CElemType e){
    
    // 树空判断
    if (T[0]==Nil) { return Nil; }
    
    // 找到e的位置
    for (int i=1; i<MAXSIZE-1; i++) {
        // 值相等，并且找到的位置是左孩子，不然没有右兄弟
        if (T[i]==e && i%2==1) {
            return T[i+1];
        }
    }
    
    return Nil;
}

3. 二叉树的遍历

3.1 前序遍历

前序遍历（DLR/NLR），是二叉树遍历的一种，也叫做先序遍历。前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。

前序遍历.png

遍历结果为：ABCDGHCEIF

实现代码：

/// 前序遍历
/// @param T 树
/// @param e 节点
void PreTraverse(SqBiTree T, int e) {
    // 打印节点
    printf("%d ",T[e]);
    
    // 前序遍历左子树
    if (T[2*e+1] != Nil) {
        PreTraverse(T, 2*e+1);
    }
    
    // 前序遍历右子树
    if (T[2*e+2] != Nil) {
        PreTraverse(T, 2*e+2);
    }
}

/// 前序遍历封装
/// @param T 树
Status PreOrderTraverse(SqBiTree T){
    
    //树不为空
    if (!BiTreeIsEmpty(T)) {
        PreTraverse(T, 0);
    }
    printf("\n");
    return  OK;
}

3.2 中序遍历

中序遍历（LDR/LNR）是二叉树遍历的一种。在二叉树中，中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。

中序遍历.png

遍历结果为：GDHBAEICF

实现代码：

/// 中序遍历
/// @param T 树
/// @param e 节点
void InTraverse(SqBiTree T, int e){
    // 如果传入节点的左子树不为空就一直寻找
    if (T[2*e+1] != Nil) {
        InTraverse(T, 2*e+1);
    }
    // 打印节点
    printf("%d ",T[e]);
    
    // 如果右子树也不为空则从该节点的右子树继续向下遍历
    if (T[2*e+2] != Nil) {
        InTraverse(T, 2*e+2);
    }
}

/// 中序遍历的包装
/// @param T 树
Status InOrderTraverse(SqBiTree T){
    
    // 树不为空则开始遍历
    if (!BiTreeIsEmpty(T)) {
        InTraverse(T, 0);
    }
    printf("\n");
    return OK;
}

3.3后序遍历

后序遍历（LRD/LRN）二叉树遍历的一种。在二叉树中，先左后右再根，即首先遍历左子树，然后遍历右子树，最后访问根结点。

后续遍历.png

遍历结果为：GHDBIEFCA

实现代码：

/// 后序遍历
/// @param T 树
/// @param e 节点
void PostTraverse(SqBiTree T, int e){
    // 如果传入节点的左子树不为空就一直寻找
    if (T[2*e+1] != Nil) {
        PostTraverse(T, 2*e+1);
    }
    
    // 如果右子树也不为空则从该节点的右子树继续向下遍历
    if (T[2*e+2] != Nil) {
        PostTraverse(T, 2*e+2);
    }
    
    // 打印节点
    printf("%d ",T[e]);
}

/// 后续遍历的包装
/// @param T 树
Status PostOrderTraverse(SqBiTree T)
{
    if(!BiTreeIsEmpty(T)){
        PostTraverse(T,0);
    }
        
    printf("\n");
    return OK;
}

3.4 层序遍历

层序遍历二叉树遍历的一种。即从根节点开始从左至右一层一层的遍历每个节点。


层序遍历.png

遍历结果为：ABCDEFGHI

实现代码：

/// 层序遍历
/// @param T 🌲
void LevelOrderTraverse(SqBiTree T) {
    // 初始化一个遍历存储值
    int i = MAX_TREE_SIZE-1;
    // 找到最后一个有值的
    while (T[i] == Nil) { i--; }
    // 遍历打印
    for (int j = 0; j<=i; j++) {
        if (T[j] != Nil) {
            printf("%d ", T[j]);
        }
    }
    printf("\n");
}

4 二叉树的链式存储实现

详细细节见注释，主要通过插入的时候进行前序方法进行设计，使用'#'作为判断到达叶子节点的条件，来实现叶子节点的置空操作。
代码实现：


#include <stdio.h>
#include "string.h"
#include "stdlib.h"
#include "math.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

/* 存储空间初始分配量 */
#define MAXSIZE 100
/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Status;

char *chars;
int indexs = 0;

typedef char CElemType;
CElemType Nil=' '; /* 字符型以空格符为空 */
typedef struct BiTNode  /* 结点结构 */
{
    CElemType data;        /* 结点数据 */
    struct BiTNode *lchild,*rchild; /* 左右孩子指针 */
}BiTNode,*BiTree;


/// 初始化
/// @param T 树
Status InitBiTree(BiTree *T) {
    *T = NULL;
    return OK;
}

/// 创建一棵链式树
/// @param T 树
void CreateBiTree(BiTree *T){
    // 使用一个全局数组来实现初始化的插入
    CElemType c = chars[indexs++];
    printf("%c ", c);
    /*
     1.如果第一个节点就是占位的则树就是空的
     2.由于叶子节点没有孩子，为了占有其左右孩子指针，通过#来判断，
     如遇#其孩子指针为空
     3.通过#号来结束插入，初始化构建的时候需要设计好顺序
     
     */
    if (c == '#') {
        *T = NULL;
    } else {
        *T = (BiTree)malloc(sizeof(BiTNode));
        // 如果没创建成功就报错
        if (!*T) { exit(OVERFLOW); }
        // 赋值
        (*T)->data = c;
        // 构造左子树
        CreateBiTree(&(*T)->lchild);
        // 构造右子树
        CreateBiTree(&(*T)->rchild);
    }
}

/// 判断是否是空树
/// @param T 树
Status BiTreeIsEmpty(BiTree T)
{
    if (T == NULL) {
        return TRUE;
    } else {
        return FALSE;
    }
}

/// 获取根节点的值
/// @param T 树
CElemType GetRoot(BiTree T) {
    if (BiTreeIsEmpty(T)) {
        return Nil;
    }
    return T->data;
}

/// 销毁二叉树
/// @param T 树
void DestroyBiTree(BiTree *T){
    // 空就不销毁了
    if (*T) {
        // 销毁左孩子
        if ((*T)->lchild) {
            DestroyBiTree(&(*T)->lchild);
        }
        
        // 销毁右孩子
        if ((*T)->lchild) {
            DestroyBiTree(&(*T)->rchild);
        }
        // 释放根节点
        free(*T);
        // 置空
        *T = NULL;
    }
}


/// 二叉树深度
/// @param T 树
int BiTreeDepth(BiTree T){
    
    /*
     由于存在左子树和右子树，那个最深需要比较一下
     */
    
    int i,j;
    // 计算左孩子的深度
    if (T->lchild) {
        i = BiTreeDepth(T->lchild);
    } else { i=0; }//没有左子树i为0
    
    // 计算有子树的深度
    if (T->rchild) {
        j = BiTreeDepth(T->rchild);
    } else { j=0; }//没有左子树i为0
    
    return i>j?i+1:j+1;
}

/// 获取某个节点的值
/// @param p 节点
CElemType GetValue(BiTree p) {
    return p->data;
}

/// 设置某个节点的值
/// @param p 节点
/// @param value 值
void SetValue(BiTree p,CElemType value){
    p->data = value;
}

/// 前序遍历
/// @param T 二叉树
void PreOrderTraverse(BiTree T){
    // 非空判断
    if (T==NULL) { return; }
    // 打印
    printf("%c ", T->data);
    // 遍历左子树
    PreOrderTraverse(T->lchild);
    // 遍历右子树
    PreOrderTraverse(T->rchild);
}

/// 中序遍历
/// @param T 二叉树
void InOrderTraverse(BiTree T){
    // 非空判断
    if (T==NULL) { return; }
    // 遍历左子树
    InOrderTraverse(T->lchild);
    // 打印
    printf("%c ", T->data);
    // 遍历右子树
    InOrderTraverse(T->rchild);
}

/// 后序遍历
/// @param T 二叉树
void PostOrderTraverse(BiTree T){
    // 非空判断
    if (T==NULL) { return; }
    // 遍历左子树
    PostOrderTraverse(T->lchild);
    // 遍历右子树
    PostOrderTraverse(T->rchild);
    // 打印
    printf("%c ", T->data);
}



int main(int argc, const char * argv[]) {
    // insert code here...

    BiTree T;
    
    InitBiTree(&T);
    chars = "ABDH#K###E##CFI###G#J##";
    CreateBiTree(&T);
    
    printf("二叉树是否为空%d\n", BiTreeIsEmpty(T));
    printf("树的深度是%d\n", BiTreeDepth(T));
    printf("树根的值是%c\n", GetRoot(T));
    
    printf("\n前序遍历二叉树:");
    PreOrderTraverse(T);
    
    printf("\n中序遍历二叉树:");
    InOrderTraverse(T);
    
    printf("\n后序遍历二叉树:");
    PostOrderTraverse(T);
    
    printf("\n");
    
    return 0;
}
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 204,684评论 6赞 478
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 87,143评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 151,214评论 0赞 337
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,788评论 1赞 277
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,796评论 5赞 368
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,665评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,027评论 3赞 399
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,679评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 41,346评论 1赞 299
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,664评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,766评论 1赞 331
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,412评论 4赞 321
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,015评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,974评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,203评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,073评论 2赞 350
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,501评论 2赞 343