[数据结构与算法]二叉树的常规操作（Java实现）

建立二叉链式存储结构下的二叉树结点类

ackage BiTree;

import LinkStack.LinkStack;
import Queue.LinkQueue;

public class BiTreeNode {
    public Object data;
    public BiTreeNode lChild;
    public BiTreeNode rChild;

    public BiTreeNode(){
        this(null);
    }
    public BiTreeNode(Object data){
        this(data,null,null);
    }
    public BiTreeNode(Object data,BiTreeNode lChild,BiTreeNode rChild){
        this.data = data;
        this.lChild = lChild;
        this.rChild = rChild;
    }

}

由标明空子树的先根遍历序列建立一棵二叉树

private static int index = 0;       //用于记录preStr的索引值
public BiTree(String preStr){
    char c = preStr.charAt(index++);
    if (c != '#'){
        root = new BiTreeNode(c);
        root.lChild = new BiTree(preStr).root;
        root.rChild = new BiTree(preStr).root;
    }else
        root = null;
}

先根遍历二叉树

1. 递归算法

public void preRootTraverse(BiTreeNode T) {
    if (T != null){
        System.out.print(T.data);
        preRootTraverse(T.lChild);
        preRootTraverse(T.rChild);
    }

2. 非递归算法

public void preRootTraverse() throws Exception {
        BiTreeNode T = root;
        if (T != null){
            LinkStack S = new LinkStack();
            S.push(T);
            while(!S.isEmpty()){
                T = (BiTreeNode) S.pop();
                System.out.print(T.data);
                while(T != null){
                    if (T.lChild != null)
                        System.out.print(T.lChild.data);
                    if (T.rChild != null)
                        S.push(T.rChild);
                    T = T.lChild;
                }
            }
        }
    }

中根遍历二叉树

3. 递归算法

public void inRootTraverse(BiTreeNode T){
    if (T != null){
        inRootTraverse(T.lChild);
        System.out.print(T.data);
        inRootTraverse(T.rChild);
    }
}

4. 非递归算法

public void inRootTraverse() throws Exception{
        BiTreeNode T = root;
        if (T != null){
            LinkStack S = new LinkStack();
            S.push(T);
            while(!S.isEmpty()){
                while(S.peek() != null){
                    S.push(((BiTreeNode)S.peek()).lChild);
                }
                S.pop();
                if (!S.isEmpty()){
                    T = (BiTreeNode) S.pop();
                    System.out.print(T.data);
                    S.push(T.rChild);
                }
            }
        }
    }

后根遍历二叉树

1. 递归算法

public void postRootTraverse(BiTreeNode T){
    if (T != null){
        postRootTraverse(T.lChild);
        postRootTraverse(T.rChild);
        System.out.print(T.data);;
    }
}

2. 非递归算法

public void postRootTraverse() throws Exception{
        BiTreeNode T = root;
        if(T != null){
            LinkStack S = new LinkStack();
            S.push(T);
            Boolean flag;
            BiTreeNode p = null;
            while(!S.isEmpty()){
                while(S.peek() != null){
                    S.push(((BiTreeNode)S.peek()).lChild);
                }
                S.pop();
                while(!S.isEmpty()){
                    T = (BiTreeNode) S.peek();
                    if (T.rChild == null || T.rChild == p){         //p用于在结点的右子树遍历完了且全部出栈了，此时的栈顶结点的左右子树均遍历完了，所以需要对当前结点进行出栈操作
                        System.out.print(T.data);
                        S.pop();
                        p = T;
                        flag = true;
                    }else{
                        S.push(T.rChild);
                        flag = false;       //当右子树存在，需要将右子树入栈最为新的栈顶结点，这时需要重新遍历栈顶结点的左子树，所以需要用flag来判断遍历右子树循环的break
                    }
                    if (!flag){
                        break;
                    }
                }
            }
        }
    }

层次遍历二叉树（从左向右）

public void leverTraverse() throws Exception{
    BiTreeNode T = root;
    if (T != null){
        LinkQueue L = new LinkQueue();
        L.offer(T);
        while (!L.isEmpty()){
            T = (BiTreeNode) L.poll();
            System.out.println(T.data);
            if (T.lChild != null)
                L.offer(T.lChild);
            if (T.rChild != null)
                L.offer(T.rChild);
        }
    }
}

统计二叉树结点数目

public int countNode1(BiTreeNode T) throws Exception{
    int count = 0;
    if (T != null){
        LinkQueue L = new LinkQueue();
        L.offer(T);
        while(!L.isEmpty()){
            T = (BiTreeNode) L.poll();
            ++count;
            if (T.lChild != null)
                L.offer(T.lChild);
            if (T.rChild != null)
                L.offer(T.rChild);
        }
    }
    return count;
}

统计叶节点数目

public int countNode2(BiTreeNode T) throws Exception{
    int count = 0;
    if (T != null){
        LinkQueue L = new LinkQueue();
        L.offer(T);
        while(!L.isEmpty()){
            T = (BiTreeNode) L.poll();
            if (T.lChild == null && T.rChild == null){
                System.out.println(T.data);
                ++count;
            }else{
                if (T.lChild != null)
                    L.offer(T.lChild);
                if (T.rChild != null)
                    L.offer(T.rChild);
            }
        }
    }

求二叉树深度

递归算法，递归遍历左子树和右子树，每次深度+1，最后返回其中深度最大的那个

public int getDepth(BiTreeNode T){
    if (T == null)
        return 0;
    else
        return getDepth(T.lChild) > getDepth(T.rChild) ? getDepth(T.lChild) + 1 : getDepth(T.rChild) + 1;
}

节点数据的查找

public BiTreeNode searchNode(BiTreeNode T,Object x){
    if (T != null) {
        if (T.data.equals(x))
        return T;
    else{
            BiTreeNode lresult = searchNode(T.lChild, x);       //递归查找左子树
            return lresult != null ? lresult : searchNode(T.rChild, x);
        }
    }
    return null;
}

判断两棵树相等

public boolean isEqual(BiTreeNode T1,BiTreeNode T2){
    if (T1 == null && T2 == null){
        return true;
    }
    //层级式判断
    if (T1 != null && T2 != null){
        if (T1.data.equals(T2.data))
            if (isEqual(T1.lChild,T2.lChild))
                if (isEqual(T1.rChild,T2.rChild))
                    return true;
    }
    return false;
}

由先根遍历和中跟遍历序列建立一棵二叉树

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.lChild = new BiTree(preOrder,inOrder,preIndex+1,inIndex,i).root;
        root.rChild = new BiTree(preOrder,inOrder,preIndex+i+1,inIndex+i+1,count-i-1).root;
        }
    }
}

求二叉树的宽度

采用层次遍历思想来求二叉树宽度，层次遍历使用队列存储结点，每次打印当前结点后其左右子树入队，此时队列中既包含当前层的结点，也包含下一层的结点，若将当前层的结点全部出队，剩余的就是下一层的结点个数。

public int getWidth(BiTreeNode T) throws Exception{
        if (T == null)
            return 0;
        int maxWidth = 0;
        LinkQueue L = new LinkQueue();
        L.offer(T);
        while (true){
        //最终队列为空时循环结束
            int len = L.length();
            if (len == 0)
                break;
            while (len > 0){
                BiTreeNode temp = (BiTreeNode) L.peek();
                L.poll();
                len--;
                if (temp.lChild != null)
                    L.offer(temp.lChild);
                if (temp.rChild != null)
                    L.offer(temp.rChild);
            }
            //使用maxWidth表示最大宽度，若下一层结点的个数大于maxWidth，则更新maxWidth
            maxWidth = maxWidth > L.length() ? maxWidth : L.length();
        }
        return maxWidth;
    }

判断一棵二叉树是否为完全二叉树

//判断完全二叉树
//通过完全二叉树的结点数和深度之间的关系来判断是否为完全二叉树
public boolean isWanquanTree(BiTreeNode T) throws Exception {
    int n = countNode1(T);
    int h = getDepth(T);
    if (h == (int) (Math.log(n) + 1))
        return true;
    else
        return false;
}