树、森林和二叉树的转换
- 树转换为二叉树
- 森林转换为树
- 二叉树转换为树
- 二叉树转换为森林
Paste_Image.png
代码
package com.self.data;
import java.util.ArrayList;
import java.util.Stack;
public class BinaryTree {
private TreeNode root = null;
public BinaryTree() {
root = new TreeNode("A");
}
/**
* 构建二叉树
* A
* B C
* D E # F
* # # # # # #
*
* ABD##E##C#F##
*/
public void createBinaryTree() {
TreeNode nodeB = new TreeNode("B");
TreeNode nodeC = new TreeNode("C");
TreeNode nodeD = new TreeNode("D");
TreeNode nodeE = new TreeNode("E");
TreeNode nodeF = new TreeNode("F");
root.leftChild = nodeB;
root.rightChild = nodeC;
nodeB.leftChild = nodeD;
nodeB.rightChild = nodeE;
nodeC.rightChild = nodeF;
}
/**
* #方法创建二叉树
* ABD##E##C#F##
*
* @return
*/
public void createTree(ArrayList<String> nodes){
if (nodes==null || nodes.size()==0) {
return;
}
createTree(nodes.size(), nodes);
}
public TreeNode createTree(int size,ArrayList<String> nodes){
TreeNode treeNode = null;
int index = size - nodes.size();
String ch = nodes.get(0);
if ("#".equals(ch)) {
nodes.remove(0);
return null;
}
treeNode = new TreeNode(index, ch);
if (index==0) {
//根结点
root = treeNode;
}
nodes.remove(0);
//创建左孩子
treeNode.leftChild = createTree(size, nodes);
//创建右孩子
treeNode.rightChild = createTree(size, nodes);
return treeNode;
}
/**
* 求二叉树的高度
*
* @author Administrator
*
*/
public int getHeight() {
return getHeight(root);
}
private int getHeight(TreeNode node) {
if (node == null) {
return 0;
}
int i = getHeight(node.leftChild);
int j = getHeight(node.rightChild);
return (i < j) ? j + 1 : i + 1;
}
/**
* 获取二叉树的结点数
*
* @author Administrator
*/
public int getSize() {
return getSize(root);
}
private int getSize(TreeNode node) {
if (node == null) {
return 0;
} else {
return 1 + getSize(node.leftChild) + getSize(node.rightChild);
}
}
/**
* 求二叉树的叶子节点 先计算左子树叶子节点，再计算右子树叶子节点
*
* @return
*/
public int getLeafSize() {
return getLeafSize(root);
}
private int getLeafSize(TreeNode node) {
int leafSize = 0;
if (node == null) {
return 0;
}
if (node.leftChild == null && node.rightChild == null) {
leafSize++;
}
leafSize += getLeafSize(node.leftChild);
leafSize += getLeafSize(node.rightChild);
return leafSize;
}
/**
* 找二叉树最左边的孩子节点
*
* @return
*/
private TreeNode getLeftMostNode(TreeNode node, Stack<TreeNode> stack) {
if (node == null) {
return null;
}
while (node.leftChild != null) {
stack.push(node);
node = node.leftChild;
}
return node;
}
/**
* 后续遍历 - 非递归
* 步骤1 如果结点有左子树，该结点入栈； 如果结点没有左子树，访问该结点；
* 步骤2 如果结点有右子树，重复
* 步骤3 如果结点没有右子树（结点访问完毕），根据栈顶指示回退，访问栈顶元素，
* 并访问右子树，重复步骤 如果栈为空，表示遍历结束。
*/
public void nonPostOrder(TreeNode node) {
if (node == null) {
return;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode treeNode = getLeftMostNode(node, stack);
while (treeNode != null) {
System.out.println("nonRecOrderdata" + treeNode.getData());
if (treeNode.rightChild != null) {
treeNode = getLeftMostNode(treeNode.rightChild, stack);
} else if (!stack.isEmpty()) {
treeNode = stack.pop();
} else {
treeNode = null;
}
}
}
/**
* 中续遍历 - 非递归
* 1、让做孩子循环进栈，当没有左孩子退出，执行出栈。
* 2、获取刚出栈的结点，为空时出栈并处理右子树，不为空循环1,2。
*/
public void nonMidOrder(TreeNode node) {
if (node == null) {
return;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode root = node;
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);// 先访问再入栈
root = root.leftChild;
}
root = stack.pop();
System.out.println("nonRecOrderdata " + root.getData());
root = root.rightChild;// 如果是null，出栈并处理右子树
}
}
/**
* 前序遍历——迭代
*
* @author Administrator
*
*/
public void preOrder(TreeNode node) {
if (node == null) {
return;
} else {
System.out.println("preOrder data:" + node.getData());
preOrder(node.leftChild);
preOrder(node.rightChild);
}
}
/**
* 前序遍历——非迭代 需要借助栈模式进行操作
*/
public void nonRecOrder(TreeNode node) {
if (node == null) {
return;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(node);
while (!stack.isEmpty()) {
// 出栈和进栈
TreeNode n = stack.pop();// 弹出根结点
// 压入子结点
System.out.println("nonRecOrder data" + n.getData());
if (n.rightChild != null) {
stack.push(n.rightChild);
}
if (n.leftChild != null) {
stack.push(n.leftChild);
}
}
}
/**
* 中序遍历——迭代
*
* @author Administrator
*
*/
public void midOrder(TreeNode node) {
if (node == null) {
return;
} else {
midOrder(node.leftChild);
System.out.println("midOrder data:" + node.getData());
midOrder(node.rightChild);
}
}
/**
* 后序遍历——迭代
*
* @author Administrator
*
*/
public void postOrder(TreeNode node) {
if (node == null) {
return;
} else {
postOrder(node.leftChild);
postOrder(node.rightChild);
System.out.println("postOrder data:" + node.getData());
}
}
public class TreeNode {
private int index;
private String data;
private TreeNode leftChild;
private TreeNode rightChild;
public int getIndex() {
return index;
}
public void setIndex(int index) {
this.index = index;
}
public String getData() {
return data;
}
public void setData(String data) {
this.data = data;
}
public TreeNode(int index, String data) {
this.index = index;
this.data = data;
this.leftChild = null;
this.rightChild = null;
}
public TreeNode(String data) {
this.data = data;
this.leftChild = null;
this.rightChild = null;
}
}
/**
* 层次遍历方法1
* 首先把第0层保存在一个队列中，然后按节点访问，并把已经访问节点的左右孩子节点放在第二个队列中，当第一个队
* 列中的所有节点都访问完成之后，交换两个节点。这样重复下去，知道所有层的节点都被访问，这样做的代价就是空间复杂度有点高。
*/
private void broadLevelTree() {
LinkedList<TreeNode> linkedList = new LinkedList<BinaryTree.TreeNode>();
LinkedList<TreeNode> secondList = new LinkedList<BinaryTree.TreeNode>();
linkedList.add(root);
System.out.println("层次遍历：");
TreeNode tmpRoot = null;
while (!linkedList.isEmpty()) {//层次
while (!linkedList.isEmpty()) {//某一层的所有孩子结点
tmpRoot = linkedList.removeFirst();
System.out.print(" " + tmpRoot.data);
if (tmpRoot.leftChild != null) {
secondList.add(tmpRoot.leftChild);
}
if (tmpRoot.rightChild != null) {
secondList.add(tmpRoot.rightChild);
}
}
linkedList.addAll(secondList);
secondList.clear();
}
}
/**
* 层次遍历方法2
* 递归遍历，遍历某一层的数据，想要遍历整个树，对层次进行for循环
*
* @param node
* 起始结点为根结点
* @param level
* 第几层
* @return
*/
private int broadLevelTree(TreeNode node, int level) {
if (node == null) {
return 0;
}
if (level == 0) {
System.out.println("层次遍历: " + node.data);
return 1;
}
return broadLevelTree(node.leftChild, level - 1)
+ broadLevelTree(node.rightChild, level - 1);
}
public static void main(String[] args) {
BinaryTree binaryTree = new BinaryTree();
// binaryTree.createBinaryTree();
String[] nodes = new String[]{"A","B","D","#","#","E","#","#","C",
"#","F","#","#"};
ArrayList<String> listNodes = new ArrayList<String>();
for (int i = 0; i < nodes.length; i++) {
listNodes.add(nodes[i]);
}
binaryTree.createTree(listNodes);
int height = binaryTree.getHeight();
System.out.println("treeHeihgt:" + height);
int size = binaryTree.getSize();
System.out.println("treeSize:" + size);
int leafSize = binaryTree.getLeafSize();
System.out.println("leafSize:" + leafSize);
System.out.println("前序遍历:");
binaryTree.preOrder(binaryTree.root);
System.out.println("中序遍历:");
binaryTree.midOrder(binaryTree.root);
System.out.println("后序遍历:");
binaryTree.postOrder(binaryTree.root);
System.out.println("非递归遍历:");
binaryTree.nonRecOrder(binaryTree.root);
System.out.println("非递归中序遍历:");
binaryTree.nonMidOrder(binaryTree.root);
System.out.println("非递归后续遍历:");
binaryTree.nonPostOrder(binaryTree.root);
for (int i = 0; i < 3; i++) {
binaryTree.broadLevelTree(binaryTree.root, i);
}
binaryTree.broadLevelTree();
}
}
