第6章 二叉树和树 前面的章节主要讨论的是线性结构，二叉树和树属于非线性的结构。遍历非线性结构比线性结构要麻烦。 二叉树及树的遍历技术是本章各种算法的核心，而且大多是以递归的形式表现的，阅读和编写递归算法是学习本章的难点。 讲授本章课程大约需8课时。

6.1 二叉树 6.2 二叉树的遍历

二叉树链式存储表示 1. 二叉链表 2．三叉链表 3．线索链表

1. 二叉链表 结点结构: root lchild data rchild A D E B C F 

C 语言的类型描述如下: typedef char TElemType; typedef struct BiTNode { // 结点结构 TElemType data; struct BiTNode *lchild, *rchild; // 左右孩子指针 } BiTNode, *BiTree; 结点结构: lchild data rchild

2．三叉链表 结点结构: root parent lchild data rchild A D E B C F 

C 语言的类型描述如下: typedef struct TriTNode { // 结点结构 TElemType data; struct TriTNode *lchild, *rchild; // 左右孩子指针 struct TriTNode *parent; //双亲指针 } TriTNode, *TriTree; 结点结构: parent lchild data rchild

3．线索链表 （请见后面的线索二叉树）

6.2 二叉树遍历 一、问题的提出 二、遍历算法描述 三、遍历算法应用举例 四、线索二叉树

一、问题的提出 顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。 “访问”的含义可以很广，如：输出结点的数据、判断结构信息等。

“遍历”是任何类型均有的操作， 对线性结构而言，只有一条搜索路 径(因为每个结点均只有一个后继)， 故不需要另加讨论。而二叉树是非 线性结构， 每个结点有两个后继， 则存在如何遍历即按什么样的搜索 路径遍历的问题。

对“二叉树”而言，可以有三条搜索路径： 1．先上后下的按层次遍历； 2．先左（子树）后右（子树）的遍历； 3．先右（子树）后左（子树）的遍历。

先左后右的遍历算法 先（根）序的遍历算法 中（根）序的遍历算法 后（根）序的遍历算法

先（根）序的遍历算法： 若二叉树为空树，则空操作；否则， （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树。 B A C D F G E H

中（根）序的遍历算法： 若二叉树为空树，则空操作；否则， （1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树。 B A C D F G E H

后（根）序的遍历算法： 若二叉树为空树，则空操作；否则， （1）后序遍历左子树； （2）后序遍历右子树； （3）访问根结点。 B A C D F G E H

二叉树遍历的输出顺序示例演示 前序遍历： 中序遍历： 后序遍历： A B C D E F G H A B C D E F G H A B D

二叉树遍历过程的示例演示 先序遍历： 中序遍历： 后序遍历： A B C D E F G H A A A B B C C B C D D E NULL B C D D E E F F E D F G G H H G H 先序遍历： 中序遍历： 后序遍历：

二、遍历算法描述 先序（前序）遍历二叉树的递归算法 中序遍历二叉树的递归算法 后序遍历二叉树的递归算法

先序遍历二叉树的递归算法 void preorder (BiTree T, void( *visit)(BiTree)) { // 先序遍历二叉树 ,visit是函数指针 if (T) { visit(T); // 访问结点 preorder(T->lchild, visit); // 遍历左子树 preorder(T->rchild, visit); // 遍历右子树 }

中序遍历二叉树的递归算法 void inorder (BiTree T, void( *visit)(BiTree)) { // 中序遍历二叉树 if (T) { inorder(T->lchild, visit); // 遍历左子树 visit(T); // 访问结点 inorder(T->rchild, visit); // 遍历右子树 }

后序遍历二叉树的递归算法 void postorder (BiTree T, void( *visit)(BiTree)) { // 后序遍历二叉树 if (T) { postorder(T->lchild, visit); // 遍历左子树 postorder(T->rchild, visit); // 遍历右子树 visit(T); // 访问结点 }

二叉树的递归遍历实验 tree.h文件

tree.cpp文件

三、遍历算法应用举例 1、统计二叉树中叶子结点的个数 (先序遍历) 2、求二叉树的深度(后序遍历) 3、复制二叉树(后序遍历) 4、建立二叉树的存储结构

1、统计二叉树中叶子结点的个数 算法基本思想: 先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点”的操作改为：若是叶子，则计数器增1。

void CountLeaf (BiTree T, int &count){ if ( T ) { if ((!T->lchild)&& (!T->rchild)) count++; // 对叶子结点计数 CountLeaf( T->lchild, count); CountLeaf( T->rchild, count); } // if } // CountLeaf

2. 求二叉树的深度(后序遍历) 算法基本思想: 首先分析二叉树的深度和它的左、右子树深度之间的关系。 从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加 1 。

int Depth (BiTree T ){ // 返回二叉树的深度 if ( !T ) return 0; else { hL = Depth( T->lchild );//充满技巧 hR= Depth( T->rchild ); if(hL>=hR) return hL+1; else return hR+1; }

3、复制二叉树(后序遍历) 递归操作：完成左右子树的复制 核心操作：生成一个根结点,并链接 左右子树 NEWT T 根元素 根元素

BiTNode *CopyTree(BiTNode *T) { if (!T ) return NULL; if (T->lchild ) newlptr = CopyTree(T->lchild);//复制左子树 else newlptr = NULL; if (T->rchild ) newrptr = CopyTree(T->rchild);//复制右子树 else newrptr = NULL; newT = GetTreeNode(T->data, newlptr, newrptr); return newT; } // CopyTree

BiTNode *GetTreeNode(TElemType item, BiTNode *lptr , BiTNode *rptr ){ 生成一个二叉树的结点的操作算法： (其数据域为item,左指针域为lptr,右指针域为rptr) BiTNode *GetTreeNode(TElemType item, BiTNode *lptr , BiTNode *rptr ){ if (!(T = new BiTNode)) exit(1); T-> data = item; T-> lchild = lptr; T-> rchild = rptr; return T; }

例如：下列二叉树的复制过程如下： newT A ^ B E ^ T A B C D E F G H K C ^ ^ F ^ ^ D ^ G

第8次书面作业 6.5, 6.6, 6.7, 6.8,6.9 第14次上机作业 实现算法6.1(并试验中序，后序),6.5,6.6