3.1 二叉树的存储结构

  1. //顺序存储
  2. #define MaxSize 100
  3. struct TreeNode {
  4.         ElemType value;
  5.         bool isEmpty;
  6. };
  7. TreeNode t[MaxSize];
  8. //链式存储
  9. typedef struct BiTNode{
  10.         ElemType data;
  11.         struct BiTNode *lchild,*rchild;
  12. }BiTNode,*BiTree;

3.2 二叉树的前中后序遍历

  1. //前序遍历
  2. void PreOrder(BiTree T){
  3.      if(T!=NULL)
  4.        visit(T);
  5.        PreOrder(T->lchild);
  6.        PreOrder(T->rchild);
  7. }
  8. //中序遍历
  9. void InOrder(BiTree T){
  10.      if(T!=NULL){
  11.         InOrder(T->lchild);
  12.         visit(T);
  13.         InOrder(T->rchild);
  14.      }
  15. }
  16. //后序遍历
  17. void PostOrder(BiTree T){
  18.      if(T!=NULL){
  19.         PostOrder(T->lchild);
  20.         PostOrder(T->rchild);
  21.         visit(T);
  22.      }
  23. }

3.3 二叉树的层序遍历

  1. void LevelOrder(BiTree T){
  2.      LinkQueue Q;
  3.      InitQueue(Q);
  4.      BiTree p;
  5.      EnQueue(Q,T);
  6.      while(!IsEmpty(Q)){
  7.           DeQueue(Q,p);
  8.           visit(p);
  9.           if(p->lchild!=NULL)
  10.              EnQueue(Q,p->lchild);
  11.           if(p->rchild!=NULL)
  12.              EnQueue(Q,p->rchild);
  13.      }
  14. }

3.4 二叉树的中序线索化

  1. //线索二叉树结点
  2. typedef struct ThreadNode{
  3.         ElemType data;
  4.         struct ThreadNode *lchild,*rchild;
  5.         int ltag,rtag;
  6. }ThreadNode,*ThreadTree;
  7. //全局变量pre，指向当前访问结点的前驱
  8. ThreadNode *pre=NULL;
  9. //中序遍历二叉树，一边遍历一边线索化
  10. void InThread(ThreadTree T){
  11.       if(T!=NULL){
  12.          InThread(T->lchild);
  13.          visit(T);
  14.          InThread(T->rchild);
  15.       }
  16. }
  17. void visit(ThreadNode *q){
  18.       if(q->lchild==NULL){
  19.          q->lchild=pre;
  20.          q->ltag=1;
  21.       }
  22.       if(pre!=NULL && pre->rchild==NULL){
  23.           pre->rchild=q;
  24.           pre->rtag=1;
  25.       }
  26.       pre=q;
  27. }
  28. //中序线索化二叉树T
  29. void CreateInThread(ThreadTree T){
  30.       pre=NULL;
  31.       if(T!=NULL){
  32.          if(pre->rchild==NULL)
  33.              pre->rtag=1;
  34.       }
  35. }

3.5 二叉树的先序线索化

  1. //全局变量pre,指向当前点的前驱
  2. ThreadNode * pre=NULL;
  3. //先序遍历二叉树，一边遍历一遍线索化
  4. void Prethread(ThreadTree T){
  5.     if(T!= NULL){
  6.         visit(T);
  7.         PreThread(T->lchild);
  8.         PreThread(T->lchild);
  9.     }
  10. }
  11. void visit(ThreadNode *q){
  12.     if(q->lchild==NULL){
  13.         q->lchild=pre;
  14.         q->ltag=1;
  15.     }
  16.     if(pre!=NULL && pre->rchild==NULL){
  17.         pre->rchild=q;
  18.         pre->rtag=1;
  19.     }
  20.     pre=q;
  21. }
  22. //先序线索化二叉树T
  23. void createPreThread(ThreadTree T){
  24.     pre=NULL;
  25.     if(T->NULL){
  26.         PreThread(T);
  27.         if(pre->rchild==NULL)
  28.             pre->rtag=1;
  29.     }
  30. }

3.6 二叉树的后序线索化

  1. ThreadTree *pre=NULL;
  2. //后序遍历
  3. void PostThread(ThreadTree T){
  4.     if(T!=NULL){
  5.         PostThread(T->lchild);
  6.         PostThread(T->rchild);
  7.         visit(T);
  8.     }
  9. }
  10. void visit(ThreadNode *q){
  11.     if(q->lchild==NULL){
  12.         q->lchild=pre;
  13.         q->ltag=1;
  14.     }
  15.     if(pre!=NULL && pre->rchild==NULL){
  16.         pre->rchild=q;
  17.         pre->rchild=tag;
  18.     }
  19.     pre=q;
  20. }
  21. //后序线索化二叉树T
  22. void CreatePostThread(ThreadTree T){
  23.     pre=NULL;
  24.     if(T!=NULL){
  25.         PostThread(T);
  26.     if(pre->rchild==NULL)
  27.         pre->rtag=1;
  28.     }
  29. }

3.7 线索二叉树找前驱/后继

  1. //找到以P为根的子树中，第一个被中序遍历的结点
  2. ThreadNode *Firstnode(ThreadNode *p){
  3.     //循环找到最左下结点（不一定是叶节点）
  4.     while(p->ltag==0)
  5.         p=p->lchild;
  6.     return p;
  7. }
  8. //在中序线索二叉树中找到结点p的后继结点
  9. ThreadNode *Nextnode(ThreadNode *p){
  10.     //右子树中最左结点
  11.     if(p->rtag==0) return FirstNode(p->rchild);
  12.     else return p->rchild;
  13. }
  14. //对中序线索化线索二叉树进行中序遍历（利用线索二叉树实现的非递归算法）