树-学习笔记

度(degree):是子树的个数

叶子(leaf):度为0

Height或者Depth:最大层数

Ancestor&Descendant:祖先与子孙

二叉树可以没有左子树而有右子树,也就是可以是无序的

二叉树与树是两种不同的数据结构.

完全二叉树:最多只有最下一层度数可以小于2，并且最下一层的结点都集中在左边.

二叉树性质:

1：第i(i>=1)层上的结点数最多为2^i-1

2:高度为K的二叉树最多有2^k-1个结点

3:对任何二叉树T,设n0,n1,n2分别表示度为0,1,2的结点个数,则n0=n2+1

4:具有n个结点的完全二叉树的高度为

5:非空满二叉树的叶结点数等于其分支结点数加1

6:一颗非空二叉树空子树的数目等于其结点数目加1

 

 二叉树的JAVA接口 称之为BinNode类中存储了指向Object类的引用

package Tree;

interface BinNode {
	public Object element();
	public Object setElement();
	
	public Binnode left();
	public Binnode setLeft(BinNode p);
	
	public Binnode right();
	public Binnode setRight(BinNode p);
	
	public Boolean isLeaf();
	
}

 

在顺序存储结构中一切都看做完全二叉树

假设给定结点的地址为I

1.若I=1则该结点为根结点

2.若I!=1则该结点的父亲结点地址为I/2的整数部分

3.若2*I<=n 则该结点的左儿子地址为2*I,否则该结点无左儿子

4.若2*I+1<=n 则该结点的右儿子地址为2*I+1,否则该结点无右儿子

5.若I为奇数,则该结点的左兄弟为I-1

6.若I为偶数,则该结点的右兄弟为I+1