面试2 原

尊少

``````package com.tree;

import java.util.*;

/**
* 实现对二叉树的遍历操作
*/
public class TreeOperate<T> {
public static void main(String args[]) {
TreeOperate<Integer> treeOperate = new TreeOperate<Integer>();
TreeNode treeNode2 = treeOperate.addNode(null, 2, true);
TreeNode treeNode3 = treeOperate.addNode(null, 3, false);

List<TreeNode> treeNodeList = treeOperate.noInIterator();
for (TreeNode treeNode : treeNodeList)
System.out.print(treeNode + ",");
}

static class TreeNode {
TreeNode parent;
TreeNode left;
TreeNode right;
Object data;

public TreeNode() {
}

public TreeNode(Object data) {
this.data = data;
}

public TreeNode(TreeNode parent, TreeNode left, TreeNode right, Object data) {
this.parent = parent;
this.left = left;
this.right = right;
this.data = data;
}

@Override
public String toString() {
return "" +
"data=" + data
;
}
}

public TreeOperate() {
root = new TreeNode();
}

//为指定节点添加子节点
public TreeNode addNode(TreeNode parent, T data, boolean isLeft) {
if (parent == null)
parent = root;
TreeNode treeNode = new TreeNode(data);
if (isLeft)
parent.left = treeNode;
else
parent.right = treeNode;
treeNode.parent = parent;
return treeNode;
}

/**
* ****************   非递归遍历*******************************
*/
//非递归先序遍历
public List<TreeNode> noPreIterator() {
List<TreeNode> list = new ArrayList<TreeNode>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode node = root;
stack.push(node);
while (node!=null&&!stack.isEmpty())
{
TreeNode t = stack.pop();
if (t.right!=null)
stack.push(t.right);
if (t.left!=null)
stack.push(t.left);

}
return list;
}

//非递归中序遍历
public List<TreeNode> noInIterator()
{
List<TreeNode> list = new ArrayList<TreeNode>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode treeNode = root;

while (treeNode!=null || !stack.isEmpty())
{
while (treeNode !=null)
{
stack.push(treeNode);
treeNode = treeNode.left;
}
if (!stack.isEmpty())
{
treeNode = stack.pop();
treeNode = treeNode.right;
}
}
return list;
}
// 非递归后序遍历
public List<TreeNode> noPostIterator() {
List<TreeNode> list = new ArrayList<TreeNode>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode node = root;
TreeNode pre = root;
while (node!=null||!stack.isEmpty())
{

//把左节点全部进行压栈
while (node!=null)
{
stack.push(node);
node = node.left;
}
if (stack.size()>0)
{
TreeNode temp = stack.peek().right;
if (temp==null || temp==pre)
{
node = stack.pop();
pre = node;
node=null;
}else
{
node   = temp;
}

}

}
return list;
}

/**
* ****************   递归遍历*******************************
*/
private TreeNode root;

//递归后序遍历
public List<TreeNode> postIterator() {
return postIterator(root);
}

private List<TreeNode> postIterator(TreeNode node) {
List<TreeNode> list = new ArrayList<TreeNode>();

//递归访问左子树
if (node.left != null)

//递归访问右子树
if (node.right != null)
//访问根节点
return list;
}

//递归中序遍历
public List<TreeNode> inIterator() {
return inIterator(root);
}

private List<TreeNode> inIterator(TreeNode node) {
List<TreeNode> list = new ArrayList<TreeNode>();

//递归访问左子树
if (node.left != null)
//访问根节点
//递归访问右子树
if (node.right != null)
return list;
}

;

//递归先序遍历
public List<TreeNode> preIterator() {
return preIterator(root);
}

private List<TreeNode> preIterator(TreeNode node) {

List<TreeNode> list = new ArrayList<TreeNode>();
//先访问根节点
//递归访问左子树
if (node.left != null)
//递归访问右子树
if (node.right != null)
return list;
}

}``````

尊少

2016/05/27
1
0

2016/05/26
1
0
2016-08当当面试总结

2016/08/17
146
0

2017/10/24
0
0

2017/09/19
0
0

26分钟前
12
0
springboot统一校验validator实现

zzx10
27分钟前
3
0
vue组件系列-预览、放大、缩小、旋转

29分钟前
3
0
Taro Input输入内容无法绑定state问题

30分钟前
2
0
Windows10远程连接CentOS7（搭建Xrdp服务器）

Windows10远程连接CentOS7（搭建Xrdp服务器） 听语音 浏览：0 | 更新：2018-02-11 12:56 1 2 3 4 5 6 7 分步阅读 通过VNC或Xdmcp的方式远程连接linux图形桌面，虽然都很方便，但有个缺点就是...

linjin200
30分钟前
3
0