森林、树、二叉树学习小结

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());

    }

}

<!--EndFragment-->