数据结构之树和二叉树.ppt

1. 线索链表类型定义inthreading.h #include iostream using namespace std; typedef char TElemType; enum PointerTag{Link,Thread}; //Link==0:指针，Thread==1:线索 struct BiThrNode{ TElemType data; BiThrNode *lchild,*rchild; PointerTag ltag,rtag; }; typedef BiThrNode *BiThrTree; 第六十三页，共九十二页。 void createBiThrTree(BiThrTree T); void preOrderTraverse(BiThrTree T,void (*visit)(TElemType)); BiThrNode* inOrderThreading(BiThrTree T); void inTraverseThr(BiThrTree T,void (*visit)(TElemType)); 第六十四页，共九十二页。 2. 实现inthreading.cpp #include inthreading.h //按先序次序输入二叉树中结点的值（#表示空格），构造二叉线索树T void createBiThrTree(BiThrTree T){ TElemType ch; cinch; if(ch==#) // 空 T=NULL; else{ T=new BiThrNode; if(!T) exit(1); T-data=ch; // 生成根结点 createBiThrTree(T-lchild); // 构造左子树 if(T-lchild) // 有左孩子 T-ltag=Link; createBiThrTree(T-rchild); // 构造右子树 if(T-rchild) // 有右孩子 T-rtag=Link; } } 第六十五页，共九十二页。 图6.7 二叉树的顺序存储 对于一棵二叉树，若采用顺序存贮时，当它为完全二叉树时，比较方便,若为非完全二叉树，将会浪费大量存贮存贮单元。最坏的非完全二叉树是全部只有右分支，设高度为K，则需占用2K-1个存贮单元，而实际只有k个元素，实际只需k个存储单元。因此，对于非完全二叉树，宜采用下面的链式存储结构。 第三十一页，共九十二页。 2. 二叉链表存贮结构⑴ 二叉链表表示 将一个结点分成三部分，一部分存放结点本身信息，另外两部分为指针，分别存放左、右孩子的地址。 注：如果需要倒查某结点的双亲，可以再增加一个双亲域（直接前趋）指针，将二叉链表变成三叉链表。 lchild data rchild 第三十二页，共九十二页。 对于图6.7所示二叉树，用二叉链表形式描述。 图6.8 二叉树的二叉链表表示 第三十三页，共九十二页。 ⑵ 二叉链表的数据类型bitree.h //二叉链表定义 #include iostream using namespace std; typedef char TElemType; struct BiTNode{ TElemType data; BiTNode *lchild,*rchild; }; typedef BiTNode *BiTree; 第三十四页，共九十二页。 void initBiTree(BiTree T); void createBiTree(BiTree T); //递归前序遍历 void preOrderTraverse(BiTree T,void (*visit)(TElemType)); //非递归前序遍历 void preOrderTraverse1(BiTree T,void (*visit)(TElemType)); //递归中序遍历 void inOrderTraverse(BiTree T,void (*visit)(TElemType)); //递归后序遍历 void postOrderTraverse(BiTree T,void (*visit)(TElemType)); 第三十五页，共九十二页。 ⑶ 二叉链表的建立 为了后面遍历二叉树方便，先介绍建立二叉链表的算法（假设ElemType 为char型）。 第三十六页，共九十二页。 //按先序次序输入二叉树中结点的值（#表示空格）， //构造二叉链表表示的二叉树T。 void createBiTree(BiTree T){ TElemType ch; cinch; if(ch==#