`
hellojyj
  • 浏览: 58408 次
  • 性别: Icon_minigender_1
  • 来自: 长沙
社区版块
存档分类
最新评论

二叉树的建树,先序,中序,后序,层次遍历

阅读更多

 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;
	}
}

 

 

  • 大小: 26.2 KB
分享到:
评论

相关推荐

    二叉树深度+建树+查找+遍历二叉树

    按先序扩展序列建立二叉树 先序、中序、后序遍历的递归算法 中序遍历的非递归算法 先序遍历的非递归算法 后序遍历的非递归算法 层次的非递归算法 求二叉树的深度(后序遍历)

    数据结构 实现二叉排序树的各种算法(1)

    用函数实现如下二叉排序树算法:(1) 插入新结点(2) 前序、中序、后序遍历二叉树(3) 中序遍历的非递归算法(4) 层次遍历二叉树(5) 在二叉树中查找给定关键字(函数返回值为成功1,失败0) Input 第一行:准备...

    PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次)实例详解

    要特别注意的是,二叉树的深度优先遍历比较特殊,可以细分为先序遍历、中序遍历、后序遍历。具体说明如下: 前序遍历:根节点-&gt;左子树-&gt;右子树 中序遍历:左子树-&gt;根节点-&gt;右子树 后序遍历:左子树-&gt;右子树-&gt;根节点 ...

    数据结构 实现二叉排序树的各种算法(2)

    (4) 层次遍历二叉树 (5) 在二叉树中查找给定关键字(函数返回值为成功1,失败0) (6) 交换各结点的左右子树 (7) 求二叉树的深度 (8) 叶子结点数 Input 第一行:准备建树的结点个数n 第二行:输入n个...

    数据结构课设 各种排序

    任务 :编程实现二叉树的建立,先序(递归和非递归方法)、中序、后序、层次遍历,求二叉树的高度; 要求:从文件中读入建树信息,树的节点数目不小于20个,树的高度不小于4; 3、Hash表应用 问题描述:设计散列表...

    数据结构(C++)有关练习题

    2、实现1所要求的代码后,运行设计好的代码,将以下的几组整数序列建成搜索二叉树,并记录下它们的前序遍历序列和后序遍历序列: a. 1、3、5、7、9; b. 1、13、35、13、27; c. 50、25、78、13、44、...

    用c描述的数据结构演示软件

     遍历中序线索二叉树(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...

Global site tag (gtag.js) - Google Analytics