1.树和森林
树是一种基本的数据结构。一棵树只有一个根结点。可以没有或有多个子结点。每个子结点以及子结点以下的结点又组成了一棵树，叫做子树。在一棵树结构中，只有父结点，没有子结点的结点叫做叶子结点
森林是多棵互不相交的树的集合。对树中的每个结点而言，其子树的集合就是森林。
?
?
?
2.二叉树
二叉树是另一种树型结构，它的特点是每个结点至多只有两棵子树，并且二叉树中的子树还有左右之分，它们的次序不能颠倒。
?
?
?
3.二叉树结点的表示
Class?Node{
??????? private?Object?data; //结点中存储的数据
??????? private?Node?parent; //父结点的引用
??????? private?Node?lChild; //左结点的引用
??????? private?Node?rChild; //右结点的引用
}
?
?
?
4.二叉树的性质
??????? 1．在二叉树的第i层上至多有2^(i-1)个结点(i>=1)
??????? 2．深度为k的二叉树至多有(2^k)-1个结点(k>=1)???????
??????? 3．对任何一棵二叉树，如果其终端节点数为n0，度为2的结点数为n2,则n0=n2+1.
??????????????? 设n1为度为1的结点树，则总结点数n=n0+n1+n2
??????????????? 根据度与结点的对应关系有n=n1+2*n2+1(1表示一个根结点)
??????????????? 两式结合有n0=n2+1
4．具有n个结点的完全二叉树的深度是[]+1
完全二叉树形象的理解是它的上一层是满二叉树，而下一层要求右侧的孩子节点可以也只可以连续缺少，但是左侧不能缺少。性质4的证明如下:
假设深度为k,则该二叉树为满二叉树时结点最多为(2^k)-1,最少的情况是最后一层只有一个结点为2^(k-2)+1。则2^(k-2)+1<=n<=(2^k)-1,即<k<=
+1,因为k是整数所以k=[
]+1.
?
?
5.二叉排序树的建立和遍历
二叉排序树具有如下性质:1）左子树上所有结点的值均小于根结点的值2）右子树上所有结点的值均不小于根结点的值3）左右子树也分别是二叉排序树
建立二叉排序树的代码如下:
/**
?*?将一个整型数组存储在一个查找二叉树中
?*?@param?array?被存储的数组
?*?@return?查找二叉树的根节点
?*/
public?TreeNode?arrayToTree(int[]?array)?{
??????? TreeNode?root?=?new?TreeNode(array[0]);
?
??????? for?(int?i?=?1;?i?<?array.length;?i++)?{
??????????????? TreeNode?node?=?new?TreeNode(array[i]);
??????????????? insertNode(node,?root);
??????? }
?
??????? return?root;
}
private?void?insertNode(TreeNode?node,?TreeNode?root)?{
?
??? if?((Integer)?node.getObj()?<?(Integer)?root.getObj())?{
??????? if?(root.getLchild()?==?null){
??????????? root.setLchild(node);
??????? }else
??????????? insertNode(node,?root.getLchild());
??? }?else?{
??????? if?(root.getRchild()?==?null){
??????????? root.setRchild(node);
??????? }else
??????????? insertNode(node,?root.getRchild());
??? }
}
<!--EndFragment-->?
?
遍历排序二叉树的代码如下：
/**
?? *?中序遍历二叉树
?? *?@param?root??二叉树的根节点
?? */
public?void?traverseTree(TreeNode?root)?{
??? if?(root?!=?null)?{
??????? int?data?=?(Integer)?root.getObj();
?
??????? traverseTree(root.getLchild());
?
??????? System.out.println(data);
?
??????? traverseTree(root.getRchild());
??? }
}