- 浏览: 18283 次
- 性别:
- 来自: 湖南常德
最新评论
一、数的相关
节点: 节点是树的基本组成单位,它由数据域和指向其他节点的指针
度: 节点拥有子节点的个数称为该节点的度。
叶子节点:叶子节点是树的终端节点,其度为0。
高度: 树种节点的最大层次称为树的高对(或者叫深度)。
根节点:
二叉树: 二叉树是树的一种,其特点是每个节点至多只有两颗子树(即
于2的节点),并且二叉树的子树有左右之分,其次序不能随意颠倒。
二叉树的遍历:二叉树有四种遍历次序,先序遍历,终须遍历,后序遍历
例如,一下面的树为例
先序遍历:
步骤:
若二叉树不为空,则
访问根节点;
先序遍历左子树;
先序遍历右子树;
则下面的树的先序遍历顺序为:ABDECFG
中序遍历:
步骤:
若二叉树不为空,则
中序遍历左子树;
访问根节点;
中序遍历右子树;
则下面的树的中序遍历为:DBEAFCG
后序遍历:
步骤:
若二叉树不为空,则
后序遍历左子树;
后序遍历右子树;
访问根节点;
则下面的树的后序遍历为:DEBFGCA
A
/ \
B C
/\ /\
D E F G
例如,在上面的树,A是根节点(root),D,E,F,G则是叶子节点B,C是A的子节点,是D,E,F,G
的父节点,D,E,F,G则是兄弟节点。我们在定义树的节点之间的关系时与链表相似,同样是用类封装。
public class BinaryTree { private BinaryTree root;// 二叉树的根 private BinaryTree lchild;// 定义二叉树的左子树 private BinaryTree rchild;// 定义二叉树的右子树 private BinaryTree parent;// 定义二叉树的父节点 private Object data;// 传入的数据类型 /** * * data:传入的初始数据类型 */ public BinaryTree(String data) { this.data = data; } /** * 返回数据 */ public Object getData() { return data; } /** * 设置根节点 */ public void setRoot(BinaryTree root) { this.root = root; } /** * 返回根节点 */ public BinaryTree getRoot() { return root; } /** * 设置父节点 */ public void setParent(BinaryTree parent) { this.parent = parent; } /** * 返回父节点 */ public BinaryTree getParent() { return parent; } /** * 设置左子节点 */ public void setLChild(BinaryTree lchild) { this.lchild = lchild; } /** * 返回左子节点 */ public BinaryTree getLChild() { return lchild; } /** * 设置右子节点 */ public void setRChild(BinaryTree rchild) { this.rchild = rchild; } /** * 返回右子节点 */ public BinaryTree getRChild() { return rchild; } }
定义好以后我们就可以创建一颗二叉树了我们使用表达式2*10-8/(2+2)
/** * 创建二叉树 */ public void creatTree() { BinaryTree biNode_1 = new BinaryTree("-"); BinaryTree biNode_2 = new BinaryTree("*"); BinaryTree biNode_3 = new BinaryTree("/"); BinaryTree biNode_4 = new BinaryTree("2"); BinaryTree biNode_5 = new BinaryTree("10"); BinaryTree biNode_6 = new BinaryTree("8"); BinaryTree biNode_7 = new BinaryTree("+"); BinaryTree biNode_8 = new BinaryTree("2"); BinaryTree biNode_9 = new BinaryTree("2"); root = biNode_1;// 根节点 // 根节点的左右子树 biNode_1.setLChild(biNode_2); biNode_1.setRChild(biNode_3); biNode_2.setLChild(biNode_4); biNode_2.setRChild(biNode_5); biNode_4.setLChild(null); biNode_4.setRChild(null); biNode_5.setLChild(null); biNode_5.setRChild(null); biNode_3.setLChild(biNode_6); biNode_3.setRChild(biNode_7); biNode_6.setLChild(null); biNode_6.setRChild(null); biNode_7.setLChild(biNode_8); biNode_7.setRChild(biNode_9); biNode_8.setLChild(null); biNode_8.setRChild(null); }
设置好所有的左右子树,接下来我们遍历我们建立的这颗二叉树
/** *中序遍历二叉树 */ public void inorderTraversal(BinaryTree r) { if (null != r) { traverse_1(r.getLChild()); System.out.print(r.getData()); traverse_1(r.getRChild()); } }
则打印出来的结果将会是2*10-8/2+2,如果还想算出结果的话,我们首先判断该节点是否有子节点,如果没有那我们确定该节点是数字,我们String类型强转成int行返回,再进行判断如果有子节点,那我们遍历左子树,遍历右子树,获取返回值,根据该节点的运算符号对获取的左右子树进行运算,然后返回结果。那么我们递归到最后就能得到表达式的结果
** * 计算表达式结果 */ public int inorder(BinaryTree t) { // 判断是否是叶子节点 if (null == t.getLChild() && null == t.getRChild()) { return Integer.parseInt((String) t.getData()); } else { inorder(t.getLChild()); // System.out.print(t.getData()); inorder(t.getRChild()); // 获取返回的节点值 int a = inorder(t.getLChild()); int b = inorder(t.getRChild()); if (t.getData().equals("*")) { return a * b; } else if (t.getData().equals("+")) { return a + b; } else if (t.getData().equals("-")) { return a - b; } else if (t.getData().equals("/")) { return a / b; } } return 0; }
发表评论
-
git入门
2015-02-11 11:02 0git入门 -
JVM内存结构浅谈
2013-05-19 14:47 656Java程序的运行过程: ... -
菜鸟入门之网页数据抓取
2013-05-04 21:53 5522有时候需要从网页上获取数据,比如别一些网页上的新闻获取到放 ... -
动态编译
2013-03-01 22:33 581前几天谈论了关于动 ... -
位映射
2013-03-01 22:33 915前些天讨论了位映射的内容,一个具体的例子就对于M个int ... -
线程同步
2013-03-01 22:34 7131,为什么要有线程同 ... -
生产消费模型
2013-03-01 22:34 677当遇到一个线程要产生数据而另一个线程要处理数据时,这就是生 ... -
设计模式之单例模式
2012-12-02 23:02 0单例模式又叫单台模式或者单例模式 -
数据结构之Hash
2012-11-19 21:45 858数据结构之hash 首先介绍两种非常重要的数据结构。数组,为 ... -
数据结构之Hash
2012-11-18 14:47 0数据结构之hash 首先介 ... -
网络通信总结
2012-10-28 15:33 815网络通信:一句话说,用网络传输数据(各种数据) 。进行通讯那 ... -
哈弗曼压缩
2012-08-03 11:43 666一、哈弗曼树,又称最优树,是一种带权路径长度最短的树。 ... -
链表总结
2012-08-03 11:43 783首先,链表是一种顺 ... -
线程及线程应用总结
2012-08-03 11:44 729一、什么是线程 每个java程序都至少有一个线程 ... -
java集合框架
2012-07-16 21:21 722java集合框架总结 主要由以下三部分组成: ... -
I/O体系结构总结
2012-07-16 21:22 881I/O体系结构总结 流的概念和分类: ... -
File相关类总结
2012-07-16 21:22 891File是java中的与文件相关的类,可以对进行创建、删 ... -
java异常机制
2012-07-11 13:01 689JAVA异常机制 一、异常的基本概念 简单的说 ... -
总结20120705
2012-07-05 10:07 649一、类与对象 1. ... -
java关键字总结
2012-05-20 13:31 705常用关键字: 访问修饰符关键字: public: 是最为公 ...
相关推荐
树与二叉树的详细算法,很全 以二叉树表示算术表达式 建立二叉树算法 以及一些习题
二叉树面试题 树和二叉树考研试题总结
数据结构之树与二叉树算法总结,数据结构之树与二叉树算法总结 数据结构
二叉树总结
自己根据资料对二叉搜索树,B树,红黑树等的基本梳理和总结,一张脑图就能理解,费了一些功夫弄出来的,手里没多少分的就不要下了
2. 在有n个叶子结点的哈夫曼树中,总结点数是2n-1。 3. 在有n个结点的二叉链表中,值为非空的链域的个数为 n+1。 4. 某二叉树的中序遍历序列和后序遍历序列正好相反,则该二叉树一定是高度等于其结点数的二叉树。
通过本次实验,我基本掌握了二叉树的存储实现和二叉树的遍历思想, 并且实现了二叉树的几种常见算法。
2. 在有n个叶子结点的哈夫曼树中,总结点数是 2n-1 。 3. 在有n个结点的二叉链表中,值为非空的链域的个数为 n-1 。 4. 某二叉树的中序遍历序列和后序遍历序列正好相反,则该二叉树一定是 任一结点无左孩子 的二叉树...
题 目 二叉排序树与平衡二叉树的实现 1、课程设计的目的 使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法,以及它们在程序中的使用方法。 使学生掌握软件设计的基本内容...
实现了二叉树的前中后遍历,以及层次遍历,求出了二叉树的深度,叶子个数。 实验报告还包含目录,所有遍历方法的解释,以及结果展示和结论改进
408考试二叉树习题答案. 主要有递归和非递归二种写法.
//实现二叉树总结点数的求值 int LeafNodeNum(BSTree T); //实现二叉树叶子结点数的求值 Status DeleteBST(BSTree &T,ElemType e); //实现树的节点的删除 int TreeHeight(BSTree T); //实现树的高度的求值 int ...
1. 按先序次序建立一个二叉树 ,用#表示某结点的左右子树是否为空,用于表示该结点是否为叶子或者可能存在左子树or右子树。例如对一个简单的三节点二叉树,节点b和c分别为根节点a的左孩子和右孩子,用先序来创建就...
C语言版数据结构中二叉树的查找算法,对学习数据结构的新手有帮助。
实验总结和体会 实现的基本操作如下: InitBiTree(&T) DestroyBiTree(&T) CreateBiTree(&T) ClearBiTree(&T) BiTreeEmpty(T) BiTreeDepth(T) Root(T) Value(T,e) Assign(T,&e,value) Parent(T,e) LeftChild(T,e) ...
树与二叉树的叶子节点的计算与总结点之间的关系。
本文总结了二叉树的常见操作:二叉树的构建,查找,删除,二叉树的遍历(包括前序遍历、中序遍历、后序遍历、层次遍历),二叉搜索树的构造等。 1. 二叉树的构建 二叉树的基本构建方式为:添加一个节点,如果这是一棵...
二叉树遍历问题 ⼀、⼆叉树的重要性 很多经典算法如 回溯、⼴度优先遍历、分治、动态规划等通常需要转化为树的问题,⽽树的题⽬难免涉及到递归的问题,因此掌握树的三 种遍历框架是必须的。 先序遍历:根,左,右 ...
并含递归和非递归方式等的算法、求二叉树的深度、删除二叉树中以某个结点为根结点的子树、判别两棵树是否相等和是否是完全二叉树、二叉排序树的构造、查找和插入等等算法、孩子兄弟表示法的构造等算法。(含真题) ...
二叉树三种遍历算法的源码背诵版...希望对大家有用