数据结构：3.3.4遍历应用例子

应用例子一：

改一下先序遍历的程序

例子二：求二叉树的高度

怎么求？树是递归定义的，所以思考求二叉树高度能不能用递归做。

二叉树的高度和左右高度有什么关系？二叉树的高度等于左右子树的最大高度加上一

求树高的前提，要先知道左右子树的高度➡️所以要去改变后序遍历的程序

MaxH=(HL>HR)?HL:HR;

是一个简单的条件表达式，也被称为三元操作符。它的作用是比较HL和HR两个值的大小，如果HL大于HR，则将MaxH赋值为HL，否则将MaxH赋值为HR。换句话说，这段代码选择HL和HR中较大的那个值，并将其赋给MaxH。

**三元操作符（又称条件运算符）是编程语言中的一种简洁的条件判断语法。在C、C++、Java、JavaScript等许多编程语言中，三元操作符使用? :符号来实现。其基本语法结构如下：*

condition ? expression1 : expression2;

其中：

• condition 是一个表达式，它会被计算并返回一个布尔值（true 或 false）。
• expression1 是当 condition 为 true 时将要执行并返回的表达式。
• expression2 是当 condition 为 false 时将要执行并返回的表达式。

三元操作符可以看作是 if-else 语句的一种简写形式。它通常用于需要在一个简单的条件判断中选择两个值之一的场合。

例子三：二元运算表达式树及其遍历（前缀中缀后缀表达式的由来）

叶结点代表运算数，非叶结点是运算符号

注意中序遍历得到的中缀表达式不一定和原来二元运算表达式树想要表达的意思一致

如何解决？

输出左子树的时候先输个左括号，左子树结束的时候再加一个右括号(?有点不懂)，例如要输出a，先输出一个（

例子四：由两种遍历序列确定二叉树

已知三种遍历序列中的任意两种，能否唯一确定一棵二叉树？（只要包含中序就可以）

  

只给了先序和后序，可以得到不止一种符合要求的二叉树

（原因：先序是根左右，后序是左右根，根容易确定，但是不知道左右的边界在哪）

如不懂确定原二叉树的过程，可以参考原视频