1。 二叉樹接口
java" id="highlighter_836284">
|
1
2
3
4
5
6
7
8
9
|
public interface BinaryTreeInterface<T> { public T getRootData(); public int getHeight(); public int getNumberOfRoot(); public void clear(); public void setTree(T rootData); // 用rootData設(shè)置樹 public void setTree(T rootData,BinaryTreeInterface<T> left,BinaryTreeInterface<T> right); //設(shè)置樹，用左右子節(jié)點(diǎn) } |
2 節(jié)點(diǎn)類
|
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
|
package com.jimmy.impl;public class BinaryNode<T> {private T data;private BinaryNode<T> left; //左子節(jié)點(diǎn)private BinaryNode<T> right; //右子節(jié)點(diǎn)public BinaryNode(){ this(null);}public BinaryNode(T data){ this(data,null,null);}public BinaryNode(T data,BinaryNode<T> left,BinaryNode<T> right){ this.data=data; this.left=left; this.right=right;} public T getData() { return data; } public void setData(T data) { this.data= data; } public BinaryNode<T> getLeft() { return left; } public void setLeft(BinaryNode<T> left) { this.left = left; } public BinaryNode<T> getRight() { return right; } public void setRight(BinaryNode<T> right) { this.right = right; } public boolean hasLeft() {return left!=null; } public boolean hasRight() {return right!=null; } public boolean isLeaf() {return (left==null)&&(right==null); } public int getHeight() { return getHeight(this); } public int getHeight(BinaryNode<T> node) { int h=0; if(node!=null) h=1+Math.max(node.getHeight(node.left),node.getHeight(node.right)); return h; } public int getNumOfNodes(){ int lnum=0,rnum=0; if(left!=null) lnum=left.getNumOfNodes(); if(right!=null) rnum=right.getNumOfNodes(); return lnum+rnum+1; } } |
3.二叉樹實(shí)現(xiàn)
|
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
|
package com.jimmy.impl;import java.util.Stack;import com.jimmy.BinaryTreeInterface;public class Binarytree<T> implements BinaryTreeInterface<T> { private BinaryNode<T> root; //只要一個(gè)數(shù)據(jù)節(jié)點(diǎn)就夠了// 構(gòu)造空樹 public Binarytree(){ root=null; } // 用rootData構(gòu)造樹（有個(gè)根） public Binarytree(T rootdata){ root=new BinaryNode<T>(rootdata) ; } // 用其他樹構(gòu)造樹 public Binarytree(T rootdata,Binarytree<T> leftTree,Binarytree<T> rightTree){ root=new BinaryNode<T>(rootdata) ; if(leftTree!=null){ root.setLeft(leftTree.root); } if(rightTree!=null){ root.setRight(rightTree.root); } }// 用rootData設(shè)置樹（有個(gè)根） @Override public void setTree(T rootData) { root=new BinaryNode<T>(rootData) ; }// 用其他樹設(shè)置樹 public void setTree(T rootData, BinaryTreeInterface<T> left,BinaryTreeInterface<T> right) { root=new BinaryNode<T>(rootData) ; Binarytree leftTree=null; Binarytree rightTree=null; if((leftTree=(Binarytree)left)!=null){ root.setLeft(leftTree.root); } if((rightTree=(Binarytree)right)!=null){ root.setRight(rightTree.root); } } @Override public void clear() { root=null; } @Override public int getHeight() { // TODO Auto-generated method stub return root.getHeight(); } @Override public int getNumberOfRoot() { // TODO Auto-generated method stub return 0; } @Override public T getRootData() { if (root!=null) return root.getData(); else return null; } public BinaryNode<T> getRoot() { return root; } public void setRoot(BinaryNode<T> root) { this.root = root; } public int getNumOfNodes(){ return root.getNumOfNodes(); } public void inOrderTraverse(){ inOrderTraverse(root); } //用棧方法遍歷public void inOrderStackTraverse(){ Stack<BinaryNode> stack=new Stack<BinaryNode>(); BinaryNode cur=root; //stack.push(root); while(!stack.isEmpty()||(cur!=null)){ while(cur!=null) { stack.push(cur); cur=cur.getLeft(); } if(!stack.isEmpty()) { BinaryNode tmp=stack.pop(); if(tmp!=null) {System.out.println(tmp.getData()); cur=tmp.getRight(); } } }}// 遞歸遍歷public void inOrderTraverse(BinaryNode<T> node){ if(node!=null) {inOrderTraverse(node.getLeft()); System.out.println(node.getData()); inOrderTraverse(node.getRight()); } }public static void main(String[] args) {Binarytree<String> t=new Binarytree<String>();Binarytree<String> t8=new Binarytree<String>("8");Binarytree<String> t7=new Binarytree<String>("7");t.setTree("6",t7,t8); //用t7,t8設(shè)置樹tt.inOrderStackTraverse();System.out.println(t.getHeight());}} |
通過此文，希望能幫助到大家，謝謝大家對本站的支持！
