樹、森林和二叉樹的轉(zhuǎn)換
- 樹轉(zhuǎn)換為二叉樹
- 森林轉(zhuǎn)換為樹
- 二叉樹轉(zhuǎn)換為樹
- 二叉樹轉(zhuǎn)換為森林
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");
}
/**
* 構(gòu)建二叉樹
* 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;
}
/**
* #方法創(chuàng)建二叉樹
* 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) {
//根結(jié)點(diǎn)
root = treeNode;
}
nodes.remove(0);
//創(chuàng)建左孩子
treeNode.leftChild = createTree(size, nodes);
//創(chuàng)建右孩子
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;
}
/**
* 獲取二叉樹的結(jié)點(diǎn)數(shù)
*
* @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);
}
}
/**
* 求二叉樹的葉子節(jié)點(diǎn) 先計(jì)算左子樹葉子節(jié)點(diǎn)放接，再計(jì)算右子樹葉子節(jié)點(diǎn)
*
* @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;
}
/**
* 找二叉樹最左邊的孩子節(jié)點(diǎn)
*
* @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;
}
/**
* 后續(xù)遍歷 - 非遞歸
* 步驟1 如果結(jié)點(diǎn)有左子樹，該結(jié)點(diǎn)入棧婚惫； 如果結(jié)點(diǎn)沒有左子樹，訪問該結(jié)點(diǎn)蒜撮；
* 步驟2 如果結(jié)點(diǎn)有右子樹襟士，重復(fù)
* 步驟3 如果結(jié)點(diǎn)沒有右子樹（結(jié)點(diǎn)訪問完畢），根據(jù)棧頂指示回退烈拒，訪問棧頂元素圆裕，
* 并訪問右子樹，重復(fù)步驟 如果棧為空荆几，表示遍歷結(jié)束吓妆。
*/
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;
}
}
}
/**
* 中續(xù)遍歷 - 非遞歸
* 1、讓做孩子循環(huán)進(jìn)棧吨铸，當(dāng)沒有左孩子退出行拢，執(zhí)行出棧。
* 2诞吱、獲取剛出棧的結(jié)點(diǎn)舟奠，為空時(shí)出棧并處理右子樹，不為空循環(huán)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);
}
}
/**
* 前序遍歷——非迭代 需要借助棧模式進(jìn)行操作
*/
public void nonRecOrder(TreeNode node) {
if (node == null) {
return;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(node);
while (!stack.isEmpty()) {
// 出棧和進(jìn)棧
TreeNode n = stack.pop();// 彈出根結(jié)點(diǎn)
// 壓入子結(jié)點(diǎn)
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層保存在一個(gè)隊(duì)列中，然后按節(jié)點(diǎn)訪問咙俩，并把已經(jīng)訪問節(jié)點(diǎn)的左右孩子節(jié)點(diǎn)放在第二個(gè)隊(duì)列中耿戚，當(dāng)?shù)谝粋€(gè)隊(duì)
* 列中的所有節(jié)點(diǎn)都訪問完成之后，交換兩個(gè)節(jié)點(diǎn)阿趁。這樣重復(fù)下去膜蛔，知道所有層的節(jié)點(diǎn)都被訪問，這樣做的代價(jià)就是空間復(fù)雜度有點(diǎn)高脖阵。
*/
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()) {//某一層的所有孩子結(jié)點(diǎn)
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
* 遞歸遍歷飞几，遍歷某一層的數(shù)據(jù)，想要遍歷整個(gè)樹独撇，對層次進(jìn)行for循環(huán)
*
* @param node
* 起始結(jié)點(diǎn)為根結(jié)點(diǎn)
* @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("非遞歸后續(xù)遍歷:");
binaryTree.nonPostOrder(binaryTree.root);
for (int i = 0; i < 3; i++) {
binaryTree.broadLevelTree(binaryTree.root, i);
}
binaryTree.broadLevelTree();
}
}
