0%

打印二叉树边界节点

发表于 分类于
本文字数： 阅读时长 ≈

打印二叉树边界节点

打印二叉树的边界节点

对于边界点有如下定义(标准一)：

  • 1,头节点是边界节点
  • 2，叶节点也是边界节点
  • 3，如果节点在其所在的层中是最左或最右的，那也是边界节点

定义二(或标准二)：

  • 1，头节点是边界节点
  • 2，叶节点是边界节点
  • 3，树左边界延伸下去的路径是边界节点
  • 4，树右边界延伸下去的路径是边界节点
    按照标准一打印：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    class Node1 {
    	public int value;
    	public Node1  left;
    	public Node1  right;
    	
    	public Node1 (int data) {
    		value = data;
    	}
    }

    class PrintBinaryTreeEdge1 {
    	
    	
    	public static void printEdge1 (Node1 head) {
    		if (head == null) {
    			return;
    		}
    		int height = getHeight(head, 0);
    		Node1[][] edgeMap = new Node1[height][2];
    		setEdgeMap(head, 0, edgeMap);
    		//打印左边界
    		for (int i = 0; i != edgeMap.length; i++) {
    			System.out.print(edgeMap[i][0].value + " ");
    		}
    		//打印既不是左边界，也不是有边界的叶节点
    		printLeafNotInMap(head, 0, edgeMap);
    		//打印右边界，但不是左边界的节点
    		for (int i = edgeMap.length - 1; i != -1; i--) {
    			if (edgeMap[i][0] != edgeMap[i][1]) {
    				System.out.print(edgeMap[i][1].value + " ");
    			}
    		}
    		System.out.println();
    	}
    	public static int getHeight (Node1 h, int l ) {
    		if (h == null) {
    			return l;
    		}
    		return Math.max(getHeight(h.left, l + 1), getHeight(h.right, l + 1));
    	}
    	public static void setEdgeMap(Node1 h, int ll, Node1[][] edgeMap) {
    		if (h == null) {
    			return;
    		}
    		edgeMap[ll][0] = edgeMap[ll][0] == null ? h : edgeMap[ll][0];
    		edgeMap[ll][1] = h;
    		setEdgeMap(h.left, ll + 1, edgeMap);
    		setEdgeMap(h.right, ll + 1, edgeMap);
    	}
        
    	public static void printLeafNotInMap (Node1 h, int l, Node1[][] m) {
    		if (h == null) {
    			return;
    		}
    		if (h.left == null && h.right == null && h != m[l][0] && h != m[l][1]) {
    			System.out.print(h.value + " ");
    		}
    		printLeafNotInMap(h.left, l + 1, m);
    		printLeafNotInMap(h.right, l + 1, m);
    	}
    	
        //主方法
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		Node1 head = new Node1(1);
    		head.left = new Node1(2);
    		head.right = new Node1(3);
    		head.left.left = new Node1(4);
    		head.left.right= new Node1(5);
    		head.right.left= new Node1(6);
    		head.right.right= new Node1(7);
    		printEdge1(head);
    		
    	}

    }

按照标准二打印：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public static void printEdge2 (Node head) {
	if (head == null) {
		return;
	}
	System.out.print(head.value + " ");
	if (head.left != null && head.right != null) {
		printLeftEgde(head.left, true);
		printRightEdge(head.right, true);
	} else {
		printEdge2(head.left != null ? head.left : head.right);
	}
	System.out.println();
}
//打印左边界
public static void printLeftEgde (Node h, boolean print) {
	if (h == null) {
		return;
	}
	if (print || (h.left == null && h.right == null)) {
		System.out.print(h.value + " ");
	}
	printLeftEgde(h.left, print);
	printLeftEgde(h.right, print && h.left == null ? true : false);
}
//打印右边界
public static void printRightEdge (Node h, boolean print) {
	if (h == null) {
		return;
	}
	printRightEdge(h.left, print && h.right == null ? true : false);
	printLeftEgde(h.right, print);
	if (print || (h.left == null && h.right == null)) {
		System.out.print(h.value + " ");
	}
}