归终止条件是二叉树为空。Р中序遍历的递归算法定义:(1)遍历左子树; (2)访问根结点; (3)遍历右子树。Р先序遍历的递归算法定义:(1)访问根结点; (2)遍历左子树; (3)遍历右子树。Р后序遍历得递归算法定义:(1)遍历左子树; (2)遍历右子树; (3)访问根结点。Р递归工作栈中包括两项:一项是递归调用的语句编号,另一项则是指向根结点的指针。Р 已知一棵二叉树的前序和中序遍历序列或中序和后序遍历序列,可唯一确定一棵二叉树。具体方法如下:Р 首先根据前序或后序遍历序列确定二叉树的各子树的的根,然后根据中序遍历序列确定各子树根的左右子树。Р6.线索二叉树:n个结点的二叉链表必定存在n+1个空指针域,可以利用这些空指针域,存放指向结点在某种遍历次序下的前趋和后继结点的指针,这种指向前驱和后继结点的指针称为"线索",这种加上线索的二叉链表称为线索链表,相应的二叉树称为线索二叉树(Threaded BinaryTree)。Р线索链表的结点结构:Р其中:ltag和rtag是增加的两个标志域,用来区分结点的左、右指针域是指向其左、右孩子的指针,还是指向其前趋或后继的线索。Р Р 图中的实线表示指针,虚线表示线索。线索二叉树中,一个结点是叶结点的充要条件为:左、右标志均是1。Р7.二叉树的线索化: 把对一棵二叉线索链表结构中所有结点的空指针域按照某种遍历次序加线索的过程称为线索化。Р和中序遍历算法一样,递归过程中对每结点仅做一次访问。因此对于n个结点的二叉树,线索化的算法时间复杂度为O(n)。Р8.树、森林到二叉树的转换:树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。Р将树转换成二叉树:①在所有兄弟结点之间加一道连线;②对每个结点,除了保留与其长子的连线外,去掉该结点与其它孩子的连线。由于树根没有兄弟,故树转化为二叉树后,二叉树的根结点的右子树必为空。
全文预览
