/**
* 二叉树的链表节点类
* @author qiangzi
* @param <T>
*/
public class BinaryNode<T> {
public T data; //数据域
public BinaryNode<T> left,right; //链域，分别只向左右孩子
public BinaryNode(T data, BinaryNode<T> left, BinaryNode<T> right) {
this.data = data;
this.left = left;
this.right = right;
}
public BinaryNode(T data){
this(data, null, null);
}
public BinaryNode(){
this(null,null,null);
}
}
package com.hzq.test;
public class BinaryTree<T>{
public BinaryNode<T> root; // 根节点，节点结构为二叉链表
public BinaryTree(){
this.root = null;//构造空二叉树
}
public boolean isEmpty(){
return this.root == null;
}
//先跟次序遍历二叉树
public void preOrder(){
System.out.println(“先根次序遍历二叉树”);
preOrder(root);
System.out.println();
}
public void preOrder(BinaryNode<T> p) {
if (p != null) {
System.out.print(p.data.toString() + ” “); // 访问当前节点
preOrder(p.left); // 按先根次序遍历当前节点的左子树，递归调用
preOrder(p.right);// 按先根次序遍历当前节点的右子树，递归调用
}
}
//中根次序遍历二叉树
public void inOrder(){
System.out.println(“中根次序遍历二叉树”);
inOrder(root);
System.out.println();
}
public void inOrder(BinaryNode<T> p){
if(p!=null){
inOrder(p.left);
System.out.print(p.data.toString()+” “);
inOrder(p.right);
}
}
//后根次序遍历二叉树
public void postOrder(){
System.out.println(“后根次序遍历二叉树”);
postOrder(root);
System.out.println();
}
public void postOrder(BinaryNode<T> p) {
if(p!=null){
postOrder(p.left);
postOrder(p.right);
System.out.print(p.data.toString()+” “);
}
}
//求节点个数
public int count(){
return count(root);
}
private int count(BinaryNode<T> p) {
if(p==null){
return 0;
}
return 1+count(p.left)+count(p.right);
}
//求高度
public int height(){
return height(root);
}
private int height(BinaryNode<T> p) {
if(p== null){
return 0;
}
int lh = height(p.left);
int rh = height(p.right);
return (lh>=rh)?lh+1:rh+1;
}
//查找
public BinaryNode<T> search(T key){
return this.search(root,key);
}
private BinaryNode<T> search(BinaryNode<T> p, T key) {
if(p == null || key == null){
return null;
}
if(p.data.equals(key)){
return p;
}
BinaryNode<T> find = search(p.left, key);
if(find == null){
find = search(p.right,key);
}
return find;
}
//获取父节点
public BinaryNode<T> getParent(BinaryNode<T> node){
if(root == null || node == null || root == node){
return null;
}
return getParent(root,node);
}
private BinaryNode<T> getParent(BinaryNode<T> p, BinaryNode<T> node) {
if(p == null){
return null;
}
if(p.left == node || p.right == node){
return p;
}
BinaryNode<T> find = getParent(p.left,node);
if(find == null){
find = getParent(p.right,node);
}
return find;
}
//二叉树的插入与删除
//插入
public void insertBinary(T x){
root = new BinaryNode<T>(x,root,null);
}
//插入元素X作为p节点的孩子，若leftChild为true，插入节点为左孩子，否则为右孩子
public BinaryNode<T> insertBinary(BinaryNode<T> p,T x,boolean leftChild){
if(p == null || x == null){
return null;
}
if(leftChild){
p.left = new BinaryNode<T>(x,p.left,null);
return p.left;
}
p.right = new BinaryNode<T>(x,null,p.right);
return p.right;
}
//删除
public void removeAll(){
this.root = null;
}
public void removeChild(BinaryNode<T> p,boolean leftChild){
if(p!=null){
if(leftChild){
p.left = null;
}else{
p.right = null;
}
}
}
}
package com.hzq.test;
public class BinaryTreeClient {
public static void main(String[] args) {
BinaryTree<String> bitree = make();
bitree.preOrder();
bitree.inOrder();
bitree.postOrder();
System.out.println(bitree.count());
System.out.println(bitree.height());
System.out.println(bitree.search(“E”));
}
/**
* 构造一颗二叉树
* @return
*/
public static BinaryTree<String> make(){
BinaryTree<String> bitree = new BinaryTree<String>();
BinaryNode<String> child_f,child_d,child_b,child_c;
child_d = new BinaryNode<String>(“D”,null,new BinaryNode<String>(“G”));
child_b = new BinaryNode<String>(“B”,child_d,null);
child_f = new BinaryNode<String>(“F”,new BinaryNode<String>(“H”),null);
child_c = new BinaryNode<String>(“C”,new BinaryNode<String>(“E”),child_f);
bitree.root = new BinaryNode<String>(“A”,child_b,child_c);
return bitree;
}
}