分类
数据结构

二叉树-二叉链表-先序遍历

视频链接

二叉树的链式存储之二叉链表。

在单链表中,节点包含两部分,数据域(data)与指针域(next),如图:

数据域用来保存数据(可以是任意类型),指针域用来保存后继节点的地址,所有节点通过指针连在一起。

在二叉链表中,每个节点由三部分组成: 左指针(指向左孩子)、右指针(指向右孩子)、数据域(保存数据),如图:

二叉树的遍历:

  • 先序遍历(根-左-右)
  • 中序遍历(左-根-右)
  • 后序遍历(左-右-根)
  • 层次遍历(有多少层)

二叉树的定义中包含了递归的意思,再继续解读,其实左子树和右子树的左右子树其实也还是二叉树,所以可以使用递归进行遍历。

对于先序遍历,遍历的顺序为:访问根节点->先序遍历左子树->先序遍历右子树;
同理,中序遍历:中序遍历左子树->访问根节点->中序遍历右子树;
后序遍历:后续遍历左子树->后序遍历右子树->访问根节点。