java数据结构 二叉树（二）

二叉树的实现

//树的结点类 

public class TreeNode<T> {
    //存储数据
    public T data;
    //指向左孩子和右孩子结点
    public TreeNode<T> left,right;
    public TreeNode(T data, TreeNode<T> left, TreeNode<T> right) {
        super();
        this.data = data;
        this.left = left;
        this.right = right;
    }
    public TreeNode(T data) {
        super();
        this.data = data;
    }
    public TreeNode() {
        this.data = null;
        this.left = null;
        this.right =null;   
    }

    public String toString() {
        return this.data.toString();
    }

}

//二叉树实现
public class BinaryTree<T>  {
    // 根结点，结点结构为二叉链表
    public TreeNode<T> root;

    /**
     * 构造空二叉树
     */
    public BinaryTree() {
        this.root = null;
    }

    /**
     * 判断二叉树是否为空
     */

    public boolean isEmpty() {
        return this.root == null;
    }

    /** 
     * 先序遍历二叉树
     */

    public void preOrder() {
        System.out.print("先序遍历二叉树：");
        // 调用先序遍历二叉树的递归方法
        preOrder(root);
        System.out.println();
    }

    /**
     * 先根次序遍历以p结点为根的子二叉树，递归方法
     * 
     * @param p
     */
    private void preOrder(TreeNode<T> p) {
        if (p != null) {
            // 访问当前结点
            System.out.print(p.data.toString() + " ");
            // 按先序遍历当前结点的左子树，递归调用
            preOrder(p.left);
            // 按先序遍历当前结点的右子树，递归调用
            preOrder(p.right);
        }
    }

    /**
     * 中序遍历二叉树
     */

    public void inOrder() {
        System.out.print("中序遍历二叉树： ");
        inOrder(root);
        System.out.println();
    }

    /**
     * 中序遍历以p结点为根的子二叉树，递归方法
     * 
     * @param p
     */
    private void inOrder(TreeNode<T> p) {
        if (p != null) {
            // 中序遍历左子树
            inOrder(p.left);
            System.out.print(p.data.toString() + " ");
            // 中序遍历右子树
            inOrder(p.right);
        }
    }

    /**
     * 后序遍历二叉树
     */

    public void postOrder() {
        System.out.print("后序遍历二叉树： ");
        postOrder(root);
        System.out.println();
    }

    /**
     * 后序遍历以p结点为根的子二叉树，递归方法
     * 
     * @param p
     */
    private void postOrder(TreeNode<T> p) {
        if (p != null) {
            postOrder(p.left);
            postOrder(p.right);
            System.out.print(p.data.toString() + " ");
        }
    }

    /**
     * 二叉树的层次遍历
     * 
     * 按层次遍历二叉树
     */

    public void levelOrder() {
        System.out.print("层次遍历二叉树: ");
        // 创建一个空队列
        Queue<TreeNode<T>> que = new ArrayDeque<TreeNode<T>>();
        TreeNode<T> p = this.root;
        while (p != null) {
            // 访问当前结点
            System.out.print(p.data + " ");
            // 如果根节点有左孩子，p的左孩子结点入队
            if (p.left != null)
                que.add(p.left);
            // 如果根节点有右孩子，p的右孩子结点入队
            if (p.right != null)
                que.add(p.right);
            // p指向出队结点，若队列空返回null
            p = que.poll();
        }
        System.out.println();
    }

    /**
     * 返回二叉树的结点个数
     */

    public int count() {
        return count(root);
    }

    /**
     * 返回以p结点为根的子树的结点个数
     * 
     * @param p
     * @return
     */
    private int count(TreeNode<T> p) {
        if (p == null) {
            return 0;
        }
        return 1 + count(p.left) + count(p.right);
    }

    /**
     * 返回二叉树的高度
     */

    public int height() {
        return height(root);
    }

    /**
     * 返回以p结点为根的子树高度，后序遍历
     * 
     * @param p
     * @return
     */
    private int height(TreeNode<T> p) {
        if (p == null) {
            return 0;
        }
        // 返回左子树的高度
        int lh = height(p.left);
        // 返回右子树的高度
        int rh = height(p.right);
        // 当前子树高度为较高子树的高度加1
        return (lh >= rh) ? lh + 1 : rh + 1;
    }

    /**
     * 查找并返回首次出现的关键字key元素
     */

    public T search(T key) {
        return searchNode(root, key).data;
    }

    /**
     * 查找并返回首次出现的关键字为key元素结点
     * 
     * @param key
     * @return
     */
    public TreeNode<T> searchNode(T key) {
        return searchNode(root, key);
    }

    /**
     * 在以p为根的子树中查找并返回首次出现的关键字为key元素结点，若未找到返回null，先序遍历
     * 
     * @param p
     * @param key
     * @return
     */
    private TreeNode<T> searchNode(TreeNode<T> p, T key) {
        if (p == null || key == null)
            return null;

        // 查找成功，返回找到结点
        if (p.data.equals(key)) {
            return p;
        }

        // 在左子树中查找，递归调用
        TreeNode<T> find = searchNode(p.left, key);
        // 若在左子树中未找到，怎继续在右子树中查找，递归调用
        if (find == null) {
            find = searchNode(p.right, key);
        }

        // 返回查找结果
        return find;
    }

    /**
     * 返回node结点的父母结点，若空树、未找到或node为根，则返回null
     */

    public TreeNode<T> getParent(TreeNode<T> node) {
        if (root == null || node == null || node == root) {
            return null;
        }
        return getParent(root, node);
    }

    /**
     * 在以p为根的子树中查找并返回node结点的父母结点
     * 
     * @param p
     * @param node
     * @return
     */
    private TreeNode<T> getParent(TreeNode<T> p, TreeNode<T> node) {
        if (p == null)
            return null;

        if (p.left == node || p.right == node)
            return p;

        TreeNode<T> find = getParent(p.left, node);
        if (find == null) {
            find = getParent(p.right, node);
        }

        return find;
    }

    /**
     * 插入元素x作为根结点，原根结点作为其左孩子
     */

    public void insertRoot(T x) {
        this.root = new TreeNode<T>(x, this.root, null);
    }

    /**
     * 插入元素x作为p结点的孩子，若leftChild为true，插入结点作为左孩子，否则作为右孩子 返回插入结点，若p == null,
     * 则抛出空对象异常
     */

    public TreeNode<T> insertChild(TreeNode<T> p, T x, boolean leftChild) {
        if (x == null)
            return null;
        if (leftChild) {
            // 插入x结点作为p的左孩子，p原左孩子成为x的左孩子
            p.left = new TreeNode<T>(x, p.left, null);
            return p.left;
        }
        // 插入x结点作为p的右孩子，p原右孩子成为x的右孩子
        p.right = new TreeNode<T>(x, null, p.right);
        return p.right;
    }

    /**
     * 删除p结点的左或右子树，若leftChild为true，删除左子树，否则删除右子树
     * 
     * 若p == null，将抛出空对象异常
     */

    public void removeChild(TreeNode<T> p, boolean leftChild) {
        if (leftChild)
            p.left = null;
        else
            p.right = null;
    }

    /**
     * 删除二叉树的所有结点
     */

    public void removeAll() {
        this.root = null;
    }


    public String toString() {
        return toString(root);
    }

    private String toString(TreeNode<T> p) {
        if (p == null) {
            return "";
        }
        // 递归调用
        return p.data.toString() + " " + toString(p.left) + toString(p.right);
    }

    /**
     * 以先根和中根序列构建二叉树
     * 
     * @param prelist
     * @param inlist
     */
    public BinaryTree(T[] prelist, T[] inlist) {
        this.root = create(prelist, inlist, 0, 0, prelist.length);
    }

    private TreeNode<T> create(T[] prelist, T[] inlist, int preStart,
            int inStart, int n) {
        System.out.print("prelist: ");
        print(prelist, preStart, n);
        System.out.print(", inlist: ");
        print(inlist, inStart, n);
        System.out.println();

        if (n <= 0) {
            return null;
        }

        // 根结点值
        T elem = prelist[preStart];
        // 创建叶子结点
        TreeNode<T> p = new TreeNode<T>(elem);

        int i = 0;
        // 在中根序列中查找根值所在位置
        while (i < n && elem.equals(inlist[inStart + i]))
            i++;
        // 创建左子树
        p.left = create(prelist, inlist, preStart + 1, inStart, i);
        // 创建右子树
        p.right = create(prelist, inlist, preStart + 1, inStart + i + 1, n - 1
                - i);

        return p;
    }

    private void print(T[] table, int start, int n) {
        for (int i = 0; i < n; i++) {
            System.out.print(table[start + i]);
        }
    }

    /**
     * 以标明空子树的先根序列构造二叉树
     * 
     * @param prelist
     */
    public BinaryTree(T[] prelist) {
        this.root = create(prelist);
    }

    /**
     * 以标明空子树的先根序列构造一棵子二叉树，子的根值是prelist[i],返回所创建子树的根结点
     */
    private int i = 0;

    private TreeNode<T> create(T[] prelist) {
        TreeNode<T> p = null;
        if (i < prelist.length) {
            T elem = prelist[i];
            i++;
            if (elem != null) {
                // 创建叶子结点
                p = new TreeNode<T>(elem);
                // 创建p的左子树
                p.left = create(prelist);
                // 创建p的右子树
                p.right = create(prelist);
            }
        }
        return p;
    }





    /**
     * 二叉树遍历的非递归算法
     * 
     * 先序遍历二叉树的非递归算法
     */
    public void preOrderTraverse() {
        System.out.print("先根次序遍历(非递归)");
        // 创建一个空栈
        LinkedStack<TreeNode<T>> stack = new LinkedStack<TreeNode<T>>();

        TreeNode<T> p = this.root;
        // p非空或栈非空时
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                // 方位结点
                System.out.print(p.data + " ");
                // p结点入栈
                stack.push(p);
                // 进入左子树
                p = p.left;
            } else {
                // p指向出栈结点
                p = stack.pop();
                // 进入右子树
                p = p.right;
            }
        }
        System.out.println();
    }

    /**
     * 中序遍历二叉树的非递归算法
     */
    public void inOrderTraverse() {
        System.out.print("中序遍历(非递归) : ");
        LinkedStack<TreeNode<T>> stack = new LinkedStack<TreeNode<T>>();
        TreeNode<T> p = this.root;
        // p非空或栈非空时
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                // p结点入栈
                stack.push(p);
                // 进入左结点
                p = p.left;
            } else {
                // p指向出栈结点
                p = stack.pop();
                System.out.print(p.data + " ");
                // 进入右子树
                p = p.right;
            }
        }
        System.out.println();
    }

    /**
     * 遍历输出叶子结点
     */
    public void leaf() {
        leaf(root);
    }

    private void leaf(TreeNode<T> p) {
        if (p != null) {
            if (p.left == null && p.right == null)
                System.out.print(p.data.toString() + " ");
            leaf(p.left);
            leaf(p.right);
        }
    }

    /**
     * 返回以p结点为根的子树的叶子结点个数
     * 
     * @param p
     * @return
     */
    public int countLeaf(TreeNode<T> p) {
        if (p == null) {
            return 0;
        }

        if (p.left == null && p.right == null) {
            return 1;
        }

        return countLeaf(p.left) + countLeaf(p.right);
    }

    /**
     * 将首次出现的值为x的结点替换为y
     * 
     * @param x
     * @param y
     */
    public void replace(T x, T y) {
        TreeNode<T> find = searchNode(x);
        if (find != null) {
            find.data = y;
        }
    }

    /**
     * 将值为x的结点值全部替换为y
     * 
     * @param x
     * @param y
     */
    public void replaceAll(T x, T y) {
        if (x != null && y != null) {
            replaceAll(root, x, y);
        }
    }

    /**
     * 在以p为根的子树中实现全部替换
     * 
     * @param p
     * @param x
     * @param y
     */
    private void replaceAll(TreeNode<T> p, T x, T y) {
        if (p != null) {
            if (p.data.equals(x)) {
                p.data = y;
            }
            replaceAll(p.left, x, y);
            replaceAll(p.right, x, y);
        }
    }



    public void postOrderTraverse() {
        System.out.print("后序遍历(非递归): ");
        LinkedStack<TreeNode<T>> stack = new LinkedStack<TreeNode<T>>();
        TreeNode<T> p = this.root, front = null;
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                // p结点入栈
                stack.push(p);
                // 进入左子树
                p = p.left;
            } else {
                // 从左子树返回p结点，p结点不出栈

                p=stack.get();
                // p有右孩子，且右孩子没有被访问过
                if (p.right != null && p.right != front) {
                    // 进入右子树
                    p = p.right;
                    stack.push(p);
                    // 向左走
                    p = p.left;
                } else {
                    p = stack.pop();
                    System.out.print(p.data + " ");
                    front = p;
                    // front 是p在后根遍历次序下的前驱结点
                    p = null;
                }
            }
        }
        System.out.println();
    }

    /**
     * 返回x结点所在的层次，若空树或未查找到x返回-1
     * 
     * @param x
     * @return
     */
    public int getLevel(T x) {
        // 令根结点的层次为1
        return getLevel(root, 1, x);
    }

    /**
     * 在以p结点(层次为i)为根的子树中，求x结点所在的层次
     * 
     * @param p
     * @param i
     * @param x
     * @return
     */
    private int getLevel(TreeNode<T> p, int i, T x) {
        // 空树或查找不成功
        if (p == null) {
            return -1;
        }

        if (p.data.equals(x))
            return i;

        // 在左子树查找
        int level = getLevel(p.left, i + 1, x);
        if (level == -1) {
            // 继续在右子树中查找
            level = getLevel(p.right, i + 1, x);
        }
        return level;
    }

    /**
     * 比较两棵二叉树是否相等
     * 
     * @param obj
     * @return
     */
    @SuppressWarnings("unchecked")
    public boolean equals(Object obj) {
        return obj == this || obj instanceof BinaryTree
                && equals(this.root, ((BinaryTree<T>) obj).root);
    }

    /**
     * 判断以p和q结点为根的两棵子树是否相等，递归方法
     * @param p
     * @param q
     * @return
     */
    private boolean equals(TreeNode<T> p, TreeNode<T> q) {
        return p == null && q == null || p != null && q != null && p.data.equals(q.data) && 
                equals(p.left, q.left) && equals(p.right, q.right);
    }

    /**
     * 深拷贝，以已知的bitree构造二叉树
     * @param bitree
     */
    public BinaryTree(BinaryTree<T> bitree) {
        this.root = copy(bitree.root);
    }

    /**
     * 复制以p为根的子二叉树，返回新建子二叉树的根结点
     * @param p
     * @return
     */
    private TreeNode<T> copy(TreeNode<T> p) {
        if (p == null)
            return null;
        TreeNode<T> q = new TreeNode<T>(p.data);
        //复制左子树，递归调用
        q.left = copy(p.left);
        //复制右子树，递归调用
        q.right = copy(p.right);
        //返回建立子树的根结点
        return q;
    }

    /**
     * 判断是否完全二叉树
     * @return
     */
    boolean isCompleteBinaryTree() {
        if (this.root == null)
            return true;

        LinkedQueue<TreeNode<T>> que = new LinkedQueue<TreeNode<T>>();
        que.enqueue(root);
        TreeNode<T> p = null;
        while (!que.isEmpty()) {
            //p指向出对结点
            p = que.dequeue();
            //p的非空孩子结点入队
            if (p.left != null) {
                que.enqueue(p.left);
                if (p.right != null) {
                    //发现空子树，须检测队列中是否都是叶子结点
                    que.enqueue(p.right);
                } else {
                    break;
                }
            } else {
                if (p.right != null) {
                    //p的左子树空而右子树不空
                    return false;
                } else {
                    //p是叶子，须检测队列中是否都是叶子结点
                    break;
                }
            }
        }

        //检测队列中是否都是叶子结点
        while(!que.isEmpty()) {
            p= que.dequeue();
            //发现非叶子，确定不是
            if (p.left != null || p.right != null) {
                return false;
            }
        }
        return true;
    }
}

//测试二叉树
public class Test {

    public static void main(String[] args) {
        BinaryTree<String> bitree = new BinaryTree<String>();
        TreeNode<String> child_f, child_d, child_b, child_c;
        child_d = new TreeNode<String>("D", null, new TreeNode<String>("G"));
        child_b = new TreeNode<String>("B", child_d, null);
        child_f = new TreeNode<String>("F", new TreeNode<String>("H"), null);
        child_c = new TreeNode<String>("C", new TreeNode<String>("E"), child_f);
        bitree.root = new TreeNode<String>("A", child_b, child_c);
        bitree.preOrder();
        bitree.preOrderTraverse();
        bitree.inOrder();
        bitree.inOrderTraverse();
        bitree.postOrder();
        bitree.postOrderTraverse();

        bitree.levelOrder();

        }
}   

线索二叉树

若结点有左孩子，则left指针指向左孩子，否则left指针指向其前驱结点。若结点有右孩子，则right指针指向其右孩子，否则指向其后继结点。这种结构中，指向前驱和后继的指针称为线索，对二叉树以某种次序进行遍历并且加上线索的过程称为线索化，线索化了的二叉树称为线索二叉树。

这种结构我们可以在结点上设置标记，当标记为false时说明指向的为孩子结点，当标记为true时说明指向的为前驱或后继。

//线索二叉树结点
public class ThreadNode<T> {
    //存储数据
    public T data;
    //指向左孩子和右孩子结点
    public TreeNode<T> left,right;
    //标志位,标志着左右孩子是指向前驱后继还是左右孩子
    public boolean isLeftThread,isRightLeft;
    public ThreadNode() {
        this.data = null;
        this.left = null;
        this.right =null;   
    }

    public ThreadNode(T data) {
        this.data=data;
    }

    public ThreadNode(T data, TreeNode<T> left, TreeNode<T> right) {
        super();
        this.data = data;
        this.left = left;
        this.right = right;
    }

    public ThreadNode(T data, TreeNode<T> left, TreeNode<T> right, boolean isLeftThread, boolean isRightLeft) {
        super();
        this.data = data;
        this.left = left;
        this.right = right;
        this.isLeftThread = isLeftThread;
        this.isRightLeft = isRightLeft;
    }

}

线索化实质上是将二叉链表中的空指针指向相应结点的前驱或后继地址，而前驱和后继的信息只有遍历时才能得到，因此线索化的过程其实是在遍历过程中修改空指针的过程。

中序遍历线索化

    //这个结点用来保存当前结点，来做下一个结点的前驱 
    public ThreadNode<T> pre=null; 
    //使用中序遍历进行线索化
    public void inThread(ThreadNode<T> root) { 
        if(root!=null) {
            //线索化左子树
            inThread(root.left);
            //如果左子树为空，则设置前驱结点
            if(root.left==null) {
                root.isLeftThread=true;
                root.left=pre;
            }
            //设置后继结点
            if(pre!=null&&pre.right==null) {
                pre.isRightLeft=true;
                pre.right=root;
            }
            pre=root;
            //线索化右子树
            inThread(root.right);
        }
    }

中序遍历线索二叉树

    public void inThreadOrder(ThreadNode<T> root) { 
        //如果根结点不为null
         if (root != null)  
            {  
                //查找最后一个左孩子
                while(root!=null&&!root.isLeftThread) {
                    root=root.left;
                } 
                while(root!=null) { 
                    //打印数据
                    System.out.print(root.data+" "); 
                    //如果当前结点的右孩子是线索的话，让当前结点等于根节点
                    if(root.isRightLeft) {
                        root=root.right;
                    }else {
                        root=root.right;
                        while(root!=null&&!root.isLeftThread) {
                            root=root.left;
                        }
                    }

                }   
            }
    }

树、森林和二叉树的转换

在前面讲树的存储结构时，我们知道树的孩子兄弟表示法可以将一棵树用二叉链表进行存储，借助二叉链表，树和二叉树可以相互进行转换。树的孩子兄弟链表从物理结构上与二叉树的二叉链表是完全相同的，只是逻辑含义不同。

树转换为二叉树

转换步骤

    （1）树中所有相邻兄弟之间加一条线
    （2）对树中的每个结点，只保留其与第一个孩子结点之间的连线，删去其与其他孩子之间的连线
    （3）以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明

森林转换为二叉树

森林是若干棵树的集合。森林同样也可以转换为二叉树。

转换步骤

    （1）将森林中的每棵树转换成相应的二叉树
    （2）第一棵二叉树不懂，从第二棵二叉树开始，依次把后一棵的二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连在一起后，所得到的二叉树就是由森林转换得到的二叉树。

二叉树还原为树

转换步骤

    （1）若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子……都与该结点的双亲结点用线连起来。
    （2）删掉原二叉树中所有双亲结点与右孩子结点的连线
    （3）层次调整，使之结构分明

##二叉树还原为森林

怎么判断一棵二叉树是转换为树还是森林呢？只需要看这棵二叉树的根结点有没有右孩子，有就转换为森林，没有就转换为树。

转换步骤

    （1）从根结点开始，若右孩子存在，则把与右孩子结点的连线删除，再查看分离后的二叉树，若右孩子存在，则删除连线……，直到所有右孩子连线都删除，得到分离的二叉树。
    （2）再将每棵分离后的二叉树转换为树即可。

树与森林的遍历

树的遍历方法主要有以下两种：

（1）先序遍历：若树非空，则遍历方式为：访问根结点，然后从左到右，依次先序遍历每一课子树。

（2）后序遍历：若树非空，则遍历方式为：从左到右，依次后序遍历根结点的每一棵子树，然后访问根结点。

森林的遍历方法主要有以下两种：

（1）先序遍历：若森林非空，则遍历方式为：访问森林第一棵树的根结点，先序遍历第一棵树的根结点的子树，先序遍历剩余的树构成的森林。

（2）中序遍历：若森林非空，则遍历方式为：中序遍历森林中第一棵树的根结点的子树，访问第一棵树的根结点，中序遍历剩余的树构成的森林。

（3）后序遍历：若森林非空，则遍历方式为：后序遍历森林中第一棵树的根结点的子树，然后后序遍历剩余的树构成的森林，最后访问第一棵树的根结点。