在计算机科学中，二叉树（英语：Binary tree）是每个节点最多只有两个分支(不存在分支度大于2的节点)的树结构。通常分支被称作“左子树”和“右子树”。二叉树的分支具有左右次序，不能颠倒。
二叉树的第i层至多拥有个节点数；深度为的二叉树至多总共有个节点数（定义根节点所在深度 ），而总计拥有节点数匹配的，称为“满二叉树”；深度为k有n个节点的二叉树，当且仅当其中的每一节点，都可以和同样深度k的满二叉树，序号为1到n的节点一对一对应时，称为“完全二叉树”。；对任何一棵非空的二叉树T，如果其叶片(终端节点)数为n0，分支度为2的节点数为n2，则n0= n2 + 1。
与普通树不同，普通树的节点个数至少为1，而二叉树的节点个数可以为0；普通树节点的最大分支度没有限制，而二叉树节点的最大分支度为2；普通树的节点无左、右次序之分，而二叉树的节点有左、右次序之分。
二叉树通常作为数据结构应用，典型用法是对节点定义一个标记函数，将一些值与每个节点相关系。这样标记的二叉树就可以实现二叉查找树和二元堆积，并应用于高效率的搜索和排序。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;
public class BinaryTree {
private TreeNode root = null;
//构造函数,默认创建一个根节点 可传参 这里省略
public BinaryTree() {
root = new TreeNode(1, "A");
}
/**
* 最原始的构建二叉树
* A
* B C
* D E F
*/ public void createBinaryTree() {
TreeNode nodeB = new TreeNode(2, "B");
TreeNode nodeC = new TreeNode(3, "C");
TreeNode nodeD = new TreeNode(4, "D");
TreeNode nodeE = new TreeNode(5, "E");
TreeNode nodeF = new TreeNode(6, "F");
root.leftChild = nodeB;
root.rightChild = nodeC;
nodeB.leftChild = nodeD;
nodeB.rightChild = nodeE;
nodeC.rightChild = nodeF;
}
/**
* 根据先序字符串来进行二叉树创建
* A,B,D,#,#,E,#,#,C,#,F,#,#
* @param data
*/ private void creatBinaryTreePre(ArrayList<String> data) {
//为保持原始节点下标,这里传入原始大小
creatBinaryTree(data.size(), data);
}
/**
*
* @param size 原始大小
* @param data 待创建的节点数组
* @return
*/ private TreeNode creatBinaryTree(int size, ArrayList<String> data) {
String d = data.get(0);
TreeNode node;
//得到剩余的第一个节点在原节点串中的位置,这样就可以根据index=0判断是不是根节点
int index = size - data.size();
//如果是#则说明是一个空节点 返回并移除
if (d.equals("#")) {
node = null;
data.remove(0);
return node;
}
//不是#则创建一个新节点
node = new TreeNode(index, d);
//根据index判断根节点是否存在
if (index == 0) {
//创建根节点
root = node;
}
//移除已创建的
data.remove(0);
//按先序递归左右
node.leftChild = creatBinaryTree(size, data);
node.rightChild = creatBinaryTree(size, data);
return node;
}
/**
* 求二叉树的高度
*
* @author Administrator
*/ public int getHeight() {
return getHeight(root);
}
/**
* A
* B C
* @param node
* @return
*/ private int getHeight(TreeNode node) {
if (node == null) {
return 0;
} else {
//递归,第一次是A的时候 传入B,C,由于B没有左右B的递归i,j均为0,而return时返回的是i+1,
// 最后返回A的递归i=1,j=1,不满足i<j,这时返回i+1,最后为2
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 {
//这个很好理解,不为空就+1,因为根节点如果为空就返回了0,走到这里说明根节点不为空,得+1
return 1 + getSize(node.leftChild) + getSize(node.rightChild);
}
}
/**
* 前序遍历——迭代
*
* @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);
}
}
/**
* 中旬遍历 非遍历
*
* @param node
*/ public void nonMidOrder(TreeNode node) {
Stack<TreeNode> stack = new Stack<TreeNode>();
while (node != null) {
while (node != null) {
if (node.rightChild != null) {
stack.push(node.rightChild);
}
stack.push(node);
node = node.leftChild;
}
node = stack.pop();
while (!stack.isEmpty() && (node.rightChild == null)) {
System.out.println(node.data);
node = stack.pop();
}
System.out.println(node.data);
if (!stack.isEmpty()) {
node = stack.pop();
} else {
node = null;
}
}
}
/**
* 后序遍历——迭代
*
* @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());
}
}
/**
* 非递归实现后序遍历 单栈法
* A
* B C
* D E F
*/ protected static void nonPostOrder(TreeNode p) {
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode node = p;
TreeNode prev = p;
while ((node != null) || (stack.size() > 0)) {
while (node != null) {
stack.push(node);
node = node.leftChild;
}
if (stack.size() > 0) {
TreeNode temp = stack.peek().rightChild;
if ((temp == null) || (temp == prev)) {
node = stack.pop();
System.out.println(node.data);
prev = node;
node = null;
} else {
node = temp;
}
}
}
}
public static void main(String[] args) {
BinaryTree binaryTree = new BinaryTree();
String[] dataArray = new String("A,B,D,#,#,E,#,#,C,#,F,#,#").split(",");
ArrayList data = new ArrayList(Arrays.asList(dataArray));
binaryTree.creatBinaryTreePre(data);
// binaryTree.createBinaryTree();
int height = binaryTree.getHeight();
System.out.println("treeHeihgt:" + height);
int size = binaryTree.getSize();
System.out.println("treeSize:" + size);
binaryTree.preOrder(binaryTree.root);
// binaryTree.midOrder(binaryTree.root);
// binaryTree.postOrder(binaryTree.root);
// binaryTree.nonRecOrder(binaryTree.root);
// binaryTree.nonMidOrder(binaryTree.root);
// binaryTree.nonPostOrder(binaryTree.root);
}
public class TreeNode {
private int index;
private String data;
private TreeNode leftChild;
private TreeNode rightChild;
public TreeNode(int index, String data) {
this.index = index;
this.data = data;
this.leftChild = null;
this.rightChild = null;
}
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;
}
}
}
另外一种实现，这种使用Comparable来进行排序
import java.util.Arrays;
public class BinaryTree {
public static void main(String[] args) {
BinaryTreeOld bt = new BinaryTreeOld();
bt.add("B");
bt.add("A");
bt.add("X");
System.out.println(Arrays.toString(bt.toArray()));
}
}
class BinaryTreeOld {
//--------------
private Node root;
private int count;
private Object[] retData;
private int foot = 0;
public Object[] toArray() {
this.foot = 0;
this.retData = new Object[this.count];
this.root.toArrayNode();
return this.retData;
}
public void add(Object data) {
if (data == null) {
return;
}
Node newNode = new Node((Comparable) data);
if (this.root == null) {
this.root = newNode;
} else {
this.root.addNode(newNode);
}
this.count++;
}
public class Node {
private Comparable data; //保存的操作数据 Comparable子类比较大小
private Node left;
private Node right;
public Node(Comparable data) {
this.data = data;
}
public void addNode(Node newNode) {
if (this.data.compareTo(newNode.data) > 0) {
if (this.left == null) {
this.left = newNode;
} else {
this.left.addNode(newNode);
}
} else {
if (this.right == null) {
this.right = newNode;
} else {
this.right.addNode(newNode);
}
}
}
public void toArrayNode() {
if (this.left != null) {
this.left.toArrayNode();
}
BinaryTreeOld.this.retData[BinaryTreeOld.this.foot++] = this.data;
if (this.right != null) {
this.right.toArrayNode();
}
}
}
}
讲解的话，有难度，不知道怎么用文字表示，这个最好还是看视频，配合图讲解，我也只是了解了下
本站广告由 Google AdSense 提供
0条评论