数据结构二叉树
一下是java语言编写的关于数据结构中二叉树的一些常见操作：
首先需要定义二叉树的节点类Node，代码如下：
/**
* 二叉树的节点类
* @author xxqi1229
*
*/
public class Node {
private Node leftChild;//左孩子
private Node rightChild;//有孩子
private int data;//该节点的值，此处用int类型的值为例
boolean canVisit = false ;//此变量的值在后序非递归遍历的时候需要用到，表示节点是否可以直接访问
public Node(){}
public Node(int data){
leftChild = rightChild = null ;
this.data = data ;
}
public Node getLeftChild() {
return leftChild;
}
public void setLeftChild(Node leftChild) {
this.leftChild = leftChild;
}
public Node getRightChild() {
return rightChild;
}
public void setRightChild(Node rightChild) {
this.rightChild = rightChild;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public String toString(){
return "" + this.data ;
}
public boolean isCanVisit() {
return canVisit;
}
public void setCanVisit(boolean canVisit) {
this.canVisit = canVisit;
}
}
有了这个节点类之后，就是二叉树的一些具体操作了，这些操作都封装在Tree类中，Tree的代码如下：
package edu.qc.tree;
import java.util.Stack;
/**
* 二叉树
* @author Administrator
*
*/
public class Tree {
private Node root ;//根结点
private int count ;//节点个数
private boolean find = false ;//在查找特定节点的时候需要使用该成员变量
public Tree(){//无参构造函数
this.root = null ;
this.count = 0 ;
}
public Tree(int[] data){
count = 0 ;
root = this.createTree(root, data, 1) ;
}
/**
* 二叉树的创建
* @param node :创建的节点
* @param data : 节点的值
* @param index : 数组的下标
* @return
*/
public Node createTree(Node node , int[] data , int index){
if(index > data.length){//数组下标越界
return null ;
}
if(null == node){//如果节点不存在则创建新节点，并设置节点的值。
node = new Node(data[index-1]) ;
}else{
node.setData(data[index-1]) ;
}
count++ ;//记录节点的数目
//递归的创建该节点的左孩子
Node leftNode = createTree(node.getLeftChild() , data , 2*index) ;
//递归的创建该节点的右孩子
Node rightNode = createTree(node.getRightChild() , data , 2*index+1) ;
//设置当前节点的左孩子和有孩子
node.setLeftChild(leftNode) ;
node.setRightChild(rightNode) ;
return node ;//返回当前创建的节点
}
/**
* 后序遍历递归算法
* @param node
*/
public void postList(Node node){
if(node != null){
postList(node.getLeftChild()) ;//遍历左孩子
postList(node.getRightChild()) ;//遍历有孩子
System.out.print(node.getData() + ",");//输出当前节点的s值
}
}
/**
* 后序遍历非递归算法
* @param node
*/
public void postList2(Node node){
Stack<Node> stack = new Stack<Node>() ;
while(node != null || !stack.isEmpty()){//节点不为空或者栈部位空时进入循环
if(node != null){//将根节点的所有左孩子入栈
stack.push(node) ;
node = node.getLeftChild() ;
}else{
//如果栈顶节点可以访问,canVisit默认为false，不能访问，只有在有孩子也遍历了之后才可以访问父亲节点
if(stack.lastElement().isCanVisit()){
System.out.print(stack.pop().getData() + ",");//出栈，输出结果
}else{//如果栈顶节点不能访问，则遍历节点的有孩子，并设置节点可以访问
node = stack.lastElement().getRightChild() ;//遍历有孩子
stack.lastElement().setCanVisit(true) ;//将父节点设置为可以访问
}
}
}
}
/**
* 查找值data1和data2的第一个祖先节点，返回第一个祖先节点.此处定义了两个栈作为辅助，需要遍历两次二叉树。程序可以大量优化。
* @param root : 从root开始查找
* @param data1 ： 值为data1的节点
* @param data2 : 值为data2的节点
* @return
*/
public Node findNode(Node root , int data1 , int data2) {
Stack<Node> s1 = new Stack<Node>() ;//存放data1的祖先节点
Stack<Node> s2 = new Stack<Node>() ;//存放data2的祖先节点
findParents(s1 , root , data1) ;//将data1的所有祖先节点存放在s1中
this.find = false ;
findParents(s2 , root , data2) ;//将data2的所有祖先节点存放在s2中
Node parent = null ;
while(s1.size()>0 && s2.size()>0 ){//查找第一个祖先节点
if(s1.get(0).getData() == s2.get(0).getData()){
parent = s1.remove(0) ;
s2.remove(0) ;
}else{
break ;
}
}
return parent ;//返回第一个祖先节点
}
/**
* 从root开始查找值为data1的所有祖先节点，并将祖先节点存放在s中
* @param s : 存放祖先节点的栈
* @param root : 开始寻找的及诶单
* @param data ： 寻找节点的值
* @return ： 是否找到值为data1的节点
*/
public boolean findParents(Stack<Node> s , Node root , int data){
if(root != null && !find){
s.push(root) ;//根节点入栈
if(data == root.getData()){
find = true ;//找到了节点
}else{
if(root.getLeftChild() != null){
findParents(s , root.getLeftChild() , data) ;//如果左边找到了
}
if(root.getRightChild() != null){
findParents(s, root.getRightChild() , data) ;
}
if(!find){//如果当前节点的左孩子和有孩子中都没有找到要查找的节点，则当前节点出栈。
s.pop() ;
}
}
}
return find;
}
/**
* 中序遍历递归算法
* @param node
*/
public void midList(Node node){
if(node != null){
midList(node.getLeftChild()) ;
System.out.print(node.getData() + ",");
midList(node.getRightChild()) ;
}
}
/**
* 中序遍历非递归算法
* @param node
*/
public void midList2(Node node){
Stack<Node> stack = new Stack<Node>() ;
while(node != null || !stack.isEmpty()){
if(node != null){
stack.push(node) ;
node = node.getLeftChild() ;
}else{
node = stack.pop() ;
System.out.print(node.getData() + ",");
node = node.getRightChild() ;
}
}
}
/**
* 先序遍历递归算法
* @param node
*/
public void preList(Node node){
if(node != null){
System.out.print(node.getData() + ",");
preList(node.getLeftChild()) ;补充：软件开发 , Java ,
