讨论/算法和数据结构/二叉树查找算法/
二叉树查找算法
向大佬求救:
二叉树的查找算法: 不知道为什么,测试发现查找结果为null,请大佬们指教
(方法是对着书本写的,测试类是自己写的)

BiTree类:

public class BiTree {
    private BiTreeNode root;

    public BiTree() {
        this.root = null;
    }

    public BiTree(BiTreeNode root) {
        this.root = root;
    }

    public BiTreeNode getRoot() {
        return root;
    }

    public void setRoot(BiTreeNode root) {
        this.root = root;
    }
    public BiTree(String preOrder, String inOrder, int preIndex, int inIndex, int count) {
        if (count > 0) {
            char r = preOrder.charAt(preIndex);
            int i = 0;
            for (; i < count; i++) {
                if (r == inOrder.charAt(i + inIndex))
                    break;
                root = new BiTreeNode(r);
                root.setLchild(new BiTree(preOrder, inOrder, preIndex + 1, inIndex, i).root);
                root.setRchild(new BiTree(preOrder, inOrder, preIndex + 1, inIndex + i + 1, count - i - 1).root);
            }
        }
    }
    public BiTreeNode searchNode(BiTreeNode T, Object x) {
        if (T != null) {
            if (T.getData().equals(x))
                return T;
            else {
                BiTreeNode lresult = searchNode(T.getLchild(), x);
                return lresult != null ? lresult : searchNode(T.getRchild(), x);
            }
        }
        return null;
    }
    public void postRootTraverse() throws Exception {// 非递归后根遍历
        BiTreeNode T = root;
        if (T != null) {
            LinkStack S = new LinkStack();// 构造链栈
            S.push(T);// 根结点进栈
            Boolean flag;// 访问标记
            BiTreeNode p = null;// p指向刚被访问的结点
            while (!S.isEmpty()) {
                while (S.peek() != null) {// 栈顶元素非空
                    S.push(((BiTreeNode) S.peek()).getLchild());
                }
                S.pop();// 空结点出栈
                while (!S.isEmpty()) {
                    T = (BiTreeNode) S.peek();// 查看栈顶元素
                    if (T.getRchild() == null || T.getRchild() == p) {
                        System.out.print(T.getData());// 访问结点
                        S.pop();// 移除栈顶元素
                        p = T;// p指向刚被访问的结点
                        flag = true;// 设置访问标记
                    } else {
                        S.push(T.getRchild());// 右孩子结点入栈
                        flag = false;// 设置未被访问标志
                    }
                    if (!flag)
                        break;
                }
            }
        }
    }
}

测试类:

public class BiTreeTest1 {
    public static void main(String[] args) throws Exception {
        String preOrder="ABDGHCEFI";
        String inOrder="GDHBAECIF";
        BiTree T=new BiTree(preOrder,inOrder,0,0,preOrder.length());
        System.out.println("后根遍历为:");
        T.postRootTraverse();
        String c="C";
        System.out.println();
        BiTreeNode search = T.searchNode(T.getRoot(), c);
        System.out.println(search);
        
        
    }
}
展开讨论
共 0 个讨论
无讨论