[从今天开始修炼数据结构]树，二叉树，线索二叉树，霍夫曼树

public class ParentChildDemo <T>{
    
    PCTBox[] nodes; //表头数组
    int r;  //根节点的角标
    int n;  //总结点树
    int parent;  //双亲结点的角标，根节点为-1
    
    
    private class PCTBox<T>{
        T data;
        ChildNode firstchild;
    }
    private class ChildNode{
        int child; //存储本结点在表头数组中的下标
        ChildNode next;
    }
}

public class BiTNode<T> {
    T data;
    BiTNode lchild;
    BiTNode rchild;
}

    public static class Node<T>{
        private T data;
        private Node lChild;
        private Node rChild;

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

        public void setNode(T data){
            this.data = data;
        }
    }

    /**
     * 前序遍历的递归写法
     */
    public void PreOrderTraverse1(Node root){
        if (root == null)
            return;
        System.out.println(root.data);
        PreOrderTraverse1(root.lChild);
        PreOrderTraverse1(root.rChild);
    }

    /**
     * 前序遍历的非递归写法
     * 递归转成栈
     */
    public void PreOrderTraverse2(Node root){
        ArrayStack<Node> a = new ArrayStack<>();
        while (root != null || !a.isEmpty()){
            while (root != null){
                System.out.println(root.data);
                a.push(root);
                root = root.lChild;
            }

            if (!a.isEmpty()){
                root = a.pop();
                root = root.rChild;
            }
        }
    }

    /**
     * 中序遍历的递归写法
     */
    public void InOrderTraverse1(Node root){
        Node node = root;
        if (node == null){
            return;
        }
        InOrderTraverse1(node.lChild);
        System.out.println(node.data);
        InOrderTraverse1(node.rChild);
    }

    /**
     * 中序遍历的非递归写法
     */
    public void InOrderTraverse2(Node root){
        ArrayStack<Node> a = new ArrayStack<>();
        while (root != null || !a.isEmpty()){
            while (root.lChild != null){
                a.push(root);
                root = root.lChild;
            }
            if (!a.isEmpty()){
                root = a.pop();
                System.out.println(root.data);
                root = root.rChild;

            }
        }
    }

  /**
     * 后序遍历的递归写法
     */
    public void PostOrderTraverse1(Node root){
        if (root == null){
            return;
        }
        PostOrderTraverse1(root.lChild);
        PostOrderTraverse1(root.rChild);
        System.out.println(root.data);
    }

    /**
     * 后序遍历的非递归写法 —— 双栈法
     * 将前序遍历的中左右，调换变成左右中
     *
     */
    public void PostOrderTraverse2(Node root){
        ArrayStack<Node> a1 = new ArrayStack<>();
        ArrayStack<Node> a2 = new ArrayStack<>();
        Node r = root;
        while (r != null || !a1.isEmpty()){
            while (r != null){
                a1.push(r);
                a2.push(r);
                r = r.rChild;
            }
            if (!a1.isEmpty()){
                r = a1.pop();
                r = r.lChild;
            }
        }
        while (!a2.isEmpty()){
            r = a2.pop();
            System.out.println(r.data);
        }
    }

    /**
     * 利用队列实现层序遍历(可以不用优先队列，这个优先队列Demo是我前面随笔写的，顺便拿来用用)
     */
    public void LevelOrderTraverse(Node root) throws Exception {
        PriorityQueueDemo<Node> p = new PriorityQueueDemo<>(10);
        Node t;
        p.add(root);
        while (p.size() != 0){
            t = p.poll();
            System.out.println(t.data);
            if (t.lChild != null)  p.add(t.lChild);
            if (t.rChild != null)  p.add(t.rChild);
        }

    }

    private Object[] results;
    public BiTree(Object[] arr){
        this.results = arr;
    }
    private static int index = 0;
    public Node<T> buildBiTree(){
        if (index >= results.length || results[index].equals('#')){
            index++;
            return null;
        }
        Node<T> node = new Node<T>((T)results[index++]);
        node.lChild = buildBiTree();
        node.rChild = buildBiTree();
        return node;
    }

    private Node pre;//根节点的pre是head,head的rtag = 1public void Threading(Node root) {
        Node r = root;
        if (root == null){
            return;
        }else {
            Threading(r.lChild);
            if (r.lChild == null){
                r.ltag = 1;
                r.lChild = pre;
            }
            if ( pre != null&&pre.rChild == null){
                pre.rtag = 1;
                pre.rChild = r;
            }
            pre = r;
            Threading(r.rChild);
        }
    }

    /**
     * 按照二叉线索树的线索遍历
     */
    public void InOrderTraverse_Threaded(Node root){
        Node r = root;
        while (r != null) {
            while (r.lChild != null && r.ltag == 0) {
                r = r.lChild;
            }
            System.out.println(r.data);
            while (r.rtag == 1) {
                r = r.rChild;
                System.out.println(r.data);
            }
            r = r.rChild;
        }
    }

//结点结构

import java.util.Comparator;

public class TNode<T> implements Comparable{
    private T data;
    private int weight;
    private TNode lChild;
    private TNode rChild;

    private Comparator comparator;

    public TNode(T data, int weight){
        this.data = data;
        this.weight = weight;
        this.lChild = null;
        this.rChild = null;
    }

    public TNode(T data, int weight, TNode lChild, TNode rChild){
        this(data, weight);
        this.lChild = lChild;
        this.rChild = rChild;
    }

    public Comparator getComparator(){
        return this.comparator;
    }
    public void setlChild(TNode node){
        this.lChild = node;
    }

    public void setrChild(TNode node){
        this.rChild = node;
    }

    public int getWeight(){
        return this.weight;
    }

    public T getData(){
        return data;
    }

    public TNode getlChild(){
        return lChild;
    }

    public TNode getrChild(){
        return rChild;
    }

    @Override
    public int compareTo(Object o) {
        return ((TNode)o).weight - this.weight;
    }

}

class TNodeComparator implements Comparator{

        @Override
        public int compare(Object o1, Object o2) {
            return ((TNode)o1).getWeight() - ((TNode)o2).getWeight();
        }

}

//创建霍夫曼树

import java.util.LinkedList;

public class HuffmanTree<T> {
    LinkedList<TNode<T>> tnodes = new LinkedList<>();

    public HuffmanTree(LinkedList<TNode<T>> tnodes){
        this.tnodes = tnodes;
    }

    public TNode<T> buildHuffmanTree(){
        tnodes.sort(new TNodeComparator());
        while (tnodes.size() > 1) {
            TNode<T> newTNode = buildBiTree(tnodes.remove(0), tnodes.remove(0));
            tnodes.add(0, newTNode);
            tnodes.sort(new TNodeComparator());
        }
        return tnodes.remove(0);
    }

    public void PreOrderTraverse(TNode tNode){
        if (tNode == null){
            return;
        }else {
            T tdata = (T) tNode.getData();
            if (tdata != null){
                System.out.println(tdata);
            }
            PreOrderTraverse(tNode.getlChild());
            PreOrderTraverse(tNode.getrChild());
        }
    }

    private TNode buildBiTree(TNode<T> tNode, TNode<T> tNode1) {
        TNode<T> t1 = new TNode<T>(null, tNode.getWeight() + tNode1.getWeight(), tNode, tNode1);
        return t1;
    }
}