64遍历二叉树和线索二叉树 例:表达式a+b×(-d)-ef 遍历结果: 中序:a+b×c-d-e/f 后序:abcd-×+ef/ 先序:-+a×b-cd/ef
6.4 遍历二叉树和线索二叉树 例：表达式 a+b ×(c-d)-e/f a c d e f ／ b － × ＋ － + 遍历结果: 中序: a+b × c － d － e /f 后序: abcd － × +ef / － 先序: － +a × b－ cd /ef
64遍历二叉树和线索二叉树 三种遍历过程示意图例 圖Ab 虚线表示执行过程:向下表示更深层的递归调用; 向上表示递归调用返回 沿虚线记下各类符号便得到遍历的结果
6.4 遍历二叉树和线索二叉树 三种遍历过程示意图例 a c b × － a b * c - a b * - c a b * c - － × a b c • 虚线表示执行过程: 向下表示更深层的递归调用; 向上表示递归调用返回; • 沿虚线记下各类符号,便得到遍历的结果
64遍历二叉树和线索二叉树 void In OrderTraverse bitree t 中序遍历非递归算法,s为存储二叉树结点指针栈} initstack(s); push(s, T) 根结点先进栈, while(! stackempty(s) 左结点紧跟根后面 I while(stacktop(s)) 进栈右结点在根 push(s, stacktop(s)tIchi 出栈后入栈 p:pop(s) 每个结点都要进 if(! stackempty(s)) 一次和出一次栈, Ivisit(stacktop (s)t data 并且总是访问栈顶 元素,因此,算 p:pop(S) 法正确,时间复 push(s,p↑. rchild)}}杂度为o(m),空 间复杂度为O(m)
6.4 遍历二叉树和线索二叉树 void InOrderTraverse(BiTree T) {中序遍历非递归算法,s为存储二叉树结点指针栈} initstack(s)； push(s,T)； while (!stackempty(s)) { while (stacktop(s)) push(s, stacktop(s)↑.lchild)； p:=pop(s)； if(!stackempty(s)) {visit(stacktop(s)↑.data)； p:=pop(s)； push(s, p↑.rchild)}} } • 根结点先进栈， 左结点紧跟根后面 进栈,右结点在根 出栈后入栈 • 每个结点都要进 一次和出一次栈， 并且总是访问栈顶 元素， 因此， 算 法正确， 时间复 杂度为 O(n)， 空 间复杂度为O(n)
64遍历二叉树和线索二叉树 二、线索二叉树 1.问题的提出:通过遍历二叉树可得到结点 的一个线性序列,在线性序列中,就存在结点 和前驱和后继,但是在二叉树上只能找到结点 的左孩子、右孩子,结点的前驱和后继只有在 遍历过程中才能得到,那么,能否通过结点的 两个链域查找出任一结点的前驱和后继?
6.4 遍历二叉树和线索二叉树 二、线索二叉树 ⒈ 问题的提出：通过遍历二叉树可得到结点 的一个线性序列，在线性序列中，就存在结点 和前驱和后继，但是在二叉树上只能找到结点 的左孩子、右孩子，结点的前驱和后继只有在 遍历过程中才能得到，那么，能否通过结点的 两个链域查找出任一结点的前驱和后继?
64遍历二叉树和线索二叉树 2.外析: n个结点有n-1个前驱和n-1个后继; 共有2n个链域,其中:n+1个空链域, n-1个指针域; 因此,必须用空链域来存放结点的前驱 和后继。线索二叉树就是利用n+1个空链域 来存放结点的前驱和后继结点的信息
6.4 遍历二叉树和线索二叉树 2. 分析： • n个结点有n-1个前驱和n-1个后继； • 一共有2n个链域，其中：n+1个空链域， n-1个指针域； • 因此, 必须用空链域来存放结点的前驱 和后继。线索二叉树就是利用n+1个空链域 来存放结点的前驱和后继结点的信息