top
友情提示
测试消息
确定
友情提示

处理中,请稍后...

经典数据结构之二叉树
数据结构可分为线性结构和非线性结构两大类。本篇文章讨论的二叉树属于树形结构之一, 树形结构属于非线性结构。注意:树 和 二叉树 不是包含关系。二叉树不是树的特例,二者是树形结构的两种不同类型,不存在包含关系。之所以在此总结二叉树,是因为堆排序等等常用算法涉及到二叉树,并且二叉树也是一个必备的数据结构基础知识。

在树形结构中,每个节点允许有一个直接前驱节点,但允许有一个以上的直接后继节点。树的存储结构和操作实现都比较复杂,但可以将其转化为二叉树处理。

常用术语
(1)满二叉树:在二叉树中,若所有的双亲结点都存在叶子结点,且所有子结点都在同一层上,这样的二叉树叫做满二叉树。
(2)完全二叉树:若一棵具有n个结点的二叉树的结构与满二叉树的前n个结点的结构相同,则称这样的二叉树为完全二叉树。

二叉树的存储结构
二叉树的存储结构主要有三种:顺序存储结构、链式存储结构和仿真指针存储结构。
(1)顺序存储结构
顺序存储是指将二叉树的结点用数组按照一定的规律存储起来。容易想象:当二叉树为完全二叉树的时候,存储为线性结构方便操作且节省空间。但是若要存储的二叉树不是完全二叉树的时候,要想正确存储二叉树,存储结构中就要添加 “空节点” 占位(因为计算子节点的位置需要用到下标),大量的空节点出现显然是不太适合的。

所以,对于完全二叉树,采用线性存储结构是不错的选择。若不是完全二叉树,但与完全二叉树相差很小的时候,由于需要添加的 空节点 数量很少,所以也可以用线性存储结构, 相差很大的话就得另寻它法了。

(2)二叉树的链式存储结构
二叉树的链式存储结构就是用指针来描述结点之间的关系。最常用的就是 “二叉链”,二叉链结构的每个节点通常包含三个域:左孩子指针域leftChild, 数据域data, 右孩子指针域rightChild。
 
[leftChild | data | rightChild]

二叉链操作简单,可以方便地构建各种形状的二叉树。缺点是查找当前节点的双亲结点比较麻烦(为此出现了三叉链,在二叉链的基础上增加了一个指向双亲结点的指针域)。

(3)二叉树的仿真指针存储结构
仿真指针用到的是数组下标,leftChild和rightChild中均存储孩子结点所在的数组下标,这样就通过数组下标建立了一个指向关系。这个思想理解起来也比较简单,这里就不细说了。本篇主要讨论最常用的的结构:二叉树的链式存储结构

C语言实现及测试:
首先是头文件:tree.h
#ifndef TREE_H
#define TREE_H

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

typedef int dataType;  //数据类型,简单测试,将 DataType 设置为 int

//节点类型
typedef struct nodeData{
    struct nodeData *leftChild;
    struct nodeData *rightChild;
    dataType data;
}node_t;

node_t * initBiTree();
int insertLeftChildNode(node_t * currNode, node_t *childNode);
int insertRightChildNode(node_t * currNode, node_t *childNode);
node_t * insertLeftChildByData(node_t *currNode, dataType data);
node_t * insertRightChildByData(node_t *currNode, dataType data);

//警告及错误输出
void printError(char *error);
void printWarning(char *warning);
//销毁
void destroyBiTree(node_t **rootNode);
//前序遍历(递归方式)
void formerTraversal(node_t * node, void (*nodeAction)());
//中序遍历(递归方式)
void inTraversal(node_t * node, void (*nodeAction)());
//后序遍历(递归方式)
void afterTraversal(node_t * node, void (*nodeAction)());

node_t * deleteRightChild(node_t * currNode);
node_t * deleteLeftChild(node_t * currNode);

#endif

其次是tree.c:
#include "tree.h"

/** \brief 初始化二叉树
* \return
*/
node_t * initBiTree(){
    node_t *root = (node_t*)malloc(sizeof(node_t));
    root->leftChild = NULL;
    root->rightChild = NULL;
    root->data = 0;
    return root;
}

/** \brief 通过已存在节点为当前节点插入左子节点
*
* \param currNode  : 目标节点
* \param childNode  : 待插入子节点
* \return
*/
int insertLeftChildNode(node_t * currNode, node_t *childNode){
    if(currNode == NULL){
        printError("current Node is NULL");
        return -1;
    }
    if(childNode == NULL){
        printError("child node is NULL");
        return -1;
    }
    if(currNode->leftChild != NULL){
        printError("current node's leftChild is already exists");
        return -1;
    }
    currNode->leftChild = childNode;
    return 0;
}

/** \brief 通过已存在节点为当前节点插入右子节点
*
* \param currNode  : 目标节点
* \param childNode  : 待插入子节点
* \return
*/
int insertRightChildNode(node_t * currNode, node_t *childNode){
    if(currNode == NULL){
        printError("current Node is NULL");
        return -1;
    }
    if(childNode == NULL){
        printError("child node is NULL");
        return -1;
    }
    if(currNode->rightChild != NULL){
        printError("current node's rightChild is already exists");
        return -1;
    }
    currNode->rightChild = childNode;
    return 0;
}

/** \brief 通过数据为当前节点插入左节点
*
* \param currNode  : 目标节点
* \param data      : 待插入数据
* \return
*/
node_t * insertLeftChildByData(node_t *currNode, dataType data){

    if(currNode == NULL){
        printError("current node is NULL");
        return NULL;
    }
    if(currNode->leftChild != NULL){
        printError("current node's leftChild is already exists");
        return NULL;
    }
    //空间初始化
    node_t * temp = (node_t *)malloc(sizeof(node_t));
    if(temp == NULL){
        printError("memory initial error!");
        return NULL;
    }
    temp->leftChild = NULL;
    temp->rightChild = NULL;

    temp->data = data;
    currNode->leftChild = temp;
    return temp;
}

/** \brief 通过数据为当前节点插入右节点
*
* \param currNode  : 目标节点
* \param data      : 待插入数据
* \return
*/
node_t * insertRightChildByData(node_t *currNode, dataType data){

    if(currNode == NULL){
        printError("current node is NULL");
        return NULL;
    }
    if(currNode->rightChild != NULL){
        printError("current node's rightChild is already exists");
        return NULL;
    }
    //空间初始化
    node_t * temp = (node_t *)malloc(sizeof(node_t));
    if(temp == NULL){
        printError("memory initial error!");
        return NULL;
    }
    //注意每次插入新节点都要初始化
    temp->leftChild = NULL;
    temp->rightChild = NULL;

    temp->data = data;
    currNode->rightChild = temp;
    return temp;
}

/** \brief 删除当前节点的左节点
*
* \param currNode : 目标节点
* \return
*/
node_t * deleteLeftChild(node_t * currNode){

    if(currNode == NULL){
        printWarning("current node is NULL.");
        return NULL;
    }

    if(currNode->leftChild == NULL){
        printError("the left child node which you want to delete is NULL");
        return NULL;
    }

    //直接调用销毁函数,若节点后面还有子节点,则销毁的是一整棵子树
    destroyBiTree(&currNode->leftChild);
    return currNode;
}

/** \brief 删除当前节点的右节点
*
* \param currNode : 目标节点
* \return
*/
node_t * deleteRightChild(node_t * currNode){

    if(currNode == NULL){
        printWarning("current node is NULL.");
        return NULL;
    }

    if(currNode->rightChild == NULL){
        printError("the right child node which you want to delete is NULL");
        return NULL;
    }

    //直接调用销毁函数,若节点后面还有子节点,则销毁的是一整棵子树
    destroyBiTree(&currNode->rightChild);
    return currNode;
}

/** \brief 先序(前序)遍历
*
* \param node      : 二叉树根节点
* \param nodeAction : 回调函数
* \return
*
*/
void formerTraversal(node_t * node, void (*nodeAction)()){

    if(node == NULL){
        printWarning("the node you want to traverse is NULL");
        return;
    }

    nodeAction(node);

    if(node->leftChild != NULL){
        formerTraversal(node->leftChild, nodeAction);
    }

    if(node->rightChild != NULL){
        formerTraversal(node->rightChild, nodeAction);
    }
}

/** \brief 中序遍历
*
* \param node      : 二叉树根节点
* \param nodeAction : 回调函数
* \return
*
*/
void inTraversal(node_t * node, void (*nodeAction)()){

    if(node == NULL){
        printWarning("the node you want to traverse is NULL");
        return;
    }

    if(node->leftChild != NULL){
        inTraversal(node->leftChild, nodeAction);
    }

    nodeAction(node);

    if(node->rightChild != NULL){
        inTraversal(node->rightChild, nodeAction);
    }
}

/** \brief 后序遍历
*
* \param node      : 二叉树根节点
* \param nodeAction : 回调函数
* \return
*
*/
void afterTraversal(node_t * node, void (*nodeAction)()){

    if(node == NULL){
        printWarning("the node you want to traverse is NULL");
        return;
    }
    if(node->leftChild != NULL){
        afterTraversal(node->leftChild, nodeAction);
    }
    if(node->rightChild != NULL){
        afterTraversal(node->rightChild, nodeAction);
    }

    nodeAction(node);
}

/** \brief 销毁二叉树
*
* \param node : 二叉树根节点
* \return
*
*/
void destroyBiTree(node_t **rootNode){

    if(rootNode == NULL || *rootNode == NULL){
        printWarning("the node which you want to destroy is NULL");
        return;
    }
    if((*rootNode)->leftChild != NULL){
        destroyBiTree(&(*rootNode)->leftChild);
    }
    if((*rootNode)->rightChild != NULL){
        destroyBiTree(&(*rootNode)->rightChild);
    }
    free(*rootNode);
    *rootNode = NULL;
}

/**
* 组织错误输出
*
*@param error : 错误信息
*/
void printError(char *error){

    printf("### ERROR: ");
    printf("%s", error);
    printf("\n");

}

/**
* 组织警告输出
*
*@param warning : 警告信息
*/
void printWarning(char *warning){

    printf("## WARNING: ");
    printf("%s", warning);
    printf("\n");

}

最后是main.c执行测试:
#include "tree.h"

/**
*自定义回调函数,遍历时使用
*/
void visitNodeAction(node_t * node){
    if(node == NULL){
        printf("node is null!\n");
    }
    printf(" %d ",node->data);
}

int main(){
    node_t *p;
    //初始化
    node_t *tree = initBiTree();
    tree->data = 10;
    p = insertRightChildByData(tree, 20);
    p = insertLeftChildByData(p, 50);
    insertRightChildByData(p, 60);
    p = insertLeftChildByData(tree, 30);
    insertLeftChildByData(p, 40);
    /*构建了如下结构的二叉树

              10
             / \
            30  20
           /    /
         40    50
                 \
                 60

    */

    //遍历输出
    puts("former: ");
    formerTraversal(tree, visitNodeAction);
    puts("\nin: ");
    inTraversal(tree, visitNodeAction);
    puts("\nafter: ");
    afterTraversal(tree, visitNodeAction);
    //销毁
    destroyBiTree(&tree);

    return 0;
}

上述测试运行结果:
运行结果


总结
上述展示了基本的二叉树操作,包括结点的插入、删除、遍历(递归方式)、销毁等。二叉树的遍历也存在很多学问,实现方式也有很多,用递归实现是很简洁的,也是很基础的。借助其他常用的数据结构也可以用非递归的思路来做。在以后的文章中会有总结。

另外,此处用的测试数据非常简单,只是简单的整形数据,实际中根据需求更改DataType即可以上只是我个人见解,欢迎留言,欢迎吐槽,欢迎分享。


【原创内容,转载请注明出处】
标签
二叉树
数据结构
非线性
上一篇:排序算法:交换排序之快速排序
下一篇:二叉树非递归遍历
文章阅读完了, 快到评论区留下你的看法吧!
Email:
验证码:
昵 称 :
评论列表
热门标签
今日倒计时
小时 分钟
年少不识曲中意,再听已是曲中人
加油吧骚年
文章分类
最新文章
浏览排行
最新留言
[2018/11/27]博客该更新了
[2018/10/25]网站链接以便更 www.qiuyegen.com
[2018/04/07]太难找了,找到了
[2018/03/21]Entry fileTemplates//Singleton.java.ft not found in C:/Dev/android-studio/lib/resources_en.jar 该错误对我们使用AS没有影响吗?为什么复制保存后重新创建一个新的之后这个错误又出现了?
[2018/01/23]815cce30b85eb6b7ee7930c09135fcf7好漂亮的博客空间啊
[2018/01/06]好漂亮的博客.......
[2017/12/26]试试水
[2017/12/21] 博主可以分享一下这个源码不, 很喜欢这个博客
[2017/11/20]你加我友链了????
[2017/11/20]你的alert 很不友好哈
Copyright © 2018 DevSONG . All rights reserved. 有疑问或者建议? 留言给我或者E-mail me
滇ICP备17002307号-3