动画：二叉树有几种存储方式？
写在前边
今天和大家主要分享的是树这种数据结构。
树这种数据结构不像数组、链表一样，它是一种非线性结构，学起来可能比其他数据结构比较吃力，但是它在数据结构中占有很重要的地位，也是面试中的频繁考点，尤其是二叉树，一定注重起来。
由题目抛出的问题，树到底怎么存储呢？二叉树有几种存储方式呢？如果带着好奇心学习，学习更加的高效，一颗树横七竖八的，咋表示？一起来探索。
1
什么是树？
顾名思义，第一想到的就是路边的树，有树干、树根、树叶，数据结构中的树也是这样延伸过来的，只不过专用名词不一样，直接上图。
有一些树的专属名词我们总结下，A 是 B 的父节点，B 是 A 的子节点，D 是 B 的兄弟节点，C 和 D 称为叶子节点，A 为根节点。
是树它就有高度，数据结构中的树不仅有高度的概念，还有树的深度、层，节点的高度、深度等，一些最基本的知识点。
高度
树的高度就是根节点到叶子节点的最长路径。节点的高度就是节点到叶子节点的高度。
深度
节点的深度就是该节点到根节点的路径，也就是边的数量。
层
根节点为第一层，依次往下递增。
PS：注意各个概念的方向和起始值。
2
什么是二叉树？
我们知道什么是树了，二叉树的概念，就是给树做了一个限制，除了叶子结点，其余每个节点仅且只有两个子节点（也就是只有两个叉）。
二叉树有两个很重要的形态就是满二叉树和完全二叉树。
满二叉树：叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点，这种二叉树就叫作满二叉树。
完全二叉树：叶子节点都在最底下两层 ，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大。
3
二叉树的存储方式有几种？
既然我们都基本了解了二叉树的概念和基本常识，那我们要用，就要进行存储，如何存储一颗二叉树呢？
还记不记得小鹿之前的几篇文章一直强调说过，所有基本常见的数据结构都是由数组和链表演变而来，栈有顺序栈和链式栈、队列有顺序队列和链式队列，那么树可以用数组存储也可以用链表存储呀。
链式存储法
基于指针的链式存储，每个树的节点都是由数据域和两个指针域组成的。数据域用来存储数据，指针域用来存储左右两个子节点。
顺序存储法
顺序存储就是用数组来存储的，虽然不如指针域那么直观，但是存储的方法挺好理解的。根节点存储在下标 i = 1 的位置；左子节点存储在下标i * 2 = 2的位置，右子节点存储在i * 2 + 1 =3的位置。
你会问，两种方式有什么区别，这个问题其实你早就知道了，如果你看到过小鹿之前写的文章，就知道区别就是数组和链表的区别。
数组的方式存储不需要开辟额外的指针空间，但是数组需要的内存空间是连续的，如果连续的内存空间不足，就无法进行存储。
4
二叉树的遍历
既然存储方式你也学会了，那么我们看看二叉树存储的数据，我们如何遍历出来呢？
共有四种遍历的方式，分别为前序遍历、中序遍历、后序遍历、按层遍历。
这个前、中、后遍历，初学者最不容易理解，当初小鹿学习的时候也是这样，那我用最简单的步骤和图来讲述一下。
我们以前序遍历为例子，首先我要告诉你前序遍历的规则，就是先遍历根节点、然后遍历左子节点最后遍历右子节点，上图：
这个图，你很快就能知道前序遍历的顺序，答案为：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。动画如下：
前序遍历小鹿讲的很详细了，剩下的中序遍历和后续遍历的规则不一样。中序遍历先遍历左子节点，然后是根节点，最后是右子节点。而后序遍历的顺序是先遍历左子结点，然后遍历右子节点，最后遍历根节点。
其实和前序遍历道理都是一样的，只不过是换汤不换药，我把动图放到下放了，自己可以对照着遍历一下。
5
代码实现
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}
13
14//中序遍历
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}
25
26//后序遍历
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);
15
16 }
17
18 /**
19 * 时间:2019/2/24
20 * 功能:中序遍历
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);
32
33 }
34
35 /**
36 * 时间:2019/2/24
37 * 功能:后序遍历
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 + " ");
49
50 }
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 = []
14
15 def recurse(node):
16 if node != None:
17 btree.append(node.data)
18 recurse(node.lft)
19 recurse(node.rgt)
20
21 recurse(self._root)
22 return btree
23
24class BTree(object):
25 def __init__(self):
26 self._root = None
27 self._size = 0
28
29 def preOrder(self):
30 '''
31 先遍历顺序：中序遍历
32 1，根节点
33 2，遍历左子树
34 3，遍历右子树
35 '''
36 btree = []
37
38 def recurse(node):
39 if node != None:
40 btree.append(node.data)
41 recurse(node.lft)
42 recurse(node.rgt)
43
44 recurse(self._root)
45 return btree
46
47class BTree(object):
48 def __init__(self):
49 self._root = None
50 self._size = 0
51
52 # 后序遍历
53 def postOrder(self):
54 '''
55 后序遍历顺序：后续遍历
56 1，遍历左子树
57 2，遍历右子树
58 3，根节点
59 '''
60 btree = []
61
62 def recurse(node):
63 if node != None:
64 recurse(node.lft)
65 recurse(node.rgt)
66 btree.append(node.data)
67
68 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;
13
14/* 初始化二叉树 */
15BITREENODE* createBiTree()
16{
17 char chTempData = 0;
18
19 BITREENODE *pstNewNode = NULL;
20
21 scanf("%c",&chTempData);
22 if(chTempData == '#')
23 {
24 pstNewNode = NULL;
25 }
26 else
27 {
28 /* 分配内存 */
29 pstNewNode = (BITREENODE*)malloc(sizeof(BITREENODE) + 1);
30 pstNewNode->data = chTempData;
31
32 /* 递归调用产生二叉树 */
33 pstNewNode->lchild = createBiTree();
34 pstNewNode->rchild = createBiTree();
35 }
36
37 return pstNewNode;
38}
39
40/* 前序遍历二叉树 */
41int preVisitBiTree(BITREENODE* InRoot)
42{
43 if(InRoot)
44 {
45 /* 先遍历根节点 */
46 printf("%c ",InRoot->data);
47
48 /* 遍历左子树 */
49 preVisitBiTree(InRoot->lchild);
50
51 /* 遍历右子树 */
52 preVisitBiTree(InRoot->rchild);
53
54 }
55 return 0;
56}
57
58
59/* 中序遍历二叉树 */
60int inVisitBiTree(BITREENODE* InRoot)
61{
62 if(InRoot)
63 {
64 /* 遍历左子树 */
65 preVisitBiTree(InRoot->lchild);
66
67
68 /* 先遍历根节点 */
69 printf("%c ",InRoot->data);
70
71 /* 遍历右子树 */
72 preVisitBiTree(InRoot->rchild);
73
74 }
75 return 0;
76}
77
78/* 后序遍历二叉树 */
79int postVisitBiTree(BITREENODE* InRoot)
80{
81 if(InRoot)
82 {
83 /* 遍历左子树 */
84 preVisitBiTree(InRoot->lchild);
85
86
87 /* 遍历右子树 */
88 preVisitBiTree(InRoot->rchild);
89
90
91 /* 先遍历根节点 */
92 printf("%c ",InRoot->data);
93
94 }
95 return 0;
96}
6
小结
今天小鹿分享了二叉树的基础部分，二叉树的基本概念以及二叉树的存储方式，还有二叉树的前中后遍历，最后留一个问题就是，二叉树除了前中后序遍历外，还有按层遍历，可以自己去探索一下二叉树按层是怎么遍历的？
●编号1081，输入编号直达本文
●输入m获取文章目录
程序员数学学习
锻炼数学逻辑思维