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设置树
public void setTree(T rootData,BinaryTreeInterface<T> left,BinaryTreeInterface<T> right); //设置树，用左右子节点
}
|
2 节点类
|
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; //左子节点
private BinaryNode<T> right; //右子节点
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.二叉树实现
|
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; //只要一个数据节点就够了
// 构造空树
public Binarytree(){
root=null;
}
// 用rootData构造树（有个根）
public Binarytree(T rootdata){
root=new BinaryNode<T>(rootdata) ;
}
// 用其他树构造树
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设置树（有个根）
@Override
public void setTree(T rootData) {
root=new BinaryNode<T>(rootData) ;
}
// 用其他树设置树
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设置树t
t.inOrderStackTraverse();
System.out.println(t.getHeight());
}
}
|
通过此文，希望能帮助到大家，谢谢大家对本站的支持！