二叉树知识点
- 一.树的概念
- 1.1关于树的名词解释
- 二.二叉树的概念
- 1. 二叉树性质:
- 三.满二叉树与完全二叉树
- 递归前序遍历
- 递归中序遍历
- 递归后续遍历
一.树的概念
树是一种非线性数据结构,它是由n个或大于n个的结点来组成具有层次关系的一个集合(一个树及n个子树的关系集合)
把这个数据结构称之为树因为它很像一棵倒挂着的树
树的特点:
每一个结点都有零个或者n个结点组成
没有父亲结点的称为根结点
除根结点以外每一个节点都有一个父亲结点
结点之间互不相交
1.1关于树的名词解释
结点的度:一个结点含有的子树的个数称之为度。
树的度:在一棵树中,所有结点的度的最大值称之为树的度。
叶子结点或者终端结点:度为0的结点称为叶子结点/终端结点(不含有子树的结点)。
双亲结点或者父亲结点:若该结点含有子结点,则这个结点称为子结点的父亲结点。
子结点或者孩子结点:一个结点中含有子树的根结点称为该结点的子结点。
根结点:树中没有父亲结点称为根节点
结点的层次:从根开始定义为第一层,根的子结点为第二层…直到遇到所有终端结点。
树的高度:树中最大结点的层级,为树高。
一棵N个结点的树会产生n-1条边
二.二叉树的概念
二叉树是指每个节点最多有两个子树的树结构,共有五种形态
二叉树中树的度都是小于或者等于2的,不存在大于2的树
1. 二叉树性质:
性质1:二叉树第i层上的结点数最多为 2的i-1次方(i≥1)。
性质2:深度为k的二叉树至多有2的k-1次方个结点(k>=0)。
性质3:具有n个结点的二叉树的深度为log2 (n+1)。
性质4:在任意的二叉树中,若叶子结点的个数为n0,度为1的结点数为n1,度为2的结点数为n2。
表达式1:N=n0+n1+n2;
表达式2:N=n1+2*n2+1
则n0=n2+1。
三.满二叉树与完全二叉树
满二叉树:二叉树中每一个结点的度为2,为满二叉树。
非满二叉树
完全二叉树:在二叉树中,只有最下面两层结点的度可以小于2,并且最下层的叶子结点集中在左子树的位置上,如果没有集中在左树则不是一个非完全二叉树
一颗满二叉树必定是一颗完全二叉树,而完全而二叉树不一定是满二叉树。
递归前序遍历
public void preOrder(BinaryNode cur){
if(cur ==null){
return;
}
System.out.print(cur.val+" ");
preOrder(cur.left);
preOrder(cur.right);
}
递归中序遍历
public void inOrder(BinaryNode cur){
if(cur==null){
return;
}
inOrder(cur.left);
System.out.print(cur.val+" ");
inOrder(cur.right);
}
递归后续遍历
public void lastOrder(BinaryNode cur){
if(cur==null){
return;
}
inOrder(cur.left);
inOrder(cur.right);
System.out.print(cur.val+" ");
}