邯郸网站设计费用,免费一键生成短链接,做网红用哪个网站,做小程序的平台二叉树
二叉树#xff08;binary tree#xff09;是一棵树#xff0c;其中每个节点都不能有多于两个的子节点二叉树的一个性质是一颗平均二叉树的深度要比节点个数N小得多#xff08;重点#xff09;#xff0c;对二叉树的分析得出其平均深度为O(N\sqrt NN)#xff0…二叉树
二叉树binary tree是一棵树其中每个节点都不能有多于两个的子节点二叉树的一个性质是一颗平均二叉树的深度要比节点个数N小得多重点对二叉树的分析得出其平均深度为O(N\sqrt NN)而对于特殊类型的二叉树即二叉查找树binary search tree其深度的平均值是O(logN)。不过极端情况如下案例深度可以达到N-1 实现
因为一个二叉树节点最多有两个子节点所有可以保存直接连接到他们的链。树节点的声明在结构上类似双向链表在声明中节点就是element的信息加上两个其他节点的引用left和right组成的结构。
/*** 二叉树节点对象定义** author liaojiamin* Date:Created in 15:24 2020/12/11*/
public class BinaryNode {private Object element;private BinaryNode left;private BinaryNode right;public BinaryNode(Object element, BinaryNode left, BinaryNode right) {this.element element;this.left left;this.right right;}public Object getElement() {return element;}public void setElement(Object element) {this.element element;}public BinaryNode getLeft() {return left;}public void setLeft(BinaryNode left) {this.left left;}public BinaryNode getRight() {return right;}public void setRight(BinaryNode right) {this.right right;}
}我们习惯在画链表的时候使用矩形标识当我们表达树的时候用圆圈并用直线连接因为他实际上是图graph。当涉及树的时候我们也不明显的画出null节点因为具有N个节点的每一个二叉树都需要N1个null节点。二叉树有许多与搜索无关的引用主要的是编译器的设计领域。
案例表达式树
图中线上一个表达式树expression tree的案例表达式树的叶子是操作数如常数或者变量名而其他的节点是操作符。由于所有操作符都是二元的-/因此这棵树正好可以被二叉树标识虽然这是最简单情况当还是可以有可能含有多于两个的子节点。一个节点也有可能只有一个儿子如具有一目减运算符的情形。我们将通过递归计算左子树和右子树所得到的的值应用在根处的运算符而计算出表达式书T的值。在本案例中左子树的值是无需计算只有一个节点1 右子树的值23-45因此整个表达式是12*3-45我们通过递归经过左节点中节点右节点的顺序打印表达式这种遍历方式叫中序遍历另外一种遍历策略递归打印左节点右节点中节点输出为123*4-5这种输出策略称为后顺遍历第三种遍历策略是先打印运算符**中节点然后递归打印左子树右子树**得到的结果1±*2345 这种遍历方式叫前序遍历
构造表达式树
我们先给出一种算法将后缀表达式转表达式树。我们已经有了将中缀表达式转后缀表达式的算法见上一篇因此我们能够从这两常见类型的输入生成表达式树。这里所描述的方法和后缀求职算法相似上一篇流程如下 我们遍历表达式如果是符合操作数数字就建立一个单节点树并推入栈如果没有符合是操作符运算符那么将栈中弹出两个树T1T2T1先出栈将运算符T1T2 组成一个新的数改树根节点是操作符右节点是T1 左节点是T2,将新数重新压入栈 还是按上面的案例1 2 3 * 4 - 5 动图展示整个数构造过程
代码实现
/*** 后缀表达式 转表达式树** author liaojiamin* Date:Created in 15:25 2020/12/11*/
public class PostfixExTOTreeEx {public static BinaryNode toTreeEx(String postfixEx) {MyStackObject number new MyStack();String[] chars postfixEx.split( );for (String s : chars) {if (s.matches(([1-9]\\d*\\.?\\d*)|(0\\.\\d*[1-9]))) {//数字number.push(s);}else if (s.matches((\\*)|(\\/)|(\\)|(\\-))) {if (number.size() 2) {return null;}BinaryNode binaryRight null;Object right number.pop();if(right instanceof BinaryNode){binaryRight (BinaryNode) right;}else {binaryRight new BinaryNode(right, null, null);}BinaryNode binaryLeft null;Object left number.pop();if(left instanceof BinaryNode){binaryLeft (BinaryNode) left;}else {binaryLeft new BinaryNode(left, null, null);}number.push(new BinaryNode(s, binaryLeft, binaryRight));}}return (BinaryNode) number.pop();}/*** 中序遍历* author: liaojiamin* date: 18:15 2020/12/11*/public static void printMiddleFirstTree(BinaryNode binaryNode){if(binaryNode null || binaryNode.getElement() null){return;}printMiddleFirstTree(binaryNode.getLeft());System.out.print(binaryNode.getElement());printMiddleFirstTree(binaryNode.getRight());}/*** 前序遍历* author: liaojiamin* date: 18:15 2020/12/11*/public static void printLeftFirstTree(BinaryNode binaryNode){if(binaryNode null || binaryNode.getElement() null){return;}System.out.print(binaryNode.getElement());printLeftFirstTree(binaryNode.getLeft());printLeftFirstTree(binaryNode.getRight());}/*** 后序遍历* author: liaojiamin* date: 18:15 2020/12/11*/public static void printRightFirstTree(BinaryNode binaryNode){if(binaryNode null || binaryNode.getElement() null){return;}printRightFirstTree(binaryNode.getLeft());printRightFirstTree(binaryNode.getRight());System.out.print(binaryNode.getElement());}public static void main(String[] args) {BinaryNode binaryNode toTreeEx(1 2 3 * 4 - 5 );printMiddleFirstTree(binaryNode);System.out.println();printLeftFirstTree(binaryNode);System.out.println();printRightFirstTree(binaryNode);}}上一篇数据结构与算法–链表实现以及应用 下一篇数据结构与算法–重建二叉树
