[工学]数据结构c语言版 5.pptVIP

遍历的递归算法： 1.先序 void PreOrder(BTree BT) { if (BT) { Visit(BT); PreOrder(BT-Lchild); PreOrder(BT-Rchild); } } （2）中序 void InOrder(BTree BT) { if (BT) { InOrder(BT-Lchild); Visit(BT); InOrder(BT-Rchild); } } （3）后序遍历递归算法 void PostOrder(BTree BT) { if (BT) { PostOrder(BT-Lchild); PostOrder(BT-Rchild); Visit(BT); } } 5．3．2二叉树遍历算法的应用 例： 已知一棵二叉树的前序遍历结果为ABEDCFGHIJ中序遍历结果为EBCDAFHIGJ，写出这棵二叉树后序遍历结果。 5.4线索二叉树 利用空指针，使结点更紧密连结，加快遍历速度，便于查找前驱后继。 LThread LChild Data RChild RThread 1：引线 0：指针 前驱 后继 定义结点的类型如下： typedef struct thread_tree { int LThread, RThread; ElemType data; struct thread_tree *LChild, *RChild; } 建立线索二叉树 if 左指针为空 then LChild 指到该树***序遍历的前一个结点 将LThread 设为1 if 右指针为空 then RChild 指到该树***序遍历的后 一个结点 将RThread 设为1 G H D E F B C A 5.5二叉排序树（二叉查找树） 二叉排序树的建立 1.以第一个建立元素为根结点 2.依序将元素根结点比较 a. 若元素值大于根结点，则将元素往根结点右子结点移动；若此右子结点为空，将元素值存入，否则就重复比较，直到找到适当之空结点为止。 b.若元素值小于根结点，则将元素往根结点左子结点移动；若此左子结点为空，将元素值存入，否则就重复比较，直到找到适当之空结点为止。 Void create_btree(int *b_tree,int *nodelist, int len) {int i; int level; b_tree[1]=nodelist[1]; for(i=2;i=len;i++) {level=1; while(b_tree[level]!=0) {if(nodelist[i]b_tree[level]) level=level*2; else level=level*2+1; b_tree[level]=nodelist[i];}} } 二叉排序树的查找 遍历 二分 b_tree search (b-tree point, int findnode) {while(point!=null) {if(point-data==findnode) return point; else if(point-datafindnode) point=point-left; else point=point-right;} } 一般树转二叉树： 步骤： 1.保留所有结点与其左子结点的链接； 2.连接所有兄弟结点； 3.打断所有结点原本与右子结点的链接； 4.将兄弟结点顺时针旋转4