清华大学：《数据结构》课程教材PPT教学课件（C语言版）第六章 树和二叉树（6.4-6.6）

64遍历二叉树和线索二叉树 遍历二叉树 遍历二叉树是指按一定的规对二叉树的每个结 点,坊应且仅访问一次的处理过程。 访问是一种抽象操作,是对结点的某种处理,例如 可以是求结点的度、或层次、打印结点的信息,或做 其他任何工作。 次遍历后,使树中结点的非线性排列,按访问的 先后顺序变为某种线性排列。 遍历的次序:若设二叉树根为D,左子树为L,右子 树为R,并限定先左后右,则有以下三种遍历次序: LDR中序遍历;LRD后序遍历;DLR先序遍历

6.4 遍历二叉树和线索二叉树 一、遍历二叉树 遍历二叉树是指按一定的规律对二叉树的每个结 点，访问且仅访问一次的处理过程。 • 访问是一种抽象操作，是对结点的某种处理，例如 可以是求结点的度、或层次、打印结点的信息，或做 其他任何工作。 • 一次遍历后，使树中结点的非线性排列，按访问的 先后顺序变为某种线性排列。 • 遍历的次序：若设二叉树根为D，左子树为L，右子 树为R，并限定先左后右，则有以下三种遍历次序： LDR 中序遍历；LRD 后序遍历；DLR 先序遍历

64遍历二叉树和线索二叉树 1.前序遍历二又树第法颜述 算法思想 void Pre OrderTraverse (bitree t 若二叉树非空,则:{/先序遍历三又树算法 /*其中visi0是对数据元素* 1)访问根结点 /*的具体应用访问函数*/ 2)前序遍历左子树T)如果非空 3)前序遍历右子树 visit(T->data); PreOrderTraverse(t->lchild); PreOrderTraverse(t->rchild);

6.4 遍历二叉树和线索二叉树 1.前序遍历二叉树 算法思想: 若二叉树非空，则： 1）访问根结点 2）前序遍历左子树 3）前序遍历右子树 算法描述: void PreOrderTraverse(BiTree T) { /*先序遍历二叉树算法，*/ /*其中visit()是对数据元素*/ /*的具体应用访问函数*/ if(T) /*如果T非空*/ { visit(T->data); PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); } }

64遍历二叉树和线索二叉树 按前序序列建二叉树 假定 TElem Type是char型,则可用以下算法建立一个二叉树 BiTree Create Bitree( i BiTree t; char ch scanf(“%c~,&ch);∥依次输入前序序列当左(右)子树为空时输入空格 if(ch! it=(BiTree)malloc(sizeof( BiTnode) t->data=ch t->lchild= Create BiTree() t->rchild= Create BiTree(); else tNULL return t;)

6.4 遍历二叉树和线索二叉树 假定TElemType是char型，则可用以下算法建立一个二叉树 BiTree CreateBiTree( ) { BiTree t; char ch; scanf(“%c”,&ch); //依次输入前序序列当左(右)子树为空时输入空格 if(ch!=’’) {t=(BiTree)malloc(sizeof(BiTnode)); t->data=ch; t->lchild= CreateBiTree( ); t->rchild= CreateBiTree( );} else t=NULL; return t; } 按前序序列建二叉树

64遍历二叉树和线索二叉树 2后序遍历二叉树篁法述 算法想 void PostOrderTraverse(bitree t) /*后序遍历二叉树算法,* 若二叉树非空,则 /*其中 visit(是对数据元素*/ /*的具体应用访问函数*/ 后序遍历左子树f(m)产如果T非空* 2)后序遍历右子树{ 3)访问根结点 PostOrderTraverset->lchild); PostOrderTraverser->rchild); visi(T→>data) )

6.4 遍历二叉树和线索二叉树 2.后序遍历二叉树 算法思想: 若二叉树非空，则： 1）后序遍历左子树 2）后序遍历右子树 3）访问根结点 算法描述: void PostOrderTraverse(BiTree T) { /*后序遍历二叉树算法，*/ /*其中visit()是对数据元素*/ /*的具体应用访问函数*/ if(T) /*如果T非空*/ { PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); visit(T->data); } }

64遍历二叉树和线索二叉树 3中序遍历二叉树篁法述 算法思想: void InOrderTraverse(Bitree t) {/*中序遍历二叉树算法,* 若二叉树非空,则:/其中5Q是对数据元素+ /米的具体应用访问函数*/ 1)中序遍历左子树()/如果T非空* 2)访问根结点 3)中序遍历右子树 InOrderTraverset->lchild) visit(T->data); InOrderTraverset->rchild);

6.4 遍历二叉树和线索二叉树 3.中序遍历二叉树 算法思想: 若二叉树非空，则： 1）中序遍历左子树 2) 访问根结点 3）中序遍历右子树 算法描述: void InOrderTraverse(BiTree T) { /*中序遍历二叉树算法，*/ /*其中visit()是对数据元素*/ /*的具体应用访问函数*/ if(T) /*如果T非空*/ { InOrderTraverse(T->lchild); visit(T->data); InOrderTraverse(T->rchild); } }

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个空链域 来存放结点的前驱和后继结点的信息