두 갈래 나무 (둘)

6. 두 갈래 트리의 노드 값과 정수를 지정하는 모든 경로

나무의 뿌리 노드에서 시작해서 잎 노드가 지나가는 노드가 형성하는 경로까지 내려간다.예를 들어 정수 22 및 를 입력합니다.다음 두 갈래 트리: 10/\5 12/\4 7은 10, 12 및 10, 5, 7 경로로 인쇄됩니다.

	// sum  
	// num  
	public void printPath(BTreeNode root, int sum, Stack<Integer> stack, int num) {
		if (root != null) {
			sum = sum + root.data;
			stack.push(root.data);
			printPath(root.left, sum, stack, num);
			printPath(root.right, sum, stack, num);
			if(sum == num &&root.left==null&&root.right==null) {
				for (int i : stack) {
					System.out.print(i + " ");
				}
				System.out.println();
			}
			stack.pop();
		}
	}
	public static void main(String[] args) {
		BinaryTreePath btp = new BinaryTreePath();
		BTreeNode root = btp.createTree(root);
		Stack<Integer> stack = new Stack<Integer>();
		int num = 22;
		int sum = 0;
		btp.printPath(root, sum, stack, num);
	}
}

7. 층별로 두 갈래 나무의 각 결점을 인쇄하고, 같은 층의 결점은 왼쪽에서 오른쪽으로 인쇄하며, 서로 다른 층끼리 줄을 바꾼다

public void printByLevel(Node root) {
		if (root != null) {
			Queue<Node> queue = new LinkedList<Node>();
			Node flag = new Node();//  
			Node tempNode = null;
			queue.offer(root);
			queue.offer(flag);
			while (queue.size() > 1) {// flag ， 
				tempNode = queue.poll();
				if (tempNode != flag) {
					System.out.print(tempNode.getData()+" ");
					if (tempNode.getLeft() != null) {
						queue.offer(tempNode.getLeft());
					}
					if (tempNode.getRight() != null) {
						queue.offer(tempNode.getRight());
					}
				} else {
					System.out.println();
					queue.offer(flag);
				}
			}
		}
	}

 ：
	public int printNodeAtLevel(Node root, int level) {
		if (root == null || level < 0) {
			return 0;
		}
		if (0 == level) {
			System.out.print(root.getData()+" ");
			return 1;
		}
		return printNodeAtLevel(root.getLeft(), level - 1)
				+ printNodeAtLevel(root.getRight(), level - 1);
	}
	
	public void printBylevel_(Node root) {
		for (int level = 0;; level++) {
			if (printNodeAtLevel(root, level) == 0)
				break;
			System.out.println();
		}
	}

8. 두 갈래 찾기 트리가 정렬된 양방향 체인 테이블

10/\6 14/\/\4 8 12 16에서 양방향 체인 테이블로 변환
4=6=8=10=12=14=16

        static ListNode head;
	static ListNode rear;
	public static void Tree2List(BSTreeNode tree) {
		if (null != tree.getLeft()) {
			Tree2List(tree.getLeft());
		}
		ListNode node = new ListNode();
		node.setValue(tree.getValue());
		if (null != head) {
			rear.setRight(node);
			node.setLeft(rear);
			rear = node;
		} else {
			head = node;
			rear = node;
		}
		if (null != tree.getRight()) {
			Tree2List(tree.getRight());
		}
	}

9. 두 갈래 나무의 좌우 나무를 교환

public void change（Tree node）｛
      if（node  ||   &&  ）
            return
      swap(node.left, node.right)
      if（ ）
            change（node.left）；
      if（ ）
            change（node.right）；
｝

10. 앞의 순서와 중간의 순서에 따라 두 갈래 나무를 구성한다

public Node buildTree(int[] preOrder, int begin1, int end1, int[] inOrder, int begin2, int end2) {
		if (begin1 > end1 || begin2 > end2) {
			return null;
		}
		int rootData = preOrder[begin1];//  
		Node root = new Node(rootData);
		int div = getIndex(inOrder, rootData, begin2, end2);//  
		int offSet = div - begin2;//  , offSet 
		Node left = buildTree(preOrder, begin1 + 1, begin1 + offSet, inOrder, begin2, begin2 + offSet - 1);
		Node right = buildTree(preOrder, begin1 + offSet + 1, end1, inOrder, div + 1, end2);
		root.setLeft(left);
		root.setRight(right);
		return root;
	}

	public int getIndex(int[] arr, int value, int begin, int end) {
		for (int i = begin; i <= end; i++) {
			if (arr[i] == value)
				return i;
		}
		return -1;
	}

 ：	int[] preOrder = { 7, 10, 4, 3, 1, 2, 8, 11 }; //  
		int[] inOrder = { 4, 10, 3, 1, 7, 11, 8, 2 }; //  
		rootNode = test.buildTree(preOrder, 0, preOrder.length - 1, inOrder, 0, preOrder.length - 1);

11. 정수 서열이 두 갈래로 트리의 뒷부분을 훑어보는 결과인지 판단

마지막 결점은 반드시 뿌리 결점이다. 그리고 두 갈래 정렬 나무의 성질에 따라 그것의 좌우 아이를 찾은 후에 다시 찾아낸다.

public boolean check(int[] a, int begin, int end) {
		if (a == null || begin == end)//  
			return true;
		if (begin < 0 || end >= a.length) {
			return false;
		}
		int root = a[end];
		int left = begin;
		//  
		for (; left < end; left++) {
			if (a[left] > root)
				break;
		}
		//  
		int right = left;// left root 
		for (; right < end; right++) {
			if (a[right] < root)
				return false;
		}
		boolean leftFlag = true, rightFlag = true;
		if (left - begin > 1) {// left - begin ， 2 
			//  		
			leftFlag = check(a, begin, left - 1);
		}
		if (end - left > 1) {// end - left ， 2 
			//  
			rightFlag = check(a, left, end - 1);
		}
		return leftFlag && rightFlag;
	}