服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|JAVA教程|ASP教程|

服务器之家 - 编程语言 - JAVA教程 - java 数据结构二叉树的实现代码

java 数据结构二叉树的实现代码

2020-06-19 11:16lqh JAVA教程

这篇文章主要介绍了java 数据结构二叉树的实现代码的相关资料,需要的朋友可以参考下

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());
}
}

通过此文,希望能帮助到大家,谢谢大家对本站的支持!

延伸 · 阅读

精彩推荐