二叉树与单链表的算法

• 二叉树

//节点结构
public class Treenode{
    private int index;
    private T data;
    private Treenode left;
    private Treenode right;
    public Treenode(int index, T data){
        this.index = index;
        this.data = data;
        this.left = null;
        this.right = null;
    }
}


//构建树
public class BinaryTree{
    public Treenode root = null;
    public BinaryTree(){
        root = new Treenode<>(1,'A');
    }
    public void createTree(){
        Treenode B =  new Treenode(1,'B');
        root.left = B;
    }

//获取二叉树的高度和大小:一个节点有一个左孩子或者右孩子，高度就 + 1，所以二叉树的高度就是取左孩子与右孩子的最大值，然后加根节点的 1 。获取大小就是获取二叉树所有左孩子与右孩子的节点之和了，最后也要加根节点的 1。
    public int getheight(){
        return getheight(root)
    }
    public int getheight(Treenode node){
        if (node==null) {
            return 0;
        }
        int left = getheight(node.left);
        int height = getheight(node.right);
        return left>height?(left+1):(height+1);
    }
    public int getsize(){
        return getsize(root)
    }
    public int getsize(Treenode node){
        if (node==null) {
            return 0;
        }
        int left = getsize(node.left);
        int right = getsize(node.right);
        return left+height+1;
    }
    //二叉树的遍历本质上还是递归，只是跟的位置不同而已。
    //先序遍历
    public void preOrder(Treenode node){
        if (node==null) {
            return ;
        }
        System.out.println(node.data+"" );
        preOrder(node.left);
        preOrder(node.right);
    }
    // 用栈 迭代 实现前序遍历
    public static void preOrder2(Treenode root){
        if (root==null) {
            return ;
        }
        
        Stack<Treenode> stack = new Stack<Treenode>();
        stack.push(root);

        while(!stack.isEmpty()){//push the right one firstly and it will pop out later
            Treenode node = stack.pop();
            System.out.print(node.data+"");
            if (node.right!=null) {
                stack.push(node.right);
            }
            if (node.left!=null) {
                stack.push(node.left)               
            }
        }

    }
    //中序遍历
    public void midOrder(Treenode node){
        if (node==null) {
            return ;
        }
        midOrder(node.left);
        System.out.println(node.data+"");
        midOrder(node.right);
    }
    // 用栈 迭代 实现中序遍历 .
    public static void midOrder2(Treenode node){
        if (node == null) {
            return;
        }
        Stack<Treenode> stack = new Stack<Treenode>();
        Treenode cur = node;


        while(!stack.isEmpty()||cur!=null){
            if (cur!=null) {
                stack.push(cur);
                cur = cur.left//左边遍历
            }else{
                cur = stack.pop();//弹出的是相对而言的根节点，打印出来 再依次遍历右节点， 
                System.out.print(pop.data);
                cur = cur.right;
            }   
        }
    }


    //后序遍历
    public void afterOrder(Treenode node){
        if (node==null) {
            return;
        }
        afterOrder(node.left);
        afterOrder(node.right);
        System.out.println(node.data+"");
    }
    // 用栈 迭代 实现后序遍历 .
    public void afterOrder2(Treenode root){
        if (root == null) {
            return;
        }
        Stack<Treenode> stack1 = new Stack<Treenode>();
        Stack<Treenode> stack2 = new Stack<Treenode>();

        stack1.push(root);
        while(!stack1.isEmpty()){
            Treenode node = stack1.pop();
            stack2.push(node);
            if (node.left !=null) {
                stack1.push(node.left);
            }
            if (node.right != null) {
                stack1.push(node.right);
            }
        }
        while(!stack2.isEmpty()){
            System.out.print(stack2.pop().dara+"");
        }
    }



    //分层遍历二叉树 宽度优先遍历
    public static void levelTravals(Treenode root){
        if (root == null) {
            return;
        }
        Linklist<Treenode> queue = new Linklist<Treenode>();
        queue.push(root);
        while(!queue.isEmpty){
            Treenode cur = queue.removeFirst();
            System.out.println(cur.data+"")
            if (cur.left != null) {
                queue.add(cur.left);
            }
            if (cur.right!= null) {
                queue.add(cur.right);
            }
        }
    }

    //按层打印二叉树.更新下一行的最右节点进行遍历
    public static void printFromToptoBottom(Treenode root){
        if (root == null) {
            return;
        }
        Queue<Treenode> queue = new Queue<Treenode>(100);
        queue.add(root);
        Treenode curright = root;
        Treenode nextright = root;
        int level = 1;

        while(!queue.isEmpty()){
            Treenode node = queue.poll();
            System.out.print(node.data +"");
            if (node.left!=null) {
                queue.add(node.left);
                nextright = node.left;
            }
            if (node.right!=null) {
                queue.add(node.right);
                nextright = node.right;
            }
            if (node == curright) {
                System.out.println(level +"");
                level++;
                curright = nextright;
            }
        }
    }
}

• 单链表

Class Node{
    int data;
    Node next;
    public Node(int data){
        this.data =data;
    };
}
//删除单链表指定节点
public void deletnodes(Node head,Node node){
    //end 顺序查找法找到尾节点前一个
    if (node.next == null) {
        while(head.next!=node){
            head = head.next;
        }
        head = null;
    }
    else if (node == head) {
        head = null;
    }
    else {
        Node q = node.next;
        node.data = q.data;
        node.next = q.next;
    }
}
//删除单链表指定数值的节点
//stack 
public Node deletValue1(Node head,int num){
    Stack<Node> stack = new Stack<Node>();
    while(head != null){//指空推出
        if (head.next!=num) {
            stack.push(head.next);
        }
        head=head.next;
    }
    while(!stack.isEmpty()){
        stack.peek().next = head;//第一次指向空
        head =stack.pop();
    }
}
//no stack find the first not to be deleted node as our new list's head
public Node deletValue2(Node head,int num){
    while(head!=null){
        if (head.data != num) {
            break;
        }
        head = head.next;
    }

    Node pre = head;
    Node cur = head;
    while(cur.data!=null){
        if (cur.data==num) {
            pre.next =cur.next;
        }else{
            pre = cru;
        }
        cur = cur.next;
    }
}
//删除单链表中数值重复的节点用 hashset实现 contain
public void deletrepeatednodes(Node head){
    if (head ==null) {
        return;
    }
    Hashset<Integer> set = new Hashset<Integer>();
    Node pre = head;
    Node cur = head;
    set.add(head.data);
    while(cur!=null){
        if (set.contain(cur.data)) {
            pre.next = cur.next;
        }else{
            set.add(cur.data);
            pre = cur;
        }
        cur = cur.next;
    }
}
// 两个单链表生成相加的列表：每一节点的值都在0~9之间，个位数生成新链表
public Node addlist(Node head1,Node head2){
    
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

    while (head1!=null){
        stack1.push(head1.data);
        head1 = head1.next;
    }
    while (head2!=null){
        stack2.push(head2.data);
        head2 = head2.next;
    }
    int n1 =0;
    int n2 =0;
    int n =0;//node1+node2
    

    Node node = null;
    Node cur = null;

    while (!stack1.isEmpty()||!stack2.isEmpty()) {
        n1 = stack1.isEmpty()?0:stack1.pop();
        n2 = stack2.isEmpty()?0:stack2.pop();

        n = n1+n2+ca;
        cur = new Node(n%10);
        cur.next = node;
        node = cur;
    }

    return cur;
}
//判断单链表是否为回文结构123321 栈
public boolean isPalindrome(Node head){
    if (head == null) {
        return false;
    }
    Stack<Integer> stack = new Stack<Integer>();
    Node cur  = head;
    while(cur!=null){
        stack.push(cur.data);
        cur = cur.next;
    }
    while(head!=null){
        if (head.data != stack.pop()) {
            return false;
        }
        head = head.next;
    }
    return true;

}
//删除单链表的倒数第k个节点
public static Node deleteLastKthNode(Node head,int k){
    if (k<=0||head==null) {
        return head;
    }

    Node cur = head;
    Node kthbefore = head;

    for (int i = 0;i<k+1 ; k++) {
        if (cur==null) {
            return head;
        }
        cur = cur.next;
    }


    while(cur != null){
        cur = cur.next;
        kthbefore = kthbefore.next;
    }

    kthbefore.next = kthbefore.next.next;
    return head;
}
//用两个栈实现一个队列；先进后出+先进后出=先进先出。压入栈+弹栈
public class QueenwithStacks{
    private static Stack<Object> stack1 = new Stack<Object>();
    private static Stack<Object> stack2 = new Stack<Object>();


    public static void pushintostarck1(Object item){
        stack1.push(item);
    }
    public static void pushintostarck2(){
        while (!stack2.isEmpty()) {
            stack2.pop();
        }
        if (stack1.isEmpty()) {
            throw new RuntimeException();
        }
        while(!stack1.isEmpty){
            Object item = stack1.pop();
            stack2.push(item);
        }
    }
}