山东建设信息网站,网络营销培训课件,南京溧水城市建设集团网站,网站建设的相关知识目录
层序遍历
思路图解
代码实现
二叉树遍历的应用 输出二叉树中的叶节点
代码实现
求二叉树的高度
思路图解
代码实现 二元运算表达式树及其遍历
由两种遍历序列确定二叉树 层序遍历
层序遍历可以通过一个队列来实现#xff0c;其基本过程为#xff1a;
先根…目录
层序遍历
思路图解
代码实现
二叉树遍历的应用 输出二叉树中的叶节点
代码实现
求二叉树的高度
思路图解
代码实现 二元运算表达式树及其遍历
由两种遍历序列确定二叉树 层序遍历
层序遍历可以通过一个队列来实现其基本过程为
先根节点入队然后
从队列中取出一个元素访问该元素所指的节点若该元素所指节点的左、右孩子节点非空 则将其左、右孩子的指针顺序入队。循环123的步骤直到队列为空。
思路图解 代码实现
void LevelOrderTraversal(BinTree BT)
{Queue Q;BinTree T;if (!BT){return; //若为空树则直接返回}Q CreateQueue(); //创建并初始化队列QAdd(Q, BT);while (!IsEmptyQ(Q)){T DeleteQ(Q);printf(%d\n, T-data); //访问取出来的节点//若该元素的左右孩子节点不为空则依次入队if (T-Left){AddQ(Q, T-Left); }if (T-Right){AddQ(Q, T-Right);}}
} 二叉树遍历的应用 输出二叉树中的叶节点
之前讲过的递归先序遍历二叉树写法很简单而要输出二叉树中的叶节点就可以在进行遍历的过程中进行检测如果为叶节点则输出否则继续遍历。 叶节点即左孩子节点为空、右孩子节点也为空。
代码实现
void PreOrderPrintLeaves(BinTree BT)
{if (BT){if (!BT-Left !BT-Right)printf(%d , BT-data);PreOrderPrintLeaves(BT-Left);PreOrderPrintLeaves(BT-Right);}
} 求二叉树的高度
树是递归定义的一颗二叉树的高度应该等于左右两颗子树的最大高度1 求二叉树的高度利用的是后序遍历的一种程序框架来实现的。 思路图解 代码实现
int PostOrderGetHeight(BinTree BT)
{int HL, HR, MaxH;if (BT){HL PostOrderGetHeight(BT-Left); //求左子树的高度HR PostOrderGetHeight(BT-Right); //求右子树的高度MaxH (HL HR) ? HL : HR; //取左右子树的最大高度return (MaxH 1); //返回树的高度}else{return 0; //空树的高度为0}
} 二元运算表达式树及其遍历 对上面的表达式树进行三种遍历,可以得到三种不同的访问结果
试着分别写出上面表达式树前序中序和后序遍历的不同表达式复习一遍之前讲的树的遍历。 先序遍历可以得到前缀表达式a*bc**defg
中序遍历可以得到中缀表达式ab*cd*ef*g
后序遍历可以得到后缀表达式abc*de*fg*
但需要注意的是中缀表达式会受到运算符优先级的影响所以单单这样通过中序遍历得出的中缀表达式是不完全准确的。
解决方法是在输出左子树之前先输出一个左括号左子树结束的时候再输出一个右括号。 由两种遍历序列确定二叉树
已知三种遍历中的任意两种遍历序列能否唯一确定一颗二叉树呢
答案是两种遍历序列中必须要有一种是中序遍历才能够唯一确定一颗二叉树。 假设没有中序看下面两个序列
先序遍历序列A B
后序遍历序列B A 像这样一组简单的序列只有先序遍历序列和后序遍历序列的情况下就有两颗是符合的二叉树其中根节点是容易确定的先序的第一个节点就是根后序的最后一个节点就是根但是左右节点是不好区分的所以就导致了只有先序序列和后序序列的情况下没法唯一地确认一颗二叉树。 下面就来看看已知先序序列和中序序列怎么样来确定一颗二叉树。
思路
根据先序遍历序列第一个节点确定根节点根据根节点在中序遍历序列中分割出左右两个子序列对左子树和右子树分别递归使用相同的方法继续分解。 举个例子清晰一下思路
先序序列 abcdefghij
中序序列 cbedahgijf 所以最终通过先序遍历序列和中序遍历序列唯一确定的二叉树就为 end 学习自MOOC数据结构——陈越、何钦铭
