首页 > 安全资讯 >

数据结构之树-二叉树(Java版本)

12-11-28

[java]/*** 链接二叉树的结点*/package 树.二叉树;public class BinaryTreeNode { private Object element;//结点元素 private BinaryTreeNode leftChild;//左子树 private BinaryTreeNode rightC...

[java]
/**
 * 链接二叉树的结点
 */ 
package 树.二叉树; 
 
public class BinaryTreeNode { 
    private Object element;//结点元素 
    private  BinaryTreeNode leftChild;//左子树  
    private  BinaryTreeNode rightChild; //右子树 
 
    /**
     * 无参构造函数
     */ 
    public BinaryTreeNode() { 
    } 
 
    /**
     * 指定结点元素的构造函数
     * @param theElement
     */ 
    public BinaryTreeNode(Object theElement) { 
        element = theElement; 
    } 
 
    /**
     * 指定结点元素,左孩子,右孩子的构造函数
     * @param theElement 结点元素
     * @param theleftChild 左孩子
     * @param therightChild 右孩子
     */ 
    public BinaryTreeNode(Object theElement, BinaryTreeNode theleftChild, 
            BinaryTreeNode therightChild) { 
        element = theElement; 
        leftChild = theleftChild; 
        rightChild = therightChild; 
    } 
 
    /**
     * 获取当前结点大的左孩子
     * @return 当前结点的左孩子
     */ 
    public BinaryTreeNode getLeftChild() { 
        return leftChild; 
    } 
 
    /**
     * 获取当前结点的右孩子
     * @return 当前结点的右孩子
     */ 
    public BinaryTreeNode getRightChild() { 
        return rightChild; 
    } 
 
    /**
     * 获取当前结点的元素
     * @return 当前结点的元素
     */ 
    public Object getElement() { 
        return element; 
    } 
 
    /**
     * 设置当前结点的左孩子
     * @param theLeftChild 当前结点设置后的左孩子
     */ 
    public void setLeftChild(BinaryTreeNode theLeftChild) { 
        leftChild = theLeftChild; 
    } 
 
    /**
     * 设置当前结点 的右孩子
     * @param theRightChild 当前结点设置后的右孩子
     */ 
    public void setRightChild(BinaryTreeNode theRightChild) { 
        rightChild = theRightChild; 
    } 
 
    /**
     * 设置当前结点的元素
     * @param theElement 当前结点设置后的元素
     */ 
    public void setElement(Object theElement) { 
        element = theElement; 
    } 
 
    /**
     * 打印当前结点元素
     */ 
    public String toString() { 
        return element.toString(); 
    } 
 

 

[java] 
/**
 * 数据结构学习之二叉树
 * @author Sking
 */ 
package 树.二叉树; 
 
import java.lang.reflect.*; 
public interface BinaryTree {//二叉树接口 
 
    /**
     * 判断二叉树是否为空
     * @return 二叉树为空则返回true,否则返回false
     */ 
    public boolean isEmpty(); 
 
    /**
     * 返回二叉树的根
     * @return 二叉树的根
     */ 
    public Object root(); 
 
    /**
     * 指定根,左孩子,右孩子创建二叉树
     * @param root 根
     * @param left 做孩子
     * @param right 右孩子
     */ 
    public void makeTree(Object root, Object left, Object right); 
 
    /**
     * 删除二叉树的左子树并返回
     * @return 二叉树的左子树
     */ 
    public BinaryTree removeLeftSubtree(); 
 
    /**
     * 删除二叉树的右子树并返回
     * @return 二叉树的右子树
     */ 
    public BinaryTree removeRightSubtree(); 
 
    /**
     * 使用指定的节点访问方法前序遍历二叉树
     * @param visit 指定的节点访问方法
     */ 
    public void preOrder(Method visit); 
 
    /**
     * 使用指定的节点访问方法中序遍历二叉树
     * @param visit 指定的节点访问方法
     */ 
    public void inOrder(Method visit); 
 
    /**
     * 使用指定的节点访问方法后序遍历二叉树
     * @param visit 指定的节点访问方法
     */ 
    public void postOrder(Method visit); 
 
    /**
     * 使用指定的节点访问方法层序遍历二叉树
     * @param visit 指定的节点访问方法
     */ 
    public void levelOrder(Method visit); 

 

[java] 
/**
 * 二叉树的遍历类,含有前序,后序,中序,层序遍历
 * @author Sking
 */ 
package 树.二叉树; 
import 队列.ArrayQueue; 
public class BinaryTreeTraversal { 
    /**
     * 访问指定二叉树结点
     * @param t 被访问的二叉树结点
     */ 
    public static void visit(BinaryTreeNode t) { 
        System.out.print(t.getElement() + " "); 
    } 
 
    /**
     * 对指定二叉树执行前序遍历
     * @param t 被遍历的二叉树根节点
     */ 
    public static void preOrder(BinaryTreeNode t) { 
        if (t != null) { 
            visit(t); //访问子树的根节点 
            preOrder(t.getLeftChild()); //访问左子树 
            preOrder(t.getRightChild()); //访问右子树 
        } 
    } 
 
    /**
     * 对指定的二叉树执行中序遍历
     * @param t 被遍历的二叉树根节点
     */ 
    public static void inOrder(BinaryTreeNode t) { 
        if (t != null) { 
            inOrder(t.getLeftChild()); //访问二叉树的左子树 
            visit(t); //访问根 
            inOrder(t.getRightChild()); //访问二叉树的右子树 
        } 
    } 
 
    /**
     * 对指定的二叉树执行后序遍历
     * @param t 被遍历的二叉树的根节点
     */ 
    public static void postOrder(BinaryTreeNode t) { 
        if (t != null) { 
            postOrder(t.getLeftChild()); //访问左子树 
            postOrder(t.getRightChild()); //访问右子树 
            visit(t); //访问根 
        } 
    } 
 
    /**
     * 对指定的二叉树指定层序遍历
     * 使用辅助队列
     * @param t 被遍历的二叉树的根节点
     */ 
    public static void levelOrder(BinaryTreeNode t) { 
        ArrayQueue q = new ArrayQueue(10);//辅助队列 
        while (t != null) { 
            visit(t);//访问根节点 
            if (t.getLeftChild() != null) 
                q.put(t.getLeftChild());//左孩子节点入列 
            if (t.getRightChild() != null) 
                q.put(t.getRightChild());//右孩子节点入列 
            t = (BinaryTreeNode) q.get();//取出下一个被访问的节点 
        } 
    } 

 

[java] 
/**
 * 链接二叉树的实现
 * @author Sking
 */ 
package 树.二叉树.链接二叉树; 
 
import java.lang.reflect.*; 
 
import 树.二叉树.*; 
import 队列.ArrayQueue; 
 
public class LinkedBinaryTree implements BinaryTree { 
    private BinaryTreeNode root;// 二叉树的根节点 
    static Method visit; // 访问节点的方法 
    static Object[] visitArgs = new Object[1]; // parameters of visit method 
    static int count; // counter 
    static Class<?>[] paramType = { BinaryTreeNode.class };// 访问节点方法的参数类型 
    static Method theAdd1; // 实现计数器增加的方法 
    static Method theOutput; // 实现输出节点元素的方法 
    // method to initialize class data members 
    static { 
        try { 
            Class<LinkedBinaryTree> lbt = LinkedBinaryTree.class; 
            theAdd1 = lbt.getMethod("add1", paramType); 
            theOutput = lbt.getMethod("output", paramType); 
        } catch (Exception e) { 
        } 
        // exception not possible 
    } 
 
    // only default constructor available 
 
    // class methods 
    /** visit method that outputs element */ 
    public static void output(BinaryTreeNode t) { 
        System.out.print(t.getElement() + " "); 
    } 
 
    /** visit method to count nodes */ 
    public static void add1(BinaryTreeNode t) { 
        count++; 
    } 
 
    /**
     * 判断二叉树是否为空
     */ 
    public boolean isEmpty() { 
        return getRoot() == null; 
    } 
 
    public Object root() { 
        return (getRoot() == null) ? null : getRoot().getElement(); 
    } 
 
    /**
     * 返回根节点
     * 
     * @return 二叉树的根节点
     */ 
    public BinaryTreeNode getRoot() { 
        return root; 
    } 
 
    /**
     * 设置二叉树的根节点
     * 
     * @param root
     *            设置后的根节点
     */ 
    public void setRoot(BinaryTreeNode root) { 
        this.root = root; 
    } 
 
    /**
     * set this to the tree with the given root and subtrees CAUTION: does not
     * clone left and right
     */ 
    public void makeTree(Object root, Object left, Object right) { 
        this.setRoot(new BinaryTreeNode(root, ((LinkedBinaryTree) left) 
                .getRoot(), ((LinkedBinaryTree) right).getRoot())); 
    } 
 
    /**
     * remove the left subtree
     * 
     * @throws IllegalArgumentException
     *             when tree is empty
     * @return removed subtree
     */ 
    public BinaryTree removeLeftSubtree() { 
        if (getRoot() == null) 
            throw new IllegalArgumentException("tree is empty"); 
 
        // detach left subtree and save in leftSubtree 
        LinkedBinaryTree leftSubtree = new LinkedBinaryTree(); 
        leftSubtree.setRoot(getRoot().getLeftChild()); 
        getRoot().setLeftChild(null); 
        return (BinaryTree) leftSubtree; 
    } 
 
    /**
     * remove the right subtree
     * 
     * @throws IllegalArgumentException
     *             when tree is empty
     * @return removed subtree
     */ 
    public BinaryTree removeRightSubtree() { 
        if (getRoot() == null) 
            throw new IllegalArgumentException("tree is empty"); 
 
        // detach right subtree and save in rightSubtree 
        LinkedBinaryTree rightSubtree = new LinkedBinaryTree(); 
        rightSubtree.setRoot(getRoot().getRightChild()); 
        getRoot().setRightChild(null); 
 
        return (BinaryTree) rightSubtree; 
    } 
 
    /** preorder traversal */ 
    public void preOrder(Method visit) { 
        LinkedBinaryTree.visit = visit; 
        thePreOrder(getRoot()); 
    } 
 
    /** actual preorder traversal method */ 
    static void thePreOrder(BinaryTreeNode t) { 
        if (t != null) { 
            visitArgs[0] = t; 
            try { 
                visit.invoke(null, visitArgs); 
            } // visit tree root 
            catch (Exception e) { 
                System.out.println(e); 
            } 
            thePreOrder(t.getLeftChild()); // do left subtree 
            thePreOrder(t.getRightChild()); // do right subtree 
        } 
    } 
 
    /** inorder traversal */ 
    public void inOrder(Method visit) { 
        LinkedBinaryTree.visit = visit; 
        theInOrder(getRoot()); 
    } 
 
    /** actual inorder traversal method */ 
    static void theInOrder(BinaryTreeNode t) { 
        if (t != null) { 
            theInOrder(t.getLeftChild()); // do left subtree 
            visitArgs[0] = t; 
            try { 
                visit.invoke(null, visitArgs); 
            } // visit tree root 
            catch (Exception e) { 
                System.out.println(e); 
            } 
            theInOrder(t.getRightChild()); // do right subtree 
        } 
    } 
 
    /** postorder traversal */ 
    public void postOrder(Method visit) { 
        LinkedBinaryTree.visit = visit; 
        thePostOrder(getRoot()); 
    } 
 
    /** actual postorder traversal method */ 
    static void thePostOrder(BinaryTreeNode t) { 
        if (t != null) { 
            thePostOrder(t.getLeftChild()); // do left subtree 
            thePostOrder(t.getRightChild()); // do right subtree 
            visitArgs[0] = t; 
            try { 
                visit.invoke(null, visitArgs); 
            } // visit tree root 
            catch (Exception e) { 
                System.out.println(e); 
            } 
        } 
    } 
 
    /** level order traversal */ 
    public void levelOrder(Method visit) { 
        ArrayQueue q = new ArrayQueue(10); 
        BinaryTreeNode t = getRoot(); 
        while (t != null) { 
            visitArgs[0] = t; 
            try { 
                visit.invoke(null, visitArgs); 
            } // visit tree root 
            catch (Exception e) { 
                System.out.println(e); 
            } 
 
            // put t's children on queue 
            if (t.getLeftChild() != null) 
                q.put(t.getLeftChild()); 
            if (t.getRightChild() != null) 
                q.put(t.getRightChild()); 
 
            // get next node to visit 
            t = (BinaryTreeNode) q.get(); 
        } 
    } 
 
    /** output elements in preorder */ 
    public void preOrderOutput() { 
        preOrder(theOutput); 
    } 
 
    /** output elements in inorder */ 
    public void inOrderOutput() { 
        inOrder(theOutput); 
    } 
 
    /** output elements in postorder */ 
    public void postOrderOutput() { 
        postOrder(theOutput); 
    } 
 
    /** output elements in level order */ 
    public void levelOrderOutput() { 
        levelOrder(theOutput); 
    } 
 
    /** count number of nodes in tree */ 
    public int size() { 
        count = 0; 
        preOrder(theAdd1); 
        return count; 
    } 
 
    /**
     * 返回二叉树的高度
     * 
     * @return 二叉树的高度
     */ 
    public int height() { 
        return theHeight(getRoot()); 
    } 
 
    /**
     * 返回以指定结点为根的二叉树的高度
     * 
     * @param t
     *            二叉树的根节点
     * @return 二叉树的高度
     */ 
    static int theHeight(BinaryTreeNode t) { 
        if (t == null) 
            return 0; 
        int hl = theHeight(t.getLeftChild()); 
        int hr = theHeight(t.getRightChild()); 
        if (hl > hr) 
            return ++hl; 
        else 
            return ++hr; 
    } 

 

[java]
/**
 * 二叉树问题集锦
 * @author Sking
 */ 
package 树.二叉树.二叉树问题总结; 
 
import 栈.ArrayStack; 
import 树.二叉树.*; 
import 树.二叉树.链接二叉树.LinkedBinaryTree; 
import 队列.ArrayQueue; 
 
public class BinaryTreeQuestion { 
    /**
     * (1) 输出完全括弧化的中序遍历形式
     * 
     * @param t
     *            被遍历的二叉树根节点
     */ 
    public static void infix(BinaryTreeNode t) { 
        if (t != null) { 
            System.out.print("("); 
            infix(t.getLeftChild()); 
            System.out.print(t.getElement().toString()); 
            infix(t.getRightChild()); 
            System.out.print(")"); 
        } 
    } 
 
    /**
     * (2)确定链接二叉树的高度
     * 
     * @param t
     *            指定的二叉树根节点
     * @return 二叉树的高度
     */ 
    public static int height(BinaryTreeNode t) { 
        if (t != null) { 
            int hLeft = height(t.getLeftChild()); 
            int hRight = height(t.getRightChild()); 
            return Math.max(hLeft, hRight) + 1; 
        } else 
            return 0; 
    } 
 
    /**
     * (3)确定链接二叉树节点数最多的层,根为第一层
     * 
     * @param t
     *            指定二叉树的根节点
     * @return 连接二叉树节点最多的层
     */ 
    public static int maxLevel(BinaryTreeNode t) { 
        if (t == null) 
            return 0; 
        int maxLevel = 0;// 当前结点个数对多的层 
        int maxNodes = 0;// 当前单层最大节点个数 
        // endOfLevel表示层结束标记 
        BinaryTreeNode endOfLevel = new BinaryTreeNode(); 
        ArrayQueue q = new ArrayQueue(); 
        q.put(t); 
        q.put(endOfLevel);// 加入第一层的结束标记 
        int currentLevel = 1;// currentLevel表示当前层 
        int numOfNodes = 0;// 当前层的节点个数 
 
        while (true) { 
            BinaryTreeNode p = (BinaryTreeNode) q.get(); 
            if (p == endOfLevel) {// 当前层统计结束 
                if (numOfNodes > maxNodes) { 
                    maxNodes = numOfNodes; 
                    maxLevel = currentLevel; 
                } else if (numOfNodes == 0) 
                    return maxLevel;// 底层统计结束 
                currentLevel++; 
                numOfNodes = 0; 
                // 每当统计完一层时,都要为下一层加入标记endOfLevel 
                // (此时下一层的结点已经全部在队列当中,层序遍历的结果) 
                q.put(endOfLevel); 
            } else {// 当前层未统计完毕 
                numOfNodes++; 
                if (p.getLeftChild() != null) 
                    q.put(p.getLeftChild()); 
                if (p.getRightChild() != null) 
                    q.put(p.getRightChild()); 
            } 
        } 
    } 
 
    /*
     * (4)使用前序遍历制作二叉树的副本
     */ 
    public static BinaryTreeNode preOrderClone(BinaryTreeNode t) { 
        if (t != null) { 
            BinaryTreeNode ct = new BinaryTreeNode(t.getElement()); 
            ct.setLeftChild(preOrderClone(t.getLeftChild())); 
            ct.setRightChild(preOrderClone(t.getRightChild())); 
            return ct; 
        } else 
            return null; 
    } 
 
    /*
     * (5)使用后序遍历制作二叉树的副本
     */ 
    public static BinaryTreeNode postOrderClone(BinaryTreeNode t) { 
        if (t != null) { 
            BinaryTreeNode cLeft = postOrderClone(t.getLeftChild()); 
            BinaryTreeNode cRight = postOrderClone(t.getRightChild()); 
            return new BinaryTreeNode(t.getElement(), cLeft, cRight); 
        } else 
            return null; 
    } 
 
    /**
     * (6)判断结点u是否为结点v的子孙
     * 
     * @param u
     *            节点u
     * @param v
     *            节点v
     * @return 如果u是节点v的子孙,则返回true,否则返回false
     */ 
    public static boolean Is_Descendant(BinaryTreeNode u, BinaryTreeNode v) { 
        if (u == v) 
            return true; 
        else { 
            if (v.getLeftChild() != null) 
                if (Is_Descendant(u, v.getLeftChild())) 
                    return true; 
            if (v.getRightChild() != null) 
                if (Is_Descendant(u, v.getRightChild())) 
                    return true; 
        } 
        return false; 
    } 
 
    /**
     * (7)判断两棵二叉树是否相似
     * 
     * @param b1
     *            第一课二叉树的根节点
     * @param b2
     *            第二课二叉树的根节点
     * @return 如果两棵二叉树相似则返回true,否则false
     */ 
    public boolean Bitree_sim(BinaryTreeNode b1, BinaryTreeNode b2) { 
        if (b1 == null && b2 == null) 
            return true; 
        else if (b1 != null && b2 != null 
                && Bitree_sim(b1.getLeftChild(), b2.getLeftChild()) 
                && Bitree_sim(b1.getRightChild(), b2.getRightChild())) 
            return true; 
        else 
            return false; 
    } 
 
    /**
     * (8)中序遍历二叉树的非递归算法
     * 
     * @param t
     *            被遍历的二叉树根节点
     */ 
    public static void InOrderTraverse(BinaryTreeNode t) { 
        ArrayStack stack = new ArrayStack();// 辅助栈 
        BinaryTreeNode p = t;// 当前考虑子树的根节点 
        // 当p==null并且stack.empty()为true时退出while循环 
        while (p != null || !stack.empty()) { 
            // 沿着左孩子路径循环走到“最左边” 
            if (p != null) {// 当前子树不为空 
                stack.push(p);// 当前结点入栈 
                p = p.getLeftChild();// 获取当前结点的左孩子 
            } else {// p==null,当前子树为空 
                p = (BinaryTreeNode) stack.pop();// 出栈 
                System.out.print(p.getElement().toString() + " "); 
                p = p.getRightChild();// 获取当前结点的右孩子 
            } 
        } 
    } 
 
    /**
     * (9)中序遍历二叉树的非递归算法2
     * 
     * @param t
     *            被遍历的二叉树根节点
     */ 
    public static void InOrderTraverse2(BinaryTreeNode t) { 
        ArrayStack stack = new ArrayStack(); 
        BinaryTreeNode p;// 当前考虑节点 
        stack.push(t); 
        while (!stack.empty()) { 
            // 沿着左孩子路径循环走到“最左边” 
            // 当stack.peek()==null的时候退出while循环,表示到达了“最左边” 
            while ((p = (BinaryTreeNode) stack.peek()) != null) 
                stack.push(p.getLeftChild()); 
            p = (BinaryTreeNode) stack.pop();// 弹出null元素 
            if (!stack.empty()) { 
                p = (BinaryTreeNode) stack.pop(); 
                System.out.print(p.getElement().toString() + " "); 
                stack.push(p.getRightChild()); 
            } 
        } 
    } 
 
    /**
     * (10)先序遍历二叉树的非递归算法
     * 
     * @param t
     *            被遍历二叉树的根节点
     */ 
    public static void PreOrder_Nonrecursive(BinaryTreeNode t) { 
        ArrayStack stack = new ArrayStack();// 辅助栈 
        BinaryTreeNode p;// 当前被考虑节点 
        stack.push(t); 
        while (!stack.empty()) { 
            while ((p = (BinaryTreeNode) stack.peek()) != null) { 
                // 先打印根节点,再将左孩子入栈 
                System.out.print(p.getElement().toString() + " "); 
                stack.push(p.getLeftChild()); 
            } 
            p = (BinaryTreeNode) stack.pop();// 弹出null元素 
            if (!stack.empty()) { 
                p = (BinaryTreeNode) stack.pop(); 
                stack.push(p.getRightChild()); 
            } 
        } 
    } 
 
    /**
     * (11)计算二叉树中叶子结点的数目
     * 
     * @param t
     *            指定二叉树
     * @return 二叉树的叶子节点个数
     */ 
    public static int LeafCount(BinaryTreeNode t) { 
        if (t == null) 
            return 0; 
        else if (t.getLeftChild() == null && t.getRightChild() == null) 
            return 1; 
        else 
            return LeafCount(t.getLeftChild()) + LeafCount(t.getRightChild()); 
    } 
 
     
    /**
     * (12)计算二叉树中以值为x的结点为根的子树深度
     * 
     * @param t
     *            指定的二叉树
     * @param x
     *            值
     * @return 如果找到值为x的节点则返回该节点深度,否则返回-1
     */ 
    public static void Get_sub_Depth(BinaryTreeNode t, Object x,int[] depth) { 
            if (t.getElement() == x) { 
                depth[0]=Get_Depth(t); 
            } else { 
                if (t.getLeftChild() != null) 
                    Get_sub_Depth(t.getLeftChild(), x,depth); 
                if (t.getRightChild() != null) 
                    Get_sub_Depth(t.getRightChild(), x,depth); 
            } 
    } 
 
    /**
     * (13)辅助方法,用于确定指定二叉树结点的深度 深度是从底层开始向上递增,底层深度为1
     * 
     * @param t
     *            指定二叉树节点
     * @return 指定二叉树节点的深度
     */ 
    public static int Get_Depth(BinaryTreeNode t) { 
        if (t == null) 
            return 0; 
        else { 
            int m = Get_Depth(t.getLeftChild()); 
            int n = Get_Depth(t.getRightChild()); 
            return (m > n ? m : n) + 1; 
        } 
    } 
 
    /*
     * (13)后序遍历二叉树的非递归算法,使用栈 为了区别两次进栈的不同处理方法,
     * 在堆栈中增加一个mark域,mark=0 表示刚刚访问此结点,mark=1表示左
     * 子树处理结束返回,mark=2表示右 子树处理结束返回,每次根据栈顶元素的
     * mark域决定执行什么工作。只有 当左右子树都处理完毕后才能对该结点调用打
     * 印操作,而且存储mark是在 访问左右子树之前就执行。
     */ 
    class PMType { 
        BinaryTreeNode ptr; 
        int mark; 
 
        public PMType(BinaryTreeNode ptr, int mark) { 
            this.ptr = ptr; 
            this.mark = mark; 
        } 
    } 
 
    public void PostOrder_Stack(BinaryTreeNode t) { 
        PMType a; 
        ArrayStack stack = new ArrayStack(); 
        stack.push(new PMType(t, 0)); 
        while (!stack.empty()) { 
            a = (PMType) stack.pop(); 
            switch (a.mark) { 
            case 0: 
                stack.push(new PMType(a.ptr, 1)); 
                if (a.ptr.getLeftChild() != null) 
                    stack.push(new PMType(a.ptr.getLeftChild(), 0)); 
                break; 
            case 1: 
                stack.push(new PMType(a.ptr, 2)); 
                if (a.ptr.getRightChild() != null) 
                    stack.push(new PMType(a.ptr.getRightChild(), 0)); 
                break; 
            case 2: 
                System.out.print(a.ptr.getElement().toString() + " "); 
            } 
        } 
    } 
 
    /**
     * (14)求树节点的子孙总数 为了能用一个统一的计算公式计算子孙数目,
     * 当t为空指针的时候,访问设置为-1而不是0
     */ 
    public int DescNum(BinaryTreeNode t) { 
        if (t == null) 
            return -1; 
        else 
            return (DescNum(t.getLeftChild()) + DescNum(t.getRightChild()) + 2); 
    } 
 
    /**
     * (15)判断二叉树是否为完全二叉树 思想:不管当前结点是否有左右孩子,都入列,这样当树是完全二叉树
     * 时候,遍历时候得到的是一个连续的不包含空指针的序列,反之则有空指针。 另外可能出现一种情况:队列的最后是连续的空指针,此时也是完全二叉树,
     * 这种情况在算法中的表现是每一次循环都只执行到if (btn == null)flag = true;
     * 如果之后没有出现非空指针则队列将空,return true,如果之后出现非空指针 算法将执行语句else if (flag) return
     * false;
     */ 
    public boolean IsFullBinaryTree(BinaryTreeNode t) { 
        ArrayQueue queue = new ArrayQueue(); 
        BinaryTreeNode btn; 
        boolean flag = false; 
        queue.put(t); 
        while (!queue.isEmpty()) { 
            btn = (BinaryTreeNode) queue.get(); 
            if (btn == null) 
                flag = true; 
            else if (flag) 
                return false; 
            else { 
                queue.put(btn.getLeftChild()); 
                queue.put(btn.getRightChild()); 
            } 
        } 
        return true; 
    } 
 
    /**
     * (16)求二叉树中结点p,q的最近共同祖先
     */ 
    boolean found = false; 
 
    public BinaryTreeNode Find_Near_Ancient(BinaryTreeNode t, BinaryTreeNode p, 
            BinaryTreeNode q) { 
        int i; 
        BinaryTreeNode[] pathp = new BinaryTreeNode[100]; 
        BinaryTreeNode[] pathq = new BinaryTreeNode[100]; 
        // 将根t到两个结点p,q的路径存放在数组当中 
        FindPath(t, p, pathp, 0); 
        found = false; 
        FindPath(t, q, pathq, 0); 
        for (i = 0; pathq[i] == pathp[i] && pathp[i] != null; i++); 
        //当pathq[i]!=pathp[i]或者pathq[i]==pathp[i]&&pathp[i]==null时退出 
        return pathp[--i]; 
    } 
 
    public void FindPath(BinaryTreeNode t, BinaryTreeNode p, 
            BinaryTreeNode[] path, int i) { 
        if (t == p) { 
            found = true; 
            return; 
        } 
        path[i] = t; 
        if (t.getLeftChild() != null) 
            FindPath(t.getLeftChild(), p, path, i + 1); 
        if (t.getRightChild() != null && !found) 
            FindPath(t.getRightChild(), p, path, i + 1); 
        if (!found) 
            path[i] = null;// 回溯 
    } 
 
    /**
     * (17)非递归复制二叉树
     */ 
    public BinaryTreeNode Bitree_Copy_Nonrecursive(BinaryTreeNode t, 
            BinaryTreeNode u) { 
        BinaryTreeNode q; 
        BinaryTreeNode p; 
        ArrayStack stack1 = new ArrayStack(); 
        ArrayStack stack2 = new ArrayStack(); 
        stack1.push(t); 
        u.setElement(t.getElement()); 
        q = u; 
        stack2.push(u); 
        while (!stack1.empty()) { 
            while ((p = (BinaryTreeNode) stack1.peek()) != null) { 
                q.setLeftChild(new BinaryTreeNode()); 
                q = q.getLeftChild(); 
                q.setElement(p.getElement()); 
                stack1.push(p.getLeftChild()); 
                stack2.push(q); 
            } 
            p = (BinaryTreeNode) stack1.pop(); 
            q = (BinaryTreeNode) stack2.pop(); 
            if (!stack1.empty()) { 
                p = (BinaryTreeNode) stack1.pop(); 
                q = (BinaryTreeNode) stack2.pop(); 
                q.setRightChild(new BinaryTreeNode()); 
                q = q.getRightChild(); 
                q.setElement(p.getElement()); 
                stack1.push(p.getRightChild()); 
                stack2.push(q); 
            } 
        } 
        return u; 
    } 
 
    /**
     * (18)交换所有结点的左右子树
     */ 
    public void Bitree_Revolute(BinaryTreeNode t) { 
        BinaryTreeNode temp; 
        temp = t.getLeftChild(); 
        t.setLeftChild(t.getRightChild()); 
        t.setRightChild(temp); 
        if (t.getLeftChild() != null) 
            Bitree_Revolute(t.getLeftChild()); 
        if (t.getRightChild() != null) 
            Bitree_Revolute(t.getRightChild()); 
    } 
 
    /**
     * (18)删除所有以元素x为根的子树
     */ 
    public void Del_Sub_x(BinaryTreeNode t, Object x) { 
        if (t.getElement() == x) 
            Del_Sub(t); 
        else { 
            if (t.getLeftChild() != null) 
                Del_Sub_x(t.getLeftChild(), x); 
            if (t.getRightChild() != null) 
                Del_Sub_x(t.getRightChild(), x); 
        } 
    } 
 
    public void Del_Sub(BinaryTreeNode t) { 
        if (t.getLeftChild() != null) 
            Del_Sub(t.getLeftChild()); 
        if (t.getRightChild() != null) 
            Del_Sub(t.getRightChild()); 
        t = null;// 将其赋值为null表示删除t 
    } 

 

相关文章
最新文章
热点推荐