package other;
import java.util.Stack;
class TreeNode {
private String key;
private TreeNode lchild; //左孩子
private TreeNode rchild; //右孩子
private TreeNode parent; //双亲节点
public TreeNode(String key) {
this.key = key;
}
public String getKey() {
return key;
}
public void setKey(String key) {
this.key = key;
}
public TreeNode getLchild() {
return lchild;
}
public void setLchild(TreeNode lchild) {
this.lchild = lchild;
}
public TreeNode getRchild() {
return rchild;
}
public void setRchild(TreeNode rchild) {
this.rchild = rchild;
}
public TreeNode getParent() {
return parent;
}
public void setParent(TreeNode parent) {
this.parent = parent;
}
public String toString() { // 打印出树种某个节点的信息
StringBuffer sb = new StringBuffer();
sb.append("key:" + this.key + " ");
if (this.getLchild() != null) {
sb.append(" left child:" + this.getLchild().getKey());
}
if (this.getRchild() != null) {
sb.append(" right child:" + this.getRchild().getKey());
}
return sb.toString();
}
}
public class TreeTest {
private static Stack<TreeNode> s;
private static TreeNode root;
public static TreeNode createTree(){
root = new TreeNode("6");
TreeNode l = new TreeNode("3");
TreeNode r = new TreeNode("8");
l.setParent(root);
r.setParent(root);
TreeNode ll = new TreeNode("2");
TreeNode rl = new TreeNode("7");
l.setLchild(ll);
r.setLchild(rl);
ll.setParent(l);
rl.setParent(r);
root.setLchild(l);
root.setRchild(r);
root.setParent(null);
return root;
}
public static void main(String[] args) {
// 简单的构造一个树,当然是先构造树上的每一个节点
root = createTree();
System.out.println(treeDepth(root));
// preOrderTraverse(root); // 递归先序遍历树
//
//
// //
// TreeNode finded = treeSearchTranverse(root, "6"); // 查找树中的某个key是否存在
// System.out.println(finded);
//
// TreeNode finded2 = treeSearchTranverse(root, "6"); // 查找树中的某个key是否存在
// System.out.println(finded2);
// inOrderNonTraverse(root);
}
// 递归先序遍历二叉树,后序和中序相似,只是调换输出子树根节点的次序
public static void preOrderTraverse(TreeNode t) {
System.out.println("递归先序遍历");
if (t != null) {
System.out.println(t.getKey());
preOrderTraverse(t.getLchild());
preOrderTraverse(t.getRchild());
}
}
public static void inOrderNonTraverse(TreeNode t) { // 中序遍历二叉树的非递归
s = new Stack<TreeNode>();
s.clear();
s.push(t);// 根节点入栈
while (!s.isEmpty()) {
while (!s.isEmpty()&&s.peek()!= null)
s.push(s.peek().getLchild());// 向左走到尽头
s.pop();//空指针退栈,别忘了
if (!s.isEmpty()) {
TreeNode current = s.pop();
System.out.println(current.getKey());
s.push(current.getRchild());
}
}
}
// 二叉查找树,必须满足左子树的关键字小于等于根,右子树的节点大于等于根,这样中序遍历该树,可得到一个有序序列
/*
* 在二叉查找树上找关键字为key的节点,递归方法
*/
public static TreeNode treeSearchTranverse(TreeNode root, String key) {
if (root == null || root.getKey().equals(key))
return root;
if (root.getKey().compareTo(key) > 0) { // 小于根节点的关键字,肯定在左子树上
return treeSearchTranverse(root.getLchild(), key);
} else {
return treeSearchTranverse(root.getRchild(), key);
}
}
/*
* 在二叉查找树上找关键字为key的节点,非递归方法
*/
public static TreeNode treeSearchNonTranverse(TreeNode root, String key) {
while (root != null && !root.getKey().equals(key)) {
if (key.compareTo(root.getKey()) < 0) {
root = root.getLchild(); // 指向左孩子
} else {
root = root.getRchild();
}
}
return root;
}
/*
* 返回查找树中的最小关键字,只需一直沿着节点的left指针即可
*/
public static TreeNode TreeMin(TreeNode x) {
while (x.getLchild() != null) {
x = x.getLchild();
}
return x;
}
/*
* 返回查找树中的最大关键字,只需一直沿着节点的right指针即可
*/
public static TreeNode TreeMax(TreeNode x) {
while (x.getRchild() != null) {
x = x.getRchild();
}
return x;
}
/*
* 返回中序遍历查找树时节点x的后继,无需对关键字进行比较,因为二叉查找树的结构,x的后继就是具有大于x.getKey()的关键字中最小者的那个节点
*/
public static TreeNode TreeSuccessor(TreeNode x) {
if (x.getRchild() != null) //根据中序遍历
return TreeMin(x.getRchild());
TreeNode y = x.getParent();
while(y!=null&&x==y.getRchild()){ //x是y的右孩子或x是根节点???
x=y;
y=y.getParent();
}
return y; //x是y的左孩子
}
/*
* 在二叉查找树中插入一个节点z,使之仍然保持查找树的特性???????????不懂,指针x跟踪路径,从根节点开始,下降,而y始终指向x的父节点。
*/
public static void insertNode(TreeNode z){
TreeNode y =null;
TreeNode x = getRoot(); //根的父节点为空
while(x!=null){
y=x;
if(z.getKey().compareTo(x.getKey())<0) x=x.getLchild();
else x=x.getRchild();
}
z.setParent(y); //插入的z节点的双亲节点
if(y==null){
setRoot(z);//当前树为空树,设置根节点
}
else if(z.getKey().compareTo(y.getKey())<0){
y.setLchild(z);
}
else y.setRchild(z);
}
public static TreeNode getRoot() {
return root;
}
public static void setRoot(TreeNode root) {
TreeTest.root = root;
}
/*
* 在二叉查找树中删除一个节点z,使之仍然保持查找树的特性
*/
public static TreeNode deleteNode(TreeNode z){
TreeNode x,y;
if(z.getLchild()==null||z.getRchild()==null){
y=z;
}
else y = TreeSuccessor(z);
if(y.getLchild()!=null){
x=y.getLchild();
}
else x = y.getRchild();
if(x!=null){
x.setParent(y.getParent());
}
if(y.getParent()==null){
setRoot(x);
}
else if(y==y.getParent().getLchild()){
y.getParent().setLchild(x);
}
else{
y.getParent().setRchild(x);
}
if(y!=z){
z.setKey(y.getKey());
}
return y;
}
public static int treeDepth(TreeNode t){ //计算树的深度
TreeNode lchild,rchild;
int lchildDepth,rchildDepth;
if(t==null) return 0;
else {
System.out.println("树节点不为空时:");
lchild = t.getLchild();
rchild = t.getRchild();
lchildDepth = treeDepth(lchild);
rchildDepth = treeDepth(rchild);
return lchildDepth>rchildDepth?(lchildDepth+1):(rchildDepth+1);
}
}
}
分享到:
相关推荐
二叉树基本操作java实现,递归与非递归实现三种遍历顺序,对应的我的博客地址是: http://blog.csdn.net/u012320459/article/details/48025767#t8
平衡二叉树Java实现,平衡二叉树Java实现,平衡二叉树Java实现,平衡二叉树Java实现,
代码实现: 二叉树的查找、插入、删除和输出根节点到当前节点的路径 二叉树的前序遍历,中序遍历和后续遍历 TreeNode.java --定义树节点 Mytree.java----创建树结构和上述功能函数 TestTree.java --测试上述的功能
java二叉树实现 (简单实现,入门用) /**创建二叉树*/ public BinaryTree createTree(String treeStr); /**寻找结点*/ public BinaryTree findNode(BinaryTree tree ,char sign); /**找所给结点的左子树*/ ...
java实现二叉树非递归前序中序后序遍历
java使用jtree动态实现二叉树,包含二叉树的插入删除很查找
用java实现二叉树遍历 包括先序,中序,后序 后续是自己写的算法 可以运行
数据结构二叉树专题java代码实现
编程实现如下功能: 1、假设二叉树的结点值是字符,根据输入的一颗二叉树的标明了空子树的完整先根遍历序列,建立一棵以二叉链表表示的二叉树。 2、对二叉树进行先根、中根和后根遍历操作,并输出遍历序列,同时观察...
数据结构二叉树(Binary Tree)的Java实现; 包括最基本的清空方法/判断为空方法/求树的深度的方法/获得父结点的方法/获得左/右兄弟结点的方法/递归先序/中序/后序遍历二叉树的方法;
使用教程:http://blog.csdn.net/z740852294/article/details/78250911
文档中是我自己实现的用java语言实现(1)判断给定的二叉树是否平衡;(2)二叉树插入新数据后,如果失衡自我旋转调整的方法。
Java实现二叉树,Java实现队列.pdf
1:构造一个二叉树 2:二叉树前序遍历(递归) 3:二叉树中序遍历(递归) 4:二叉树后续遍历(递归) 5:二叉树前序遍历(非递归) 6:二叉树中序遍历(非递归) 7:二叉树后序遍历(非递归)
内容涵盖二叉树的各种操作 包括新建二叉树后以多种方式输出 插入结点 删除结点等等
Java实现二叉树的基本操作