이원 탐색 트 리 를 정렬 된 양 방향 링크 로 변환 합 니 다. [데이터 구조]

제목: 이원 찾기 트 리 를 입력 하고 이원 찾기 트 리 를 정렬 된 양 방향 링크 로 변환 합 니 다.새로운 노드 를 만 들 수 없고 포인터 의 방향 만 조정 하 라 고 요구 합 니 다.
이원 찾기 트 리                                            10                                           /    \                                         6       14                                       /  \     /　 \                                    　4     8  12 　  16. 양 방향 링크 로 전환
4=6=8=10=12=14=16。
분석: 이 문 제 는 마이크로소프트 면접 문제 입 니 다.나무 와 관련 된 많은 문 제 는 재 귀적 인 사고 로 해결 되 는데 본 문제 도 예 외 는 아니다.다음은 우 리 는 두 가지 서로 다른 귀속 사고방식 으로 분석한다.
사고 1: 우리 가 특정한 노드 에 도착 하여 이 노드 를 뿌리 노드 로 하 는 서브 트 리 를 조정 하려 고 할 때 먼저 왼쪽 서브 트 리 를 조정 하여 왼쪽 서브 트 리 를 정렬 된 왼쪽 체인 표 로 바 꾸 고 오른쪽 서브 트 리 를 오른쪽 체인 표 로 바 꾸 도록 한다.최근 에 왼쪽 링크 의 가장 오른쪽 노드 (왼쪽 트 리 의 최대 노드), 현재 노드 와 오른쪽 링크 의 가장 왼쪽 노드 (오른쪽 트 리 의 최소 노드) 를 연결 합 니 다.나무의 뿌리 결점 부터 모든 결점 을 재 귀적 으로 조정 하 다.
사고방식 2: 우 리 는 나 무 를 차례대로 옮 겨 다 닐 수 있다.이 방식 으로 나 무 를 옮 겨 다 니 며 작은 노드 를 먼저 방문 합 니 다.만약 에 우리 가 하나의 노드 를 방문 할 때마다 이전에 방문 한 노드 가 정렬 양 방향 링크 로 조정 되 었 다 고 가정 하면 우 리 는 현재 노드 를 조정 하 는 지침 을 링크 의 끝 에 연결 합 니 다.모든 노드 가 방문 한 후에 나무 전체 도 정렬 양 방향 링크 로 바 뀌 었 다.
 
참조 사이트 주소:http://zhedahht.blog.163.com/blog/static/254111742007127104759245/
여기에 사고방식 2 의 자바 실현 을 첨부 합 니 다.

//    ，      ，      、        
public class TreeNode {
	private int key;
	private TreeNode leftchlid;
	private TreeNode rightchild;
	private TreeNode parent;
	public int getKey() {
		return key;
	}
	public void setKey(int key) {
		this.key = key;
	}
	public TreeNode getLeftchlid() {
		return leftchlid;
	}
	public void setLeftchlid(TreeNode leftchlid) {
		this.leftchlid = leftchlid;
	}
	public TreeNode getRightchild() {
		return rightchild;
	}
	public void setRightchild(TreeNode rightchild) {
		this.rightchild = rightchild;
	}
	public TreeNode getParent() {
		return parent;
	}
	public void setParent(TreeNode parent) {
		this.parent = parent;
	}
	//    
	public  TreeNode(int key,TreeNode leftchild,TreeNode rightchild,TreeNode parent){
		this.key= key;
		this.leftchlid= leftchild;
		this.rightchild= rightchild;
		this.parent= parent;
		
	}
}

//      
public class BSTree {
	private TreeNode root = null;

	public TreeNode getRoot() {
		return root;
	}

	public void setRoot(TreeNode root) {
		this.root = root;
	}
	//  key          
	public void insert(int key) {
		TreeNode newnode = new TreeNode(key, null, null, null);
		TreeNode parentnode = null;
		TreeNode pnode = root;
		if (root == null) {
			root = newnode;
			return;
		}
		while (pnode != null) {
			parentnode = pnode;
			if (key < pnode.getKey()) {
				pnode = pnode.getLeftchlid();
			} else if (key > pnode.getKey()) {
				pnode = pnode.getRightchild();
			} else {
				//        ，    
				return;
			}

		}
		if (key < parentnode.getKey()) {
			parentnode.setLeftchlid(newnode);
			newnode.setParent(parentnode);
		} else {
			parentnode.setRightchild(newnode);
			newnode.setParent(parentnode);
		}
	}
	/*      key   ，           ，  null，
	 *        key    
	 */
	public TreeNode search(int key) {
		TreeNode pnode = root;

		while (pnode != null && pnode.getKey() != key) {
			if (key < root.getKey()) {
				pnode = pnode.getLeftchlid();
			} else if (key > pnode.getKey()) {
				pnode = pnode.getRightchild();
			}
		}
		return pnode;
			

	}

	/*
	 *    node          key      
	 */
	public TreeNode minElem(TreeNode node) {
		if (root == null || node == null) {
			return null;
		}
		while (node.getLeftchlid() != null) {
			node = node.getLeftchlid();
		}
		return node;

	}

	/*
	 *    node          key      
	 */
	public TreeNode maxElem(TreeNode node) {
		if (root == null || node == null) {
			return null;
		}
		while (node.getRightchild() != null) {
			node = node.getRightchild();
		}
		return node;
	}

	/*
	 *        node       
	 */
	public TreeNode precessor(TreeNode node) {
		if (node == null || root == null) {
			return null;
		}
		//             ，      ，   maxElem（node.getleftchild()）,  
		//      ，                ，   ，      ，
		//     ，             ，               ，           
		TreeNode parentnode = node.getParent();

		if (node.getLeftchlid() != null) {
			return maxElem(node.getLeftchlid());
		}
		if (parentnode.getRightchild() == node) {
			return parentnode;
		}
		while (parentnode != null && parentnode.getLeftchlid() == node) {
			node = parentnode;
			parentnode = parentnode.getParent();
		}
		return parentnode;
	}

	/*
	 *        node       
	 */
	public TreeNode successor(TreeNode node) {
		if (node == null || root == null) {
			return null;
		}
		TreeNode parentnode = node.getParent();
		//         ，   minElem（node.getrightchild()）,  
		//      ，                ，   ，      
		//     ，             ，               
		if (node.getRightchild() != null) {
			return minElem(node.getRightchild());
		}
		if (node == parentnode.getLeftchlid()) {
			return parentnode;
		}
		while (parentnode != null && node == parentnode.getRightchild()) {
			node = parentnode;
			parentnode = parentnode.getParent();
		}
		return parentnode;
	}
	//    
	public void delete(TreeNode node){
		//                
		if(node == null){
			//System.out.println("");
			return;
		}
		TreeNode parentnode = node.getParent();
		//              
		if(node.getLeftchlid() == null&&node.getRightchild() == null){
			if(parentnode.getLeftchlid() == node)//           
			{
				parentnode.setLeftchlid(null);
			}
			else
				parentnode.setRightchild(null);
			return;
		}
		//         ，      
		if(node.getLeftchlid() == null&&node.getRightchild()!=null){
			if(parentnode.getLeftchlid() == node)//           
			{
				parentnode.setLeftchlid(node.getRightchild());
				node.getRightchild().setParent(parentnode);
			}
			else //           
			{
				parentnode.setRightchild(node.getRightchild());
				node.getRightchild().setParent(parentnode);
			}
			return;
		}
		//         ，      
		if(node.getLeftchlid()!=null&&node.getRightchild()==null){
			if(parentnode.getLeftchlid()==node)//           
			{
				parentnode.setLeftchlid(node.getLeftchlid());
				node.getLeftchlid().setParent(parentnode);
			}
			else////           
			{
				parentnode.setRightchild(node.getLeftchlid());
				node.getLeftchlid().setParent(parentnode);
			}
			return;
		}
		//               
		TreeNode successornode = successor(node);
		delete(successornode);
		node.setKey(successornode.getKey());
	}
	
	public void delete(int key) {
		TreeNode findnode = search(key);
		if(findnode == null){
			System.out.println("      ！");
			return;
		}
		else 
		{
			delete(findnode);
		}
	}
	//       
	public void convertToDoubleList(TreeNode currentnode){
		TreeNode headnode = null;//         
		TreeNode indexnode = null;//       
		
		currentnode.setLeftchlid(indexnode);
		if(indexnode == null){
			headnode = currentnode;
		}
		else{
			indexnode.setRightchild(currentnode);
		}
		indexnode = currentnode;
		System.out.println(currentnode.getKey());
	}
	//    
	public void inOrderBSTree(TreeNode root){
		if(root == null){
			return;
		}
		if(root.getLeftchlid()!=null){
			inOrderBSTree(root.getLeftchlid());
		}
		convertToDoubleList(root);
		
		if(root.getRightchild()!=null){
			inOrderBSTree(root.getRightchild());
		}
	}

}

public class Test {
	public static void main(String[] args)  {
		BSTree tree = new BSTree();
		int[] array = {10,6,8,12,14,4,16};
		for(int i =0;i<array.length;i++){
			tree.insert(array[i]);
		}
		tree.inOrderBSTree(tree.getRoot());
		//tree.delete(12);
		//tree.inOrderBSTree(tree.getRoot());

	}

}

테스트 결과:
4 6 8 10 12 14 16