java实现二叉树的创建及5种遍历方法(总结)

用java实现的数组创建二叉树以及递归先序遍历，递归中序遍历，递归后序遍历，非递归前序遍历，非递归中序遍历，非递归后序遍历，深度优先遍历，广度优先遍历8种遍历方式：

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

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

package myTest;

import java.util.ArrayList;

import java.util.LinkedList;

import java.util.List;

import java.util.Stack;

public class myClass {

public static void main(String[] args) {

// TODO Auto-generated method stub

myClass tree = new myClass();

int[] datas = new int[]{1,2,3,4,5,6,7,8,9};

List<Node> nodelist = new LinkedList<>();

tree.creatBinaryTree(datas, nodelist);

Node root = nodelist.get(0);

System.out.println("递归先序遍历：");

tree.preOrderTraversal(root);

System.out.println();

System.out.println("非递归先序遍历：");

tree.preOrderTraversalbyLoop(root);

System.out.println();

System.out.println("递归中序遍历：");

tree.inOrderTraversal(root);

System.out.println();

System.out.println("非递归中序遍历：");

tree.inOrderTraversalbyLoop(root);

System.out.println();

System.out.println("递归后序遍历：");

tree.postOrderTraversal(root);

System.out.println();

System.out.println("非递归后序遍历：");

tree.postOrderTraversalbyLoop(root);

System.out.println();

System.out.println("广度优先遍历：");

tree.bfs(root);

System.out.println();

System.out.println("深度优先遍历：");

List<List<Integer>> rst = new ArrayList<>();

List<Integer> list = new ArrayList<>();

tree.dfs(root,rst,list);

System.out.println(rst);

}

/**

*

* @param datas 实现二叉树各节点值的数组

* @param nodelist 二叉树list

*/

private void creatBinaryTree(int[] datas,List<Node> nodelist){

//将数组变成node节点

for(int nodeindex=0;nodeindex<datas.length;nodeindex++){

Node node = new Node(datas[nodeindex]);

nodelist.add(node);

}

//给所有父节点设定子节点

for(int index=0;index<nodelist.size()/2-1;index++){

//编号为n的节点他的左子节点编号为2*n 右子节点编号为2*n+1 但是因为list从0开始编号，所以还要+1

//这里父节点有1（2,3）,2（4,5）,3（6,7）,4（8,9） 但是最后一个父节点有可能没有右子节点 需要单独处理

nodelist.get(index).setLeft(nodelist.get(index*2+1));

nodelist.get(index).setRight(nodelist.get(index*2+2));

}

//单独处理最后一个父节点因为它有可能没有右子节点

int index = nodelist.size()/2-1;

nodelist.get(index).setLeft(nodelist.get(index*2+1)); //先设置左子节点

if(nodelist.size() % 2 == 1){ //如果有奇数个节点，最后一个父节点才有右子节点

nodelist.get(index).setRight(nodelist.get(index*2+2));

}

/**

* 遍历当前节点的值

* @param nodelist

* @param node

*/

public void checkCurrentNode(Node node){

System.out.print(node.getVar()+" ");

}

/**

* 先序遍历二叉树

* @param root 二叉树根节点

*/

public void preOrderTraversal(Node node){

if (node == null) //很重要，必须加上当遇到叶子节点用来停止向下遍历

return;

checkCurrentNode(node);

preOrderTraversal(node.getLeft());

preOrderTraversal(node.getRight());

}

/**

* 中序遍历二叉树

* @param root 根节点

*/

public void inOrderTraversal(Node node){

if (node == null) //很重要，必须加上

return;

inOrderTraversal(node.getLeft());

checkCurrentNode(node);

inOrderTraversal(node.getRight());

}

/**

* 后序遍历二叉树

* @param root 根节点

*/

public void postOrderTraversal(Node node){

if (node == null) //很重要，必须加上

return;

postOrderTraversal(node.getLeft());

postOrderTraversal(node.getRight());

checkCurrentNode(node);

}

/**

* 非递归前序遍历

* @param node

*/

public void preOrderTraversalbyLoop(Node node){

Stack<Node> stack = new Stack();

Node p = node;

while(p!=null || !stack.isEmpty()){

while(p!=null){ //当p不为空时，就读取p的值，并不断更新p为其左子节点，即不断读取左子节点

checkCurrentNode(p);

stack.push(p); //将p入栈

p = p.getLeft();

}

if(!stack.isEmpty()){

p = stack.pop();

p = p.getRight();

}

/**

* 非递归中序遍历

* @param node

*/

public void inOrderTraversalbyLoop(Node node){

Stack<Node> stack = new Stack();

Node p = node;

while(p!=null || !stack.isEmpty()){

while(p!=null){

stack.push(p);

p = p.getLeft();

}

if(!stack.isEmpty()){

p = stack.pop();

checkCurrentNode(p);

p = p.getRight();

}

/**

* 非递归后序遍历

* @param node

*/

public void postOrderTraversalbyLoop(Node node){

Stack<Node> stack = new Stack<>();

Node p = node,prev = node;

while(p!=null || !stack.isEmpty()){

while(p!=null){

stack.push(p);

p = p.getLeft();

}

if(!stack.isEmpty()){

Node temp = stack.peek().getRight();

if(temp == null||temp == prev){

p = stack.pop();

checkCurrentNode(p);

prev = p;

p = null;

}else{

p = temp;

}

/**

* 广度优先遍历（从上到下遍历二叉树）

* @param root

*/

public void bfs(Node root){

if(root == null) return;

LinkedList<Node> queue = new LinkedList<Node>();

queue.offer(root); //首先将根节点存入队列

//当队列里有值时，每次取出队首的node打印，打印之后判断node是否有子节点，若有，则将子节点加入队列

while(queue.size() > 0){

Node node = queue.peek();

queue.poll(); //取出队首元素并打印

System.out.print(node.var+" ");

if(node.left != null){ //如果有左子节点，则将其存入队列

queue.offer(node.left);

}

if(node.right != null){ //如果有右子节点，则将其存入队列

queue.offer(node.right);

}

/**

* 深度优先遍历

* @param node

* @param rst

* @param list

*/

public void dfs(Node node,List<List<Integer>> rst,List<Integer> list){

if(node == null) return;

if(node.left == null && node.right == null){

list.add(node.var);

/* 这里将list存入rst中时，不能直接将list存入，而是通过新建一个list来实现，

* 因为如果直接用list的话，后面remove的时候也会将其最后一个存的节点删掉*/

rst.add(new ArrayList<>(list));

list.remove(list.size()-1);

}

list.add(node.var);

dfs(node.left,rst,list);

dfs(node.right,rst,list);

list.remove(list.size()-1);

}

/**

* 节点类

* var 节点值

* left 节点左子节点

* right 右子节点

*/

class Node{

int var;

Node left;

Node right;

public Node(int var){

this.var = var;

this.left = null;

this.right = null;

}

public void setLeft(Node left) {

this.left = left;

}

public void setRight(Node right) {

this.right = right;

}

public int getVar() {

return var;

}

public void setVar(int var) {

this.var = var;

}

public Node getLeft() {

return left;

}

public Node getRight() {

return right;

}

运行结果：

递归先序遍历：
1 2 4 8 9 5 3 6 7

非递归先序遍历：
1 2 4 8 9 5 3 6 7

递归中序遍历：
8 4 9 2 5 1 6 3 7

非递归中序遍历：
8 4 9 2 5 1 6 3 7

递归后序遍历：
8 9 4 5 2 6 7 3 1

非递归后序遍历：
8 9 4 5 2 6 7 3 1

广度优先遍历：
1 2 3 4 5 6 7 8 9

深度优先遍历：
[[1, 2, 4, 8], [1, 2, 4, 9], [1, 2, 5], [1, 3, 6], [1, 3, 7]]

以上这篇java实现二叉树的创建及5种遍历方法(总结)就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持快网idc。

java实现二叉树的创建及5种遍历方法(总结)

相关文章

快网idc优惠网

相关文章

微信

快网idc优惠网

QQ交流群