PS:输入测试数据时候采用先序遍历的方式用#作为分隔符来输入,例如:此二叉树
用这种方式输入ABC##DE#G##F###
package cn.jinyejun.experiment_Tree; public class BNode{ int data; BNode lchild; BNode rchild; }
package cn.jinyejun.experiment_Tree; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; import java.util.Stack; public class BinTree { static int index = 0; static class Info { int numOfNode = 0; int degree_1 = 0; int degree_2 = 0; int numOflNode = 0; int maxData; int minData; } public static void main(String[] args) { Scanner cin = new Scanner(System.in); String toBuild = cin.nextLine(); BNode bd = buildTree(toBuild); System.out.print("先序遍历: "); preOrder(bd); System.out.println(); System.out.print("中序遍历: "); inOrder(bd); System.out.println(); System.out.print("后序遍历: "); postOrder(bd); System.out.println(); Info info = Non_recursive(bd); System.out.println("二叉树节点数: " + info.numOfNode + " 度为1节点数 :" + info.degree_1 + " 度为2节点数:" + info.degree_2 + " 叶节点数: " + info.numOflNode + " 最大数据 :" + info.maxData + " 最小数据: " + info.minData); System.out.print("层次遍历: "); levOrder(bd); System.out.println(); } // 建二叉树(采用先序的算法建树) public static BNode buildTree(String str) { BNode bd; char ch = str.charAt(index++); if (ch == '#') { return null; } else { bd = new BNode(); bd.data = (int)ch-48; bd.lchild = buildTree(str); bd.rchild = buildTree(str); return bd; } } // 先序遍历 public static void preOrder(BNode bd) { if (bd != null) { System.out.print(bd.data + " "); preOrder(bd.lchild); preOrder(bd.rchild); } } // 中序遍历 public static void inOrder(BNode bd) { if (bd != null) { inOrder(bd.lchild); System.out.print(bd.data + " "); inOrder(bd.rchild); } } // 后续遍历 public static void postOrder(BNode bd) { if (bd != null) { postOrder(bd.lchild); postOrder(bd.rchild); System.out.print(bd.data + " "); } } //层次遍历 public static void levOrder(BNode bd){ Queue<BNode> queue = new LinkedList<BNode>(); BNode tempbd; if(bd !=null){ queue.offer(bd); } while(!queue.isEmpty()){ tempbd = queue.poll(); System.out.print(tempbd.data+" "); if(tempbd.lchild!=null){ queue.offer(tempbd.lchild); } if(tempbd.rchild!=null){ queue.offer(tempbd.rchild); } } } // 非递归统计二叉树的节点个数、度为1、度为2和叶子节点的个数,以及数据值的最大值和最小值 public static Info Non_recursive(BNode bd) { Stack<BNode> st = new Stack<BNode>(); Info info = new Info(); BNode tempBd; int degree; //初始化最大值最小值 if (bd != null) { st.push(bd); info.maxData = bd.data; info.minData = bd.data; info.numOfNode++; } while (!st.isEmpty()) { //每次遍历节点计算度 degree = 0; tempBd = st.pop(); info.maxData = (tempBd.data > info.maxData) ? tempBd.data : info.maxData; info.minData = (tempBd.data < info.minData) ? tempBd.data : info.minData; if (tempBd.rchild != null) { st.push(tempBd.rchild); info.numOfNode++; degree++; } if (tempBd.lchild != null) { st.push(tempBd.lchild); info.numOfNode++; degree++; } //如果度为0,说明就是叶节点,如果为1或2统计度为1或2的节点数 switch (degree) { case 0: info.numOflNode++; break; case 1: info.degree_1++; break; case 2: info.degree_2++; break; } } return info; } }
相关推荐
按先序扩展序列建立二叉树 先序、中序、后序遍历的递归算法 中序遍历的非递归算法 先序遍历的非递归算法 后序遍历的非递归算法 层次的非递归算法 求二叉树的深度(后序遍历)
用函数实现如下二叉排序树算法:(1) 插入新结点(2) 前序、中序、后序遍历二叉树(3) 中序遍历的非递归算法(4) 层次遍历二叉树(5) 在二叉树中查找给定关键字(函数返回值为成功1,失败0) Input 第一行:准备...
要特别注意的是,二叉树的深度优先遍历比较特殊,可以细分为先序遍历、中序遍历、后序遍历。具体说明如下: 前序遍历:根节点->左子树->右子树 中序遍历:左子树->根节点->右子树 后序遍历:左子树->右子树->根节点 ...
(4) 层次遍历二叉树 (5) 在二叉树中查找给定关键字(函数返回值为成功1,失败0) (6) 交换各结点的左右子树 (7) 求二叉树的深度 (8) 叶子结点数 Input 第一行:准备建树的结点个数n 第二行:输入n个...
任务 :编程实现二叉树的建立,先序(递归和非递归方法)、中序、后序、层次遍历,求二叉树的高度; 要求:从文件中读入建树信息,树的节点数目不小于20个,树的高度不小于4; 3、Hash表应用 问题描述:设计散列表...
2、实现1所要求的代码后,运行设计好的代码,将以下的几组整数序列建成搜索二叉树,并记录下它们的前序遍历序列和后序遍历序列: a. 1、3、5、7、9; b. 1、13、35、13、27; c. 50、25、78、13、44、...
遍历中序线索二叉树(Inorder_thlinked) 中序线索树的插入(ins_lchild_inthr)和删除(del_lchild_inthr)结点 (4)建赫夫曼树和求赫夫曼编码(HuffmanCoding) (5)森林转化成二叉树(Forest2BT) (6)二叉树...
遍历中序线索二叉树(Inorder_thlinked) 中序线索树的插入(ins_lchild_inthr)和删除(del_lchild_inthr)结点 (4)建赫夫曼树和求赫夫曼编码(HuffmanCoding) (5)森林转化成二叉树(Forest2BT) (6)二叉树...
任务 :编程实现二叉树的建立,层次遍历,(递归和非递归方法)先序、中序、后序,二叉树的高度、宽度。二叉排序树的建立、插入、删除; 基本要求:从文件中读入建树信息,树的节点数目不小于20个,树的高度不小于5...