二叉树及用Java实现二叉树

二叉树的概念此处就不赘述了。

二叉搜索树，又名二叉查找树，二叉排序树，若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉搜索树。

---

下面附上用Java实现二叉树的代码：

public class TreeNode {

    int val;

    TreeNodeleft;

    TreeNoderight;

    TreeNode(int x) {val = x; }

    //生成二叉树

    public TreeNodecreateBT(Integer[] root,int index){

    TreeNode tn =null;

        if (index < root.length) {

            Integer value = root[index];

            if (value ==null) {

                return null;

            }

            tn =new TreeNode(value);

            tn.left = createBT(root, 2*index+1);

            tn.right = createBT(root, 2*index+2);

            return tn;

        }

    return tn;

    }

    //比较两棵二叉树是否相等

    public boolean isSameTree(TreeNode p,TreeNode q){

        if(p==null&&q==null){

            return true;

        }

        if(p!=null&&q==null){

            return false;

        }

        if(p==null&&q!=null){

            return false;

        }

        if(p.val!=q.val){

            return false;

        }

    return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);

    }

}