[二叉树的定义]
二叉树(binary tree)是结点的有限集合，这个集合或者空，或者由一个根及两个互不相交的称为这个根的左子树或右子树构成.
从定义可以看出，二叉树包括：1.空树 2.只有一个根节点 3.只有左子树 4.只有右子树 5.左右子树都存在 有且仅有这5种表现形式
[二叉树与一般树的区别]
1, 一般树的子树不分次序，而二叉树的子树有左右之分.
2, 由于二叉树也是树的一种，所以大部分的树的概念，对二叉树也适用.
3, 二叉树的存贮：每个节点只需要两个指针域（左节点，右节点）,有的为了操作方便也会 增加指向父级节点的指针，除了指针域以外，还会有一个数据域用来保存当前节点的信息
[二叉树的特点：]
性质1：在二叉树的第i层上至多有2^(i-1)个节点(i >= 1)
性质2：深度为k的二叉树至多有2^k-1个节点(k >=1)
性质3：对于任意一棵二叉树T而言，其叶子节点数目为N0,度为2的节点数目为N2，则有N0 = N2 + 1。
性质4：具有n个节点的完全二叉树的深度 。
[二叉树的遍历]
[二叉树的遍历分为三种：前序遍历 中序遍历 后序遍历]
前序遍历：按照“根左右”,先遍历根节点，再遍历左子树 ，再遍历右子树
中序遍历：按照“左根右“,先遍历左子树，再遍历根节点，最后遍历右子树
后续遍历：按照“左右根”，先遍历左子树，再遍历右子树，最后遍历根节点
*其中前，后，中指的是每次遍历时候的根节点被遍历的顺序
先贴代码再作分析
BinaryTree为定义二叉树,
package cn.jq.binarytree;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
* 二叉树
* @author bsnpbus
*
*/
public class BinaryTree {
//根节点
private Node root;
//遍历后存入list
private List<Node> list = new ArrayList<Node>();
public BinaryTree(){}
public BinaryTree(Node root) {
this.root = root;
}
public Node getRoot() {
return root;
}
public List<Node> getList() {
return list;
}
//定义节点类
/**
* 内部类,可以四种访问权限，public/protected/private/默认
* public:则可以在任何地方访问，protected只能同一包或继承外部类来访问，private只能在外部类内部访问，默认不写只能在同一个包或外部类内部访问
* @author bsnpbus
*
*/
class Node{
private String data;
private Node lchild;//定义指向左子树的指针
private Node rchild;//定义指向右子树的指针
public Node(String data, Node lchild, Node rchild) {
this.data = data;
this.lchild = lchild;
this.rchild = rchild;
}
public String getData() {
return data;
}
}
/**
* 前序遍历，结果存入list中
*/
public void preOrder(Node node){
list.add(node);//先将根节点存入list中
// 先遍历左子树
if (node.lchild != null)
{
preOrder(node.lchild);
}
// 无论走到哪一层,只要当前节点左子树为空,就去右子树遍历
if (node.rchild != null)
{
preOrder(node.rchild);
}
}
/**
* 中序遍历，结果存入list中
*/
public void midOrder(Node node) {
//先遍历左子树
if (node.lchild != null) {
midOrder(node.lchild);
}
list.add(node);
if(node.rchild != null) {
midOrder(node.rchild);
}
}
/**
* 后续遍历,结果存入list
* @param node
*/
public void postOrder(Node node) {
if (node.lchild != null) {
postOrder(node.lchild);
}
if (node.rchild != null) {
postOrder(node.rchild);
}
list.add(node);
}
/**
* 返回树的深度
* @param node
* @return
*/
public int getTreeDepth(Node node) {
if(node.lchild == null && node.rchild == null) {
return 1;
}
int left=0, right=0;
if (node.lchild != null) {
left = getTreeDepth(node.lchild);
}
if (node.rchild != null) {
right = getTreeDepth(node.rchild);
}
return left > right?left+1:right+1;
}
/**
* 采用栈进行排序1(前序),
*
* @param node
*/
public void iterativeOrder(Node node) {
Stack<Node> stack = new Stack<Node>();
if (node != null) {
stack.push(node);
while (!stack.empty()) {
node = stack.pop();
list.add(node);//插入list
if (node.rchild != null)
stack.push(node.rchild);
if (node.lchild != null)
stack.push(node.lchild);
}
}
}
/**
* 采用栈进行排序2(前序),
*
* @param node
*/
public void iterativeOrder2(Node node) {
Stack<Node> stack = new Stack<Node>();
while (node != null || stack.size() > 0) {
while (node != null) {//压入所有的左节点,
list.add(node);
stack.push(node);
node = node.lchild;
}
if (stack.size() > 0) {
node = stack.pop();
node = node.rchild;
}
}
}
}
做一个测试类
package cn.jq.binarytree;
import java.util.List;
import cn.jq.binarytree.BinaryTree.Node;
public class LoopBinaryTree {
//创建一个树
public static BinaryTree initBinaryTree() {
Node x = new BinaryTree().new Node("X", null, null);
Node y = new BinaryTree().new Node("Y", null, null);
Node z = new BinaryTree().new Node("Z", null, null);
Node d = new BinaryTree().new Node("D", x, y);
Node e = new BinaryTree().new Node("E", null, z);
Node f = new BinaryTree().new Node("F", null, null);
Node c = new BinaryTree().new Node("C", e, f);
Node b = new BinaryTree().new Node("B", d, null);
Node a = new BinaryTree().new Node("A", b, c);
Node root = a;
return new BinaryTree(root);
}
public static void main(String args[]) {
BinaryTree tree = LoopBinaryTree.initBinaryTree();
//tree.preOrder(tree.getRoot());//递归前序遍历
//tree.midOrder(tree.getRoot());//递归中序遍历
//tree.postOrder(tree.getRoot());//递归后序遍历
//tree.iterativeOrder1(tree.getRoot());//栈方式遍历1
tree.iterativeOrder2(tree.getRoot());//栈方式遍历2
List<Node> list = tree.getList();
for (int i=0; i<list.size(); i++) {
Node node = (Node) list.get(i);
System.out.print(node.getData()+", ");
}
System.out.println("");
//获取树的深度
System.out.println("树的深度为:"+tree.getTreeDepth(tree.getRoot()));
}
}
该树结构如下图
binarytree1.jpg
输出结果:
1,递归前序 A, B, D, X, Y, C, E, Z, F,
2,递归中序 X, D, Y, B, A, E, Z, C, F,
3,递归后序 X, Y, D, B, Z, E, F, C, A,
4,栈方式1(前序) A, B, D, X, Y, C, E, Z, F,
5,栈方式2(前序) A, B, D, X, Y, C, E, Z, F,
[遍历方式分析]
4, 栈方式1分析
/**
* 采用栈进行排序1,(前序)
*
* @param node
*/
public void iterativeOrder1(Node node) {
Stack<Node> stack = new Stack<Node>();
if (node != null) {
stack.push(node);
while (!stack.empty()) {
node = stack.pop();
list.add(node);//插入list
if (node.rchild != null)
stack.push(node.rchild);
if (node.lchild != null)
stack.push(node.lchild);
}
}
}
对栈遍历分析:
Untitled1.png
网友评论