二叉树 n叉树遍历算法

灰太狼 2022-12-09 05:19 177阅读 0赞

## 二叉树 ##

// 二叉树的遍历
    class TreeNode { 
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode(int x) {  val = x; }
      }
    
    public class pre { 
        List<Integer> treeList=new ArrayList();
        public static void main(String[] args) { 
    
        }
        //前序遍历 递归
        public void preTraversal(TreeNode root) { 
            if(root==null) return;
            treeList.add(root.val);
            if(root.left!=null){ 
                preTraversal(root.left);
            }
            if(root.right!=null){ 
                preTraversal(root.right);
            }
        }
        //前序遍历 非递归
        public void preTraversal2(TreeNode root) { 
            Stack<TreeNode> st=new Stack<>();
            TreeNode p=root;
            while (p!=null || st!=null){ 
               if(p!=null){ 
                treeList.add(p.val);
                st.push(p);
                p=p.left;
            }
            if(p==null){ 
            p=st.pop().right;
            }
            
        }
    
        //中序遍历 递归
        public void inorderTraversal(TreeNode root) { 
            if(root==null) return;
            if(root.left!=null){ 
                preTraversal(root.left);
            }
            treeList.add(root.val);
            if(root.right!=null){ 
                preTraversal(root.right);
            }
    
        }
        //中序遍历 非递归
        public void inorderTraversal2(TreeNode root) { 
            Stack<TreeNode> st=new Stack<>();
            TreeNode p=root;
            while (p!=null){ 
            if(p!=null){ 
                st.push(p);
                p=p.left;
            }
            if(p==null){ 
             p=st.pop();
            treeList.add(p.val);
            p=p.right;	
    	}
                
            }
           
        }
        //后序遍历 递归
        public void postTraversal(TreeNode root) { 
            if(root==null) return;
            if(root.left!=null){ 
                preTraversal(root.left);
            }
            if(root.right!=null){ 
                preTraversal(root.right);
            }
            treeList.add(root.val);
    
        }
        //后序遍历 非递归
        public void postTraversal2(TreeNode root) { 
                if (root == null)
                    return;
                Stack<TreeNode> s1 = new Stack<>();
                Stack<TreeNode> s2 = new Stack<>();
                s1.push(root);
                while (!s1.isEmpty()) { 
                    root = s1.pop();
                    s2.push(root);
                    if (root.left != null) { 
                        s1.push(root.left);
                    }
                    if (root.right != null) { 
                        s1.push(root.right);
                    }
                }
                while (!s2.isEmpty()) { 
                    treeList.add(s2.pop().val);
                }
            }
        
        //层次遍历
        public void levelTraversal(TreeNode root) { 
            Queue<TreeNode> que=new LinkedList<>();
            if(root==null)return;
            que.offer(root);
            while(!que.isEmpty()){ 
                int count=que.size();
                while (count-->0){ 
                    TreeNode p=que.poll();
                    treeList.add(p.val);
                    if(p.left!=null){ 
                        que.offer(p.left);
                    }
                    if(p.right!=null){ 
                        que.add(p.right);
                    }
                }
            }
        }
    }

## n叉树 ##

import java.util.LinkedList;
    import java.util.List;
    import java.util.Queue;
    import java.util.Stack;
    
    //n叉树 遍历
    class Node { 
        public int val;
        public List<Node> children;
    
        public Node() { 
        }
    
        public Node(int _val) { 
            val = _val;
        }
    
        public Node(int _val, List<Node> _children) { 
            val = _val;
            children = _children;
        }
    }
    public class Treen { 
        List<Integer> treelist=new LinkedList<Integer>();
        public static void main(String[] args) { 
    
        }
        // n叉树 前序遍历 递归
        public void preorder(Node root) { 
            if(root==null)return;
            treelist.add(root.val);
            for(int i=0;i<root.children.size();i++){ 
                preorder(root.children.get(i));
            }
        }
        // n叉树 前序遍历 非递归
        public void preorder2(Node root) { 
            if(root==null)return;
            Stack<Node> st=new Stack<>();
            st.push(root);
            while (!st.isEmpty()){ 
                Node p=st.pop();
                treelist.add(p.val);
                for (int i=p.children.size()-1;i>=0;i--){ 
                    st.push(p.children.get(i));
                }
    
            }
    
        }
    
        // n叉树 后序遍历 递归
        public void postorder(Node root) { 
            if(root==null)return;
    
            for(int i=0;i<root.children.size();i++){ 
                preorder(root.children.get(i));
            }
            treelist.add(root.val);
        }
    
        // n叉树 后序遍历 非递归
        public void postorder2(Node root) { 
            Stack<Node> st1=new Stack<>();
            Stack<Node> st2=new Stack<>();
            if(root==null)return;
            st1.push(root);
            while (!st1.isEmpty()){ 
                Node p=st1.pop();
                st2.push(p);
                for (int i=0;i<p.children.size();i++){ 
                    if(p.children.get(i)!=null){ 
                        st1.push(p.children.get(i));
                    }
                }
            }
            while (!st2.isEmpty()){ 
                treelist.add(st2.pop().val);
            }
        }
        // n叉树 层次遍历
        public void levelorder(Node root) { 
            Queue<Node> que=new LinkedList<>();
            if(root==null)return;
            que.offer(root);
            while(!que.isEmpty()){ 
                int count=que.size();
                while (count-->0){ 
                    Node p=que.poll();
                    treelist.add(p.val);
                    for (int i=0;i<p.children.size();i++){ 
                        if(p.children.get(i)!=null){ 
                            que.offer(p.children.get(i));
                        }
                    }
                }
            }
        }
    }