package Binary;
public class BinaryTree<T> {
private int i = 0;
public BinaryNode<T> root;
public BinaryTree() {
this.root = null;
}
public BinaryTree(T[] prelist) {
this.root = creat(prelist);
}
private BinaryNode<T> creat(T[] prelist){//先根次序创建二叉树
BinaryNode<T> p = null;
if(i < prelist.length) {
T elem = prelist[i];
i++;
if(elem != null) {
p = new BinaryNode<T>(elem);
p.left = creat(prelist);
p.right = creat(prelist);
}
}
return p;
}
public BinaryNode<T> insert(T x){
return this.root = new BinaryNode<T>(x, this.root, null);
}
public BinaryNode<T> insert(BinaryNode<T> parent, T x, boolean leftChild){
if(x == null)
return null;
if(leftChild)
return parent.left = new BinaryNode<T>(x, parent.left, null);
return parent.right = new BinaryNode<T>(x, null, parent.right);
}
public void remove(BinaryNode<T> parent, boolean leftChild) {
if(leftChild)
parent.left = null;
else parent.right = null;
}
public void clear() {
this.root = null;
}
public void preorder() {//先根次序遍历
preorder(this.root);
System.out.println();
}
private void preorder(BinaryNode<T> p) {
if(p != null) {
System.out.print(p.data.toString() + "");
preorder(p.left);
preorder(p.right);
}
}
public String toString() {
return toString(this.root);
}
private String toString(BinaryNode<T> p) {
if(p == null)
return "^";
return toString(p.left) + "" + p.data.toString() + "" + toString(p.right);
}
public void inorder() {//中根次序遍历
inorder(this.root);
System.out.println();
}
private void inorder(BinaryNode<T> p) {
if(p != null) {
inorder(p.left);
System.out.print(p.data.toString() + "");
inorder(p.right);
}
}
public void postorder() {//后根次序遍历
postorder(this.root);
System.out.println();
}
private void postorder(BinaryNode<T> p){
if(p != null) {
postorder(p.left);
postorder(p.right);
System.out.print(p.data.toString() + "");
}
}
public int size() {//返回二叉树的节点数(递归算法)
return size(this.root);
}
private int size(BinaryNode<T> p) {
if(p == null)
return 0;
return 1 + size(p.left) + size(p.right);
}
public int height() {//返回二叉树的高度(递归算法)
return height(this.root);
}
private int height(BinaryNode<T> p) {
int lh = height(p.left);
int rh = height(p.right);
return (lh >= rh) ? lh+1 : rh+1;
}
public void leaf() {
leaf(this.root);
System.out.println();
}
private void leaf(BinaryNode<T> p) {
if(p != null) {
if(p.left == null && p.right == null) {
System.out.print(p.data);
leaf(p.left);
leaf(p.right);
}
}
}
public void preorderTraverse() {
System.out.print("先根次序遍历(非递归): ");
LinkedStack<BinaryNode<T>> stack = new LinkedStack<BinaryNode<T>>();
BinaryNode<T>p = this.root ;
while(p!=null || !stack.isEmpty())
if(p != null) {
System.out.print(p.data+"");
stack.push(p);
p = p.left;
}
else {
System.out.print("^ ");
p = stack.pop();
p = p.right;
}
System.out.println();
}
public void inorderTraverse() {
System.out.print("中根次序遍历(非递归): ");
LinkedStack<BinaryNode<T>> stack = new LinkedStack<BinaryNode<T>>();
BinaryNode<T>p = this.root;
while(p != null || !stack.isEmpty())
if(p != null) {
stack.push(p);
p = p.left;
}
else {
System.out.print("^ ");
p = stack.pop();
System.out.print(p.data+"");
p = p.right;
}
System.out.println();
}
public void printGenList() {
System.out.print("二叉树的广义表表示: ");
printGenList(this.root);
System.out.println();
}
private void printGenList(BinaryNode<T> p) {
if(p == null)
System.out.print("^");
else {
System.out.print(p.data.toString()+"");
if(p.left != null || p.right != null) {
System.out.print("(");
printGenList(p.left);
System.out.print(",");
printGenList(p.right);
System.out.print(")");
}
}
}
public void postorderTraverse() {
System.out.print("后根次序遍历(栈的非递归): ");
LinkedStack<BinaryNode<T>> stack = new LinkedStack<BinaryNode<T>>();//储存非根节点
BinaryNode<T> p = this.root;
BinaryNode<T> proot ;
int flag;
if(p != null) {
do {
while(p != null) {
stack.push(p);
p = p.left;
}
proot = null;
flag = 1;
while(!stack.isEmpty() && flag==1) {
p = stack.peek();
if(p.right == proot) {
p = stack.pop();
System.out.print(p.data);
proot = p;
}else {
p = p.right;
flag = 0;
}
}
}while(!stack.isEmpty());
}
}
public static void main(String[] args) {
String[] prelist = {"A", "B", "D", null, "G", null, null, null, "C", "E", null, null, "F", "H"};
BinaryTree<String>bitree = new BinaryTree<String>(prelist);
System.out.println(bitree.toString());
bitree.inorderTraverse();
bitree.postorderTraverse();
}
}
没有合适的资源?快使用搜索试试~ 我知道了~
c.zip_java
共2个文件
java:2个
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 177 浏览量
2022-09-20
11:52:01
上传
评论
收藏 2KB ZIP 举报
温馨提示
二叉树以广义表的形式构造,依次由递归、堆栈和父链遍历。
资源推荐
资源详情
资源评论
收起资源包目录
c.zip (2个子文件)
c
BinaryTree.java 5KB
BinaryNode.java 453B
共 2 条
- 1
资源评论
四散
- 粉丝: 54
- 资源: 1万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功