《数据结构》复习笔记--二叉树2

《数据结构》复习笔记--二叉树2

二叉树的非递归遍历：

中序遍历非递归遍历算法 非递归算法实现的基本思路：使用堆栈：

void InOrderTraversal( BinTree BT ){ BinTree T=BT; Stack S = CreatStack( MaxSize ); /*创建并初始化堆栈S*/ while( T || !IsEmpty(S) ) { while(T) /*一直向左并将沿途结点压入堆栈*/ { Push(S,T); T = T->Left; } if(!IsEmpty(S)) { T = Pop(S); /*结点弹出堆栈*/ printf(“%5d”, T->Data); /*（访问）打印结点*/ T = T->Right; /*转向右子树*/ } }}

void InOrderTraversal( BinTree BT ){ BinTree T=BT; Stack S = CreatStack( MaxSize ); /*创建并初始化堆栈S*/ while( T || !IsEmpty(S) ) { while(T) /*一直向左并将沿途结点压入堆栈*/ { Push(S,T); printf(“%5d”, T->Data); /*（访问）打印结点*/ T = T->Left; } if(!IsEmpty(S)) { T = Pop(S); /*结点弹出堆栈*/ T = T->Right; /*转向右子树*/ } }}

void PostOrder_NoRecurse(BinTree BT, void (*Do)(BinTree))//非递归实现后序遍历{ BinTree T = BT; Stack s = CreateStack(20); int Tag[20]; //Tag用来标记第几次遇到堆栈内的元素，本身是一个整形堆栈 while(T || !Stack_IsEmpty(s)) { while(T) //每遇到一个新元素，则到控制到此处 { Stack_Push(s, T); //放入堆栈并循环至其最左 Tag[s->size - 1] = 0; T = T->Left; } while (!T && !Stack_IsEmpty(s)) { T = Stack_Pop(s); //取出堆栈中的一个元素，并判断它的Tag if(Tag[s->size]) { (*Do)(T); //Tag != 0 说明是第三次遇见该节点，对它进行操作 T = 0; //将T设为0以触发While条件，继续循环 } else //Tag = 0 说明是第二次遇见（第一次是将Tag设为0） { if (!T->Right) (*Do)(T); //如果右儿子不存在，则直接输出 else { Stack_Push(s, T); //如果右儿子存在，则将它放回堆栈 Tag[s->size - 1]++; //并累加相应的Tag } T = T->Right; //返回右儿子。注意，如果右儿子不存在，则会触发While继续循环 } //否则会判定为遇见新元素跳出循环，继续外部外部的大While循环 } }}

由两种遍历序列确定二叉树?

已知三种遍历中的任意两种遍历序列，能否唯一确定一棵二叉树呢？我们知道，无论哪一种，必须要先知道先序遍历。

比如：先序和中序遍历序列来确定一棵二叉树 〖分析〗  1根据先序遍历序列第一个结点确定根结点； 2根据根结点在中序遍历序列中分割出左右两个子序列 3对左子树和右子树分别递归使用相同的方法继续分解。

题目练习：过几天再贴上。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。