怎么用java先序创建二叉树?(说的详细些)
[align=center]先序是个什么概念?二叉树又是个什么概念?
怎么用先序来创建二叉树???[/align]
[最优解释]
递归方法前序遍历
public class BinaryTree<E>{//二叉树类
public BinaryNode<E> root;//根结点
public E data;//数据元素
public BinaryNode<E> left,right;//分别指向左、右孩子的结点
public BinaryTree(){//构造空二叉树
this.root = null;
}
public BinaryTree(BinaryNode<E> root){//构造指定根结点的二叉树
this.root = root;
}
public boolean isEmpty(){//判断是否是空二叉树
return this.root == null;
}
public BinaryNode<E> getRoot(){//返回二叉树的根结点
return this.root;
}
//三种次序遍历的成员方法
public void preOrder(){//先根次序遍历二叉树
System.out.print("\n先根序列: ");
preOrder(root);
}
private void preOrder(BinaryNode<E> p){//先根次序遍历以p结点为根的子树
if(p != null){//若二叉树不空
System.out.print(p.data + " ");//访问当前结点
preOrder(p.left);//访问根次序遍历当前结点的左子树
preOrder(p.right);//访问根次序遍历当前结点的右子树
}
}
//非递归方法中序遍历二叉树
public void inOrder(){
System.out.print("\n中根序列(非递归): ");
LinkedStack<BinaryNode<E>> stack = new LinkedStack<BinaryNode<E>>();
BinaryNode<E> p = this.root;
while(p != null
[其他解释]
!stack.isEmpty()){//p非空或栈非空时
if(p != null){
stack.push(p);//p结点入栈
p = p.left;//进入左子树
}else{
p = stack.pop();//p指向出栈结点
System.out.print(p.data + " ");
p = p.right;//进入右子树
}
}
}
/**
*递归方法中序二叉树遍历
* public void inOrder(){//中根次序遍历二叉树
*
*System.out.print("\n中根序列: ");
*inOrder(root);
* }
*
* private void inOrder(BinaryNode<E> p){//中根次序遍历以p结点为根的子树
*
*if(p != null){//若二叉树不空
*
* inOrder(p.left);//访问根次序遍历当前结点的左子树
* System.out.print(p.data + " ");//访问当前结点
* inOrder(p.right);//访问根次序遍历当前结点的右子树
* }
* }
*/
public void postOrder(){//后根次序遍历二叉树
System.out.print("\n后根序列: ");
postOrder(root);
}
private void postOrder(BinaryNode<E> p){//后根次序遍历以p结点为根的子树
if(p != null){//若二叉树不空
postOrder(p.left);//访问根次序遍历当前结点的左子树
postOrder(p.right);//访问根次序遍历当前结点的右子树
System.out.print(p.data + " ");//访问当前结点
}
}
//求结点个数
public int count(){//返回二叉树的结点个数
return count(root);
}
private int count(BinaryNode<E> p){//返回以p结点为根的子树的结点个数
if(p != null)
return 1 + count(p.left) + count(p.right);
else
return 0;
}
//求高度
public int height(){//返回二叉树的高度
return height(root);
}
private int height(BinaryNode<E> p){//返回以p结点为根的子树高度,后根次序遍历
if(p != null){
int ld = height(p.left);//返回左子树的高度
int rd = height(p.right);//返回右子树的高度
return (ld >= rd) ? ld+1 : rd+1;//当前子树的高度为较高子树的高度加1
}else
return 0;
}
//获得父母结点
public BinaryNode<E> getParent(BinaryNode<E> node){//返回node的父母结点,若为空树、未找到或node为根,返回null
if((root == null)
[其他解释]
(node == root))
return null;
else
return getParent(root,node);
}
private BinaryNode<E> getParent(BinaryNode<E> p,BinaryNode<E> node){//在以p为根结点的子树中查找并返回node结点的父母结点
BinaryNode<E> find = null;
if(p != null){
if(p.left == node
[其他解释]
数据结构里面的哈!
[其他解释]
汗,楼主这个题问的强悍!光是二叉树就可以跟你说上个大半天的了,你说在帖子里怎么回?
[其他解释]
(node == null)
[其他解释]
p.right == null)
find = p;//查找成功
else{
find = getParent(p.left,node);//在左子树中查找
if(find == null)
find = getParent(p.right,node);//若左子树中未找到,则继续在右子树中查找
}
}
return find;//返回找到的父母结点
}
//获得左、右孩子
public BinaryNode<E> getLChild(BinaryNode<E> node){//返回node的左孩子,若为空树、未找到或node为叶子,返回null
if((root == null)
[其他解释]
(node == null)
------其他解决方案--------------------
(node.left == null)