首页 > 代码库 > 二叉树
二叉树
需再次了解：
package com.qdcz.breadth.demo;
import java.util.ArrayList;
import java.util.List;
/**
*
* <p>Title: TwoforktreeAl</p>
* <p>Description:
* 二叉树定义： 二叉树(binary tree)是结点的有限集合，这个集合或者空，或者由一个根及两个互不相交的称为这个根的左子树或右子树构成. </br>
* 二叉树与一般树的区别:
* 一般树的子树不分次序，而二叉树的子树有左右之分.</br>
* 由于二叉树也是树的一种，所以大部分的树的概念，对二叉树也适用.</br>
* 二叉树的存贮：每个节点只需要两个指针域（左节点，右节点）,有的为了操作方便也会 增加指向父级节点的指针，除了指针域以外，还会有一个数据域用来保存当前节点的信息</br>
* 二叉树的特点 :
* 性质1：在二叉树的第i层上至多有2^(i-1)个节点(i >= 1)</br>
* 性质2：深度为k的二叉树至多有2^(k-1)个节点(k >=1)</br>
* 性质3：对于任意一棵二叉树T而言，其叶子节点数目为N0,度为2的节点数目为N2，则有N0 = N2 + 1。</br>
* 性质4：具有n个节点的完全二叉树的深度 。</br>
* 二叉树的遍历分为三种：前序遍历 中序遍历 后序遍历</br>
* 前序遍历：按照“根左右”,先遍历根节点，再遍历左子树 ，再遍历右子树</br>
* 中序遍历：按照“左根右“,先遍历左子树，再遍历根节点，最后遍历右子树</br>
* 后续遍历：按照“左右根”，先遍历左子树，再遍历右子树，最后遍历根节点 </br>
* <a href="http://blog.csdn.net/gfj0814/article/details/51637696">具体资料</a></p>
* <p>Company:奇点创智 </p>
* <p>Version:1.0 </p>
* @author Administrator
* @date 2017年6月6日 上午11:06:49
*/
public class TwoforktreeAl {
private Node root;
private List<Node> list=new ArrayList<>();
public TwoforktreeAl() {
init();
}
/**
*
*<p>Title:init </p>
*<p>Description:初始化。先从叶子开始。由叶到跟 </p>
*@return void
*@author Administrator
*@date 2017年6月6日 上午11:05:44
*/
private void init() {
Node x=new Node("X",null,null);
Node y=new Node("Y",null,null);
Node d=new Node("D",x,y);
Node e=new Node("E",null,null);
Node f=new Node("F",null,null);
Node c=new Node("C",e,f);
Node b=new Node("B",d,null);
Node a=new Node("A",b,c);
root=a;
}
/**
*
* <p>Title: Node</p>
* <p>Description:定义节点类 </p>
* <p>Company: </p>
* <p>Version: </p>
* @author Administrator
* @date 2017年6月6日 上午11:02:17
*/
private class Node{
private String data;
private Node lchid;//定义指向左边字树的指针
private Node rchild;//定义指向右子树的指针
public Node(String data, Node lchid, Node rchild) {
super();
this.data = http://www.mamicode.com/data;
this.lchid = lchid;
this.rchild = rchild;
}
@Override
public String toString() {
return "[data="http://www.mamicode.com/+ data +", lchid=" + lchid + ", rchild=" + rchild+"]" ;
}
}
/**
*
*<p>Title:preOrder </p>
*<p>Description:二叉树初期遍历，遍历结果 放List;前序遍历:ABDXYCEF</p>
*@param node
*@return void
*@author Administrator
*@date 2017年6月6日 上午11:01:33
*/
public void preOrder(Node node){
list.add(node);
if(node.lchid!=null){//如果左子树不为空继续往左找，在递归调用方法的时候一直会将子树的根存入list，这就做到了先遍历根节点
preOrder(node.lchid);
}
if(node.rchild!=null){//无论走到哪一层，只要当前节点左子树为空，那么就可以在右子树上遍历，保证了根左右的遍历顺序
preOrder(node.rchild);
}
}
/**
*
*<p>Title: inOrder</p>
*<p>Description:对二叉树进行中期遍历，结果存list</p>
*@param node
*@return void
*@author Administrator
*@date 2017年6月6日 上午11:00:39
*/
public void inOrder(Node node){
if(node.lchid!=null){
inOrder(node.lchid);
}
list.add(node);
if(node.rchild!=null){
inOrder(node.rchild);
}
}
/**
*
*<p>Title: postOrder</p>
*<p>Description:对二叉树后期遍历,遍历结果储到List中 </p>
*@param node
*@return void
*@author Administrator
*@date 2017年6月6日 上午10:59:05
*/
public void postOrder(Node node){
if(node.lchid!=null){
postOrder(node.lchid);
}
if(node.rchild!=null){
postOrder(node.rchild);
}
list.add(node);
}
/**
*
*<p>Title:getTreeDepth </p>
*<p>Description:返回当前深度</br>
* 说明:
* 1、如果一棵树只有一个结点，它的深度为1。</br>
* 2、如果根结点只有左子树而没有右子树，那么树的深度是其左子树的深度加1；</br>
* 3、如果根结点只有右子树而没有左子树，那么树的深度应该是其右子树的深度加1；</br>
* 4、如果既有右子树又有左子树，那该树的深度就是其左、右子树深度的较大值再加1。</br>
* </p>
*@param node
*@return
*@return int
*@author Administrator
*@date 2017年6月6日 上午10:57:25
*/
public int getTreeDepth(Node node){
if(node.lchid==null&&node.rchild==null){
return 1;
}
int left=0,right=0;
if(node.lchid!=null){
left=getTreeDepth(node.lchid);
}
if(node.rchild!=null){
right=getTreeDepth(node.rchild);
}
return left>right? left+1:right+1;
}
/**
*
*<p>Title: getResult</p>
*<p>Description:获取遍历结果 </p>
*@return
*@return List<Node>
*@author Administrator
*@date 2017年6月6日 上午10:57:09
*/
public List<Node> getResult(){
return list;
}
public static void main(String[] args) {
TwoforktreeAl tfa=new TwoforktreeAl();
System.out.print("根节点为："+tfa.root.toString());
System.out.println();
tfa.postOrder(tfa.root);
for (Node node : tfa.getResult()) {
System.out.print(node.data);
}
System.out.println();
System.out.println("树的深度是："+tfa.getTreeDepth(tfa.root));
}
}
二叉树