二叉树的遍历与线索二叉树（哈喜老师）

1、二叉树的遍历1.1概念1.2先、中、后序遍历的递归代码#define_CRT_SECURE_NO_WARNINGS1#includestdio.h// 实现二叉链表结构的二叉树// 定义二叉树中结点的结构typedefstructBiTNode{intdata;// 数据域structBiTNode*lchild;// 指向左孩子的指针structBiTNode*rchild;// 指向右孩子的指针}BiTNode,*BiTree;// 前序遍历递归版本voidPreOrder(BiTree T)// T接收根结点的地址{if(T!NULL){// 空树不处理printf(%d ,T-data);// ① 访问根结点PreOrder(T-lchild);// ② 递归遍历左子树PreOrder(T-rchild);// ③ 递归遍历右子树}}// 中序遍历递归版本voidInOrder(BiTree T)// T接收根结点的地址{if(T!NULL){// 空树不处理InOrder(T-lchild);// ① 递归遍历左子树printf(%d ,T-data);// ② 访问根结点InOrder(T-rchild);// ③ 递归遍历右子树}}// 后序遍历递归版本voidPostOrder(BiTree T)// T接收根结点的地址{if(T!NULL){// 空树不处理PostOrder(T-lchild);// ① 递归遍历左子树PostOrder(T-rchild);// ② 递归遍历右子树printf(%d ,T-data);// ③ 访问根结点}}1.3利用队列实现二叉树的层次遍历Queue.h#pragmaonce#includestdio.h#includestdlib.h#includestdbool.hstructBiTNode;// 结构体类型的声明// 实现链式存储结构的队列(带头结点的版本)// 定义结点的结构结点用于存储队列中的元素typedefBiTNode*ElemType;// 队列中存储的数据类型是二叉树的结点的地址typedefstructLinkNode{ElemType data;structLinkNode*next;}LinkNode;// 定义队列的结构typedefstructLinkQueue{LinkNode*front;// 指向头结点的指针千万注意不是指向队头元素的指针LinkNode*rear;// 指向队尾元素的指针}LinkQueue;// 队列的初始化voidInitQueue(LinkQueueQ);// 队列是否为空。若为空返回true否则返回falseboolIsEmpty(LinkQueue Q);// 新元素x入队(即将新元素插到单链表的尾部)voidEnQueue(LinkQueueQ,ElemType x);// 队头元素出队(即删除第一个存储有效数据的结点),并将出队元素的值赋给变量xboolDeQueue(LinkQueueQ,ElemTypex);Queue.cpp#define_CRT_SECURE_NO_WARNINGS1#includeQueue.h// 队列的初始化voidInitQueue(LinkQueueQ){// 先申请一个头结点的空间// 初始化时指向头结点的指针与指向队尾元素的指针均指向头结点Q.frontQ.rear(LinkNode*)malloc(sizeof(LinkNode));Q.front-nextNULL;// 头结点中的next指针置为NULL}// 队列是否为空。若为空返回true否则返回falseboolIsEmpty(LinkQueue Q){if(Q.frontQ.rear)// 队列为空的条件既可以是Q.front Q.rear也可以是Q.front-next NULLreturntrue;elsereturnfalse;}// 新元素x入队(即将新元素插到单链表的尾部)voidEnQueue(LinkQueueQ,ElemType x){// 新元素x入队前先申请一个结点的空间用于存储新元素LinkNode*s(LinkNode*)malloc(sizeof(LinkNode));// s指向新结点s-datax;s-nextNULL;Q.rear-nexts;Q.rears;// 不要忘了让rear指针指向新的队尾元素}// 队头元素出队(即删除第一个存储有效数据的结点),并将出队元素的值赋给变量xboolDeQueue(LinkQueueQ,ElemTypex){if(Q.frontQ.rear)// 若队列为空则无法执行出队操作returnfalse;LinkNode*pQ.front-next;// p指向待出队的元素xp-data;// 将待出队元素的值赋给变量xQ.front-nextp-next;if(pQ.rear)// 注意如果队列中只有一个有效元素那么出队时需要修改队尾指针的值Q.rearQ.front;free(p);// 回收待出队元素的空间pNULL;returntrue;}BTree.h#define_CRT_SECURE_NO_WARNINGS1#includeQueue.h// 实现二叉链表结构的二叉树// 定义二叉树中结点的结构typedefstructBiTNode{intdata;// 数据域structBiTNode*lchild;// 指向左孩子的指针structBiTNode*rchild;// 指向右孩子的指针}BiTNode,*BiTree;// 利用队列实现二叉树的层序遍历voidLevelOrder(BiTree T);// T表示根结点的地址BTree.cpp重点看这个代码#define_CRT_SECURE_NO_WARNINGS1#includeBTree.h// 利用队列实现二叉树的层序遍历voidLevelOrder(BiTree T)// T表示根结点的地址{LinkQueue q;// 创建一个队列InitQueue(q);// 队列的初始化BiTree p;EnQueue(q,T);// 根结点入队while(!IsEmpty(q))// 队列不为空就进入循环{DeQueue(q,p);// 队头结点出队并将出队元素的值赋给pprintf(%d ,p-data);// 打印出队结点的值if(p-lchild!NULL)EnQueue(q,p-lchild);// 若p指向的结点的左孩子不为空则让左孩子入队if(p-rchild!NULL)EnQueue(q,p-rchild);// 若p指向的结点的右孩子不为空则让右孩子入队}}1.4由遍历序列构造二叉树1.4.1习题11.4.2习题2真题1.4.3习题3真题2、线索二叉树2.1线索二叉树的概念// 定义线索二叉树的结点结构typedefstructThreadNode{ElemType data;// 数据域存放结点的值structThreadNode*left,*right;// 左、右指针域intlTag,rTag;// lTag是左、rTag是右标志位0表示孩子指针1表示线索指针}ThreadNode,*ThreadTree;2.2构造线索二叉树2.3习题2.3.12010年题3比较容易显然选D。根据后序遍历序列为dbca以及后序线索二叉树的概念可知选D2.3.2习题二有难度