二叉树

二叉树是树的一种每个节点最多可具有两个子树，即结点的度最大为 2（结点度：结点拥 有的子树数）

数据域： 存储数据的元素 指针域： 存储下个节点的地址

当前根节点的左边全部比根节点小，当前根节点的右边全部比根节点大

图片9

二叉树种类

斜树

所有结点都只有左子树，或者右子树

图片11

满二叉树

所有的分支节点都具有左右节点

图片10

完全二叉树

若设二叉树的深度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树

图片12

二叉树遍历方式

图片13

前序遍历

先访问根节点，然后遍历左子树，最后遍历右子树（根 > 左 > 右）

根据以上图片进行遍历：1 - 2 - 4 - 5 - 7 - 8 - 3 - 6 - 9

中序遍历

先遍历左子树，然后访问根节点，然后遍历右子树（左 > 根 > 右）

根据以上图片进行遍历：4 - 2 - 7 - 5 - 8 - 1 - 9 - 6 - 3

后序遍历

先遍历左子树，然后遍历右子树，最后访问树的根节点（左 > 右 > 根）

根据以上图片进行遍历：4 - 7 - 8 - 5 - 2 - 9 - 6 - 3 - 1