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设置树tt.inOrderStackTraverse();System.out.println(t.getHeight());}} |
通过此文，希望能帮助到大家，谢谢大家对本站的支持！
