二叉树基本概述

大家好，欢迎来到IT知识分享网。

前面已经介绍过树了。
废话不多说，现在我们直接来看二叉树。
1.二叉树的定义

2.二叉树的五种基本形态

1.空二叉树就是什么也没有（null）
2.只有一个根
3.只有左子树，没有右子树
4.只有右子树，没有左子树
5.左右都有，如图

3.平衡二叉树
平衡二叉树不一定是对称的。
用树的最高高度-树的最低高度不能大于1，这样的树就称为平衡二叉树。
如图：

图中树的最高高度为4，最低高度为3, 4-3=1 , 1没有大于1.
所以只要差值小于等于1，都是平衡二叉树。
否则就是非平衡二叉树。
4.斜树

5.满二叉树

如图中，这个树有四层，它的四层全部都得是满的。所以它叫满二叉树。
如果有n层，它的n层全部都得是满的。

6.完全二叉树

每一行必须是从左往右依次排开。
规律如下：

7.二叉树的性质

全是公式，通过找规律推导的。可以直接记忆。

8.二叉树适用的存储结构

顺序存储结构只适合平衡树的存储。

除了完全二叉树、平衡二叉树或者满二叉树，其他的一般都用链式存储结构。

二、 二叉树的遍历

1.前序遍历

前序遍历DLR，D-->根结点，L-->根的左子树的结点,R-->根的右子树的结点
从根结点开始，每个结点都按DLR的顺序进行判断。

2.中序遍历

中序遍历LDR，L-->根的左子树的结点,D-->根结点，R-->根的右子树的结点
从根结点开始，每个结点都按LDR的顺序进行判断。
如图中的树，如果A在中序遍历的最前面，说明此树无左子树
如果A在中序遍历的最后面，说明此树无右子树

3.后续遍历

后序遍历LRD，L-->根的左子树的结点,R-->根的右子树的结点，D-->根结点
从根结点开始，每个结点都按LRD的顺序进行判断。

4.层序遍历

层序遍历是逐层从左到右遍历

1.深优一般基于栈实现，广优一般基于队列实现
2.前序和后序推不出一颗唯一的二叉树。

栈实现中序遍历：
1.从根结点开始，把根结点的左孩子和该孩子的左孩子（一直是左孩子）.......
（最左边的一排）全部进栈，一直到左边树没有下一个结点为止。
2.开始出栈，如果栈顶结点没有左，没有右，出栈它自己。
否则先出栈它自己，然后把它右孩子和该右孩子的所有左边进栈。然后再出栈。
3.出栈的顺序就是遍历的顺序




队列实现层序遍历：
1.根结点开始进队列
2.根结点出队，把根结点的左右孩子进队，再出队
3.其他结点一样，把该结点的左右孩子进队，再出队
4.队列出队的顺序就是层序遍历的顺序

二叉树基本知识点就到这里。
经过不断的学习，我会进行补充。