动画：二叉树有几种存储方式？(上)

写在前边

前边几篇文章的讲了数组、链表、队列等，今天和大家主要分享的是树这种数据结构。

树这种数据结构不像数组、链表一样，它是一种非线性结构，学起来可能比其他数据结构比较吃力，但是它在数据结构中占有很重要的地位，也是面试中的频繁考点，尤其是二叉树，一定注重起来。

由题目抛出的问题，树到底怎么存储呢？二叉树有几种存储方式呢？如果带着好奇心学习，学习更加的高效，一颗树横七竖八的，咋表示？下边小鹿带你一起来探索。

什么是树？

顾名思义，第一想到的就是路边的树，有树干、树根、树叶，数据结构中的树也是这样延伸过来的，只不过专用名词不一样，直接上图。

有一些树的专属名词我们总结下，A 是 B 的父节点，B 是 A 的子节点，D 是 B 的兄弟节点，C 和 D 称为叶子节点，A 为根节点。

是树它就有高度，数据结构中的树不仅有高度的概念，还有树的深度、层，节点的高度、深度等，一些最基本的知识点。

高度

树的高度就是根节点到叶子节点的最长路径。节点的高度就是节点到叶子节点的高度。

深度

节点的深度就是该节点到根节点的路径，也就是边的数量。

层

根节点为第一层，依次往下递增。

PS：注意各个概念的方向和起始值。

什么是二叉树？

我们知道什么是树了，二叉树的概念，就是给树做了一个限制，除了叶子结点，其余每个节点仅且只有两个子节点（也就是只有两个叉）。

二叉树有两个很重要的形态就是满二叉树和完全二叉树。

满二叉树：叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点，这种二叉树就叫作满二叉树。

完全二叉树：叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大。

二叉树的存储方式有几种？

既然我们都基本了解了二叉树的概念和基本常识，那我们要用，就要进行存储，如何存储一颗二叉树呢？

还记不记得小鹿之前的几篇文章一直强调说过，所有基本常见的数据结构都是由数组和链表演变而来，栈有顺序栈和链式栈、队列有顺序队列和链式队列，那么树可以用数组存储也可以用链表存储呀。

链式存储法

基于指针的链式存储，每个树的节点都是由数据域和两个指针域组成的。数据域用来存储数据，指针域用来存储左右两个子节点。

顺序存储法

顺序存储就是用数组来存储的，虽然不如指针域那么直观，但是存储的方法挺好理解的。根节点存储在下标 i = 1 的位置；左子节点存储在下标i 2 = 2的位置，右子节点存储在i 2 + 1 =3的位置。

图片
你会问，两种方式有什么区别，这个问题其实你早就知道了，如果你看到过小鹿之前写的文章，就知道区别就是数组和链表的区别。

数组的方式存储不需要开辟额外的指针空间，但是数组需要的内存空间是连续的，如果连续的内存空间不足，就无法进行存储。

二叉树的遍历

既然存储方式你也学会了，那么我们看看二叉树存储的数据，我们如何遍历出来呢？

共有四种遍历的方式，分别为前序遍历、中序遍历、后序遍历、按层遍历。

这个前、中、后遍历，初学者最不容易理解，当初小鹿学习的时候也是这样，那我用最简单的步骤和图来讲述一下。

我们以前序遍历为例子，首先我要告诉你前序遍历的规则，就是先遍历根节点、然后遍历左子节点最后遍历右子节点，上图：

这个图，你很快就能知道前序遍历的顺序，答案为：A->B->C

但是我换一张图，你来前序遍历下。

你可能就懵逼了，咋和刚才的不一样？我就是按照刚才那样遍历的？无论你是否成功遍历，小鹿来讲一下自己的思路。

我们还是看根节点的三个节点，按照根、左、右，我们知道先输出根节点 A、然后输出左子节点，因为 B 作为 D 和 E 的根节点先输出，然后 B 的左子节点是 D，D 作为 F 的根节点也要输出 D。

然后开始遍历左子节点，D 根节点的左子节点为 F，所以输出 F, B 的左子节点已经输出完毕，所以遍历右子节点 E。那么整个 A 的左子节点已经全部输出完毕，开始遍历 A 额右子节点。

还是按照左、根、右的遍历方法，依次输出去 C、H。整体的前序遍历为：A->B->D->F->E->C->H。动画如下：

前序遍历小鹿讲的很详细了，剩下的中序遍历和后续遍历的规则不一样。中序遍历先遍历左子节点，然后是根节点，最后是右子节点。而后序遍历的顺序是先遍历左子结点，然后遍历右子节点，最后遍历根节点。

其实和前序遍历道理都是一样的，只不过是换汤不换药，我把动图放到下放了，自己可以对照着遍历一下。

代码实现

JavaScript 版本

 1//遍历二叉查找树 2//前序遍历 3preorderTraversal = (tree) =>{ 4    //判断树是否为空 5    if(tree == null) return false; 6    //根节点 7    console.log(tree.data) 8    //左子树 9    this.preorderTraversal(tree.left)10    //右子树11    this.preorderTraversal(tree.right)12}1314//中序遍历15inorderTraversal = (tree) =>{16    //判断树是否为空17    if(tree == null) return false;18    //左子树19    this.inorderTraversal(tree.left);20    //根节点21    console.log(tree.data)22    //右节点23    this.inorderTraversal(tree.right);24}2526//后序遍历27postorderTraversal = (tree) =>{28    //判断树是否为空29    if(tree == null) return false;30    //左子树31    this.postorderTraversal(tree.left);32    //右子树33    this.postorderTraversal(tree.right);34    //根节点35    console.log(tree.data)36}

Java 版本

 1   /** 2     * 时间:2019/2/24 3     * 功能:前序遍历 4     * @param root 树的根节点 5     */ 6    public void preorderTraversal(Node root) { 7        //如果树为空 8        if(root == null) return; 9        //根节点10        System.out.print(root.data + " ");11        //左子树12        inorderTraversal(root.left);13        //右子树14        inorderTraversal(root.right);1516    }   1718    /**19     * 时间:2019/2/2420     * 功能:中序遍历21     * @param root 树的根节点22     */23    public void inorderTraversal(Node root) {24        //如果树为空25        if(root == null) return;26        //左子树27        inorderTraversal(root.left);28        //根节点29        System.out.print(root.data + " ");30        //右子树31        inorderTraversal(root.right);3233    }3435    /**36     * 时间:2019/2/2437     * 功能:后序遍历38     * @param root 树的根节点39     */40    public void postorderTraversal(Node root) {41        //如果树为空42        if(root == null) return;43        //左子树44        inorderTraversal(root.left);45        //右子树46        inorderTraversal(root.right);47        //根节点48        System.out.print(root.data + " ");4950    }

Python 版本

 1class BTree(object): 2    def __init__(self): 3        self._root = None 4        self._size = 0 5 6    def preOrder(self): 7        ''' 8        先遍历顺序：前序遍历 9        1，根节点10        2，遍历左子树11        3，遍历右子树12        '''13        btree = []1415        def recurse(node):16            if node != None:17                btree.append(node.data)18                recurse(node.lft)19                recurse(node.rgt)2021        recurse(self._root)22        return btree2324class BTree(object):25    def __init__(self):26        self._root = None27        self._size = 02829    def preOrder(self):30        '''31        先遍历顺序：中序遍历32        1，根节点33        2，遍历左子树34        3，遍历右子树35        '''36        btree = []3738        def recurse(node):39            if node != None:40                btree.append(node.data)41                recurse(node.lft)42                recurse(node.rgt)4344        recurse(self._root)45        return btree4647class BTree(object):48    def __init__(self):49        self._root = None50        self._size = 05152    # 后序遍历53    def postOrder(self):54        '''55        后序遍历顺序：后续遍历56        1，遍历左子树57        2，遍历右子树58        3，根节点59        '''60        btree = []6162        def recurse(node):63            if node != None:64                recurse(node.lft)65                recurse(node.rgt)66                btree.append(node.data)6768        recurse(self._root)69        return btree

C 语言版本

 1#include <stdio.h> 2#include <stdlib.h> 3 4/* 定义数据类型 */ 5typedef char TypeData ; 6 7/* 定义二叉树 */ 8typedef struct stBiTreeNode 9{10    TypeData data;11    struct stBiTreeNode *lchild, *rchild;12}BITREENODE;1314/* 初始化二叉树 */15BITREENODE* createBiTree()16{17    char chTempData = 0;1819    BITREENODE *pstNewNode = NULL;2021    scanf("%c",&chTempData);22    if(chTempData == '#')23    {24        pstNewNode = NULL;25    }26    else27    {28        /* 分配内存 */29        pstNewNode = (BITREENODE*)malloc(sizeof(BITREENODE) + 1);30        pstNewNode->data = chTempData;3132        /* 递归调用产生二叉树 */33        pstNewNode->lchild = createBiTree();34        pstNewNode->rchild = createBiTree();35    }3637    return pstNewNode;38}3940/* 前序遍历二叉树 */41int preVisitBiTree(BITREENODE* InRoot)42{43    if(InRoot)44    {45        /* 先遍历根节点 */46        printf("%c ",InRoot->data);4748        /* 遍历左子树 */49        preVisitBiTree(InRoot->lchild);5051        /* 遍历右子树 */52        preVisitBiTree(InRoot->rchild);5354    }55    return 0;56}575859/* 中序遍历二叉树 */60int inVisitBiTree(BITREENODE* InRoot)61{62    if(InRoot)63    {64        /* 遍历左子树 */65        preVisitBiTree(InRoot->lchild);666768        /* 先遍历根节点 */69        printf("%c ",InRoot->data);7071        /* 遍历右子树 */72        preVisitBiTree(InRoot->rchild);7374    }75    return 0;76}7778/* 后序遍历二叉树 */79int postVisitBiTree(BITREENODE* InRoot)80{81    if(InRoot)82    {83        /* 遍历左子树 */84        preVisitBiTree(InRoot->lchild);858687        /* 遍历右子树 */88        preVisitBiTree(InRoot->rchild);899091        /* 先遍历根节点 */92        printf("%c ",InRoot->data);9394    }95    return 0;96}

小结

今天小鹿分享了二叉树的基础部分，二叉树的基本概念以及二叉树的存储方式，还有二叉树的前中后遍历，最后留一个问题就是，二叉树除了前中后序遍历外，还有按层遍历，可以自己去探索一下二叉树按层是怎么遍历的？

今天的内容就到这里了，原创动画不容易，右下角给小鹿个“在看”，小鹿就很开心了，后续继续持续更新。

更多相关文章

随机推荐