二叉树的链式存储之二叉链表。
在单链表中,节点包含两部分,数据域(data)与指针域(next),如图:

数据域用来保存数据(可以是任意类型),指针域用来保存后继节点的地址,所有节点通过指针连在一起。
在二叉链表中,每个节点由三部分组成: 左指针(指向左孩子)、右指针(指向右孩子)、数据域(保存数据),如图:

二叉树的遍历:
- 先序遍历(根-左-右)
- 中序遍历(左-根-右)
- 后序遍历(左-右-根)
- 层次遍历(有多少层)
二叉树的定义中包含了递归的意思,再继续解读,其实左子树和右子树的左右子树其实也还是二叉树,所以可以使用递归进行遍历。
对于先序遍历,遍历的顺序为:访问根节点->先序遍历左子树->先序遍历右子树;
同理,中序遍历:中序遍历左子树->访问根节点->中序遍历右子树;
后序遍历:后续遍历左子树->后序遍历右子树->访问根节点。