트 리 데이터 구조의 옮 겨 다 니 기 (이 진 트 리 의 앞 뒤 순서 옮 겨 다 니 기 (재 귀, 교체), N 진 트 리 의 선후 순서 옮 겨 다 니 기 (재 귀 와 교체)

트 리 데이터 구 조 는 데이터 구조 에서 비교적 중요 한 장절 이다.그 중에서 나무 구조 에 대한 역 사 는 이 장의 핵심 이자 뒤의 관련 내용 의 기초 이다.자신 은 관련 블 로 거들 의 자 료 를 결합 시 키 고 자신 이 leecote 에서 문 제 를 푸 는 마음 과 결합 하여 나무 모양 데이터 구조 에 대한 정 리 를 얻 으 려 고 한다.모두 에 게 도움 을 줄 수 있 기 를 바 랍 니 다.
(1): 이 진 트 리 의 옮 겨 다 니 기

		1.1：           

public class BiTreeNode {
	private Object data;//   
	private BiTreeNode lchild;//   
	private BiTreeNode rchild;//   
	
	public BiTreeNode() {
		this.data=0;
		this.lchild=null;
		this.rchild=null;
	}
	
	public BiTreeNode(Object data) {
		this.data=data;
		this.lchild=null;
		this.rchild=null;
	}
	
	public BiTreeNode(Object data,BiTreeNode lchild,BiTreeNode rchild) {
		this.data=data;
		this.lchild=lchild;
		this.rchild=rchild;
	}

	1.2：        
		
		        

public void preRootSearch(BiTreeNode root) {
		if(root!=null) {
			System.out.print(root.getData());
			preRootSearch(root.getLchild());
			preRootSearch(root.getRchild());
		}
	}

public void inRootSearch(BiTreeNode root) {
		if(root!=null) {
			inRootSearch(root.getLchild());
			System.out.print(root.getData());
			inRootSearch(root.getRchild());
		}
	}
	

public void postRootSearch(BiTreeNode root) {
		if(root!=null) {
			postRootSearch(root.getLchild());
			postRootSearch(root.getRchild());
			System.out.print(root.getData());
		}
		
	}

	1.3：         


			        

public void preBitreeSearch_1(BiTreeNode root) {
		BiTreeNode t=root;
		stack st=new stack();
		if(root!=null) {
			st.push(t);
		}
		while(!st.isEmpty()) {
			t=(BiTreeNode) st.pop();
			while(t!=null) {
				System.out.print(t.getData());
				if(t.getRchild()!=null) {
					st.push(t.getRchild());
				}
					t=t.getLchild();
			}
		}
	}

public void inBitreeSearch_1(BiTreeNode root) {
		BiTreeNode t=root;
		stack st=new stack();
		if(t!=null) {
			st.push(t);
		}
		while(!st.isEmpty()) {
			while(st.peek()!=null) {
				st.push(((BiTreeNode) st.peek()).getLchild());
			}
			st.pop();
			if(!st.isEmpty()) {
				t=(BiTreeNode) st.pop();
				System.out.print(t.getData());
				st.push(t.getRchild());
				
			}
	}	
}

public void postBiTreeSearch_1(BiTreeNode root) {
		if(root==null) {
			return;
		}else {
			stack st=new stack();
			BiTreeNode t=root;
			st.push(root);
			BiTreeNode p=null;
			boolean flag=true;
			while(!st.isEmpty()) {
				while(st.peek()!=null) {
					st.push(((BiTreeNode)st.peek()).getLchild());
				}
				st.pop();
				t=(BiTreeNode)st.peek();
				if(!st.isEmpty()) {
					if(t.getRchild()==null||t.getRchild()==p) {
						t=(BiTreeNode)st.pop();
						System.out.print(t.getData());
						p=t;
						flag=true;
					}else {
						st.push(t.getRchild());
						flag=false;
					}
					if(!flag) {
						break;
					}
				}
				
			}
		}
	}

           ，      。                  N        。   
        。


	2.1：N     

public class BiTreeNode {
	private Object data;
	private LinkedList<BiTreeNode> children;
	}

                ，     2    ，        ，            
  。
	2.2：N       
		
		    

class Solution {
    List<Integer> array=new LinkedList<Integer>();
    public List<Integer> preorder(Node root) {
        if(root!=null){
            array.add(root.val);
            for(Node i:root.children){
                preorder(i);
            }
        }
        return array;
    }
}

class Solution {
    List<Integer> array=new LinkedList<Integer>();
    public List<Integer> postorder(Node root) {
        if(root!=null){
            for(Node i:root.children){
                preorder(i);
            }
            array.add(root.val);
        }
        return array;
    }
}

	2.3:N       

	         

class Solution {
    public List<Integer> preorder(Node root) {
        //    
        List<Integer> res = new ArrayList<Integer>();
        Stack<Node> stack = new Stack<Node>();
        if(root == null)
            return res;
        stack.push(root);
        while(!stack.isEmpty())
        {
            Node node = stack.pop();
            res.add (node.val);
            for(int i =  node.children.size()-1;i>= 0;i--)
            {
                stack.add(node.children.get(i));
            }  
        }
        return res;
    }
}

//    ：          
class Solution {
    public List<Integer> postorder(Node root) {
        List<Integer> res_pre = new ArrayList<>();
        if(root == null)
            return res_pre;
        Stack<Node> s = new Stack<>();
        s.push(root);
        while(!s.isEmpty()){
            Node n = s.pop();
            res_pre.add(n.val);
            for(Node node : n.children)
                s.push(node);
        }
        Collections.reverse(res_pre);
        return res_pre;
    }
}