数据结构-中序遍历线索二叉树,堆排序

青旅半醒 2022-06-07 00:46 260阅读 0赞

线索化二叉树的定义

  1. typedef char ElemType;
  2. typedef enum{LINK = 0,THREAD = 1}PointTag;
  3. typedef struct BiThrNode
  4. {
  5.     BiThrNode *leftchild;
  6.     BiThrNode *rightchild;
  7.     PointTag Ltag,Rtag;  //枚举
  8.     ElemType data;
  9. }BiThrNode * , ThreadBinaryTree;

中序遍历线索二叉树

  1. BiThrNode *frist(BiThrNode *str)  //前驱
  2. {
  3.     while (str != NULL && str->Ltag != THREAD) 
  4.     {
  5.         str = str->leftchild; //当前驱不为1时，继续遍历左孩子
  6.     }
  7.     printf("%c ",str->data);
  8. }
  9. BiThrNode *next(BiThrNode *p)  //后继
  10. {
  11.     if (p == NULL) return NULL;
  12.     if (p->Rtag == THREAD) 
  13.     {
  14.         return p->rightchild;  //当后继为1时，返回右孩子
  15.     }
  16.     else
  17.     {
  18.         return frist(p->rightchild); 
  19.     }    //当后继不为1时，返回它的右孩子的前驱
  20. }
  21. InOrderThrTree(BiThrNode *str)  //中序遍历线索二叉树
  22. {
  23.     for (BtNode *p = frist(str);p != NULL;p = next(p))
  24.     {
  25.         printf("%c ",str->data);  //前驱和后继
  26.     }
  27. }

逆序中序遍历线索二叉树
堆排序
（ABCDEFG等等为需要排序的数字）
二叉树转化为数组，序号符合左=2i+1，右=2i+2的规律

  1. typedef int HeapElem;

发表评论

表情：
评论列表 （有 0 条评论，260人围观）

还没有评论，来说两句吧...

相关阅读