Tree 树:树描述的是一个父子关系,必须有明确的父子关系的才叫树
树中的一些概念:
节点: 表示树中的每个元素
根节点: 树最上面的那一盏明灯就是根节点
叶子节点: 指的是没有孩子的节点都是叶子节点。
树的高度:是从最底下算起,最底下为0,根节点的高度是最高的
树的深度:是从根节点从上往下算起,根节点的深度为0,再往下就依次加1
树的层:根节点看作第一层,往下依次加1
普通二叉树:每一个节点最多只能有两个孩子
满二叉树:除了叶子节点,每个节点都有左右两个孩子,且所有叶子节点都在同一层
完全二叉树:从树的根节点,从上到下,从左到右依次填满节点形成的二叉树,简单来说就是按着层的顺序,在每一层里从左到右看节点是否填满
如果一个树是满二叉树那么它一定是完全二叉树,但反之则不一定
二叉树的遍历(左子树是指根节点左边连接的那颗树,子树看成是一个整体,同理右子树是指根节点右边连接的那颗树):
1.前序遍历:根节点->左子树->右子树 记忆方法:根节点在最前面的位置
2.中序遍历:左子树->根节点->右子树 记忆方法:根节点在中间的位置
3.后序遍历:左子树->右子树->根节点 记忆方法:根节点在最后面的位置