devbox
小丑西瓜9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

大一下 数据结构 清华严蔚敏(C语言)版 学习记录——树和二叉树_数据结构一课一文

作者：小丑西瓜9 | 2024-05-19 10:58:02

赞

踩

数据结构一课一文

基础知识点：

1、结点拥有的子树称为结点的度；

2、度为0的结点称为叶子或终端结点，度不为0的结点称为非终端结点或分支结点；

3、树的度是树内各结点的度的最大值；

4、同一个双亲的孩子之间互称兄弟；

5、结点的祖先是从根到该结点所经分支上的所有结点，子孙的定义反之；

6、结点的层次从根开始定义起，根为第一层，根的孩子为第二层；

7、其双亲在同一层的结点互为堂兄弟；

8、树中结点的最大层次称为树的深度或高度；

9、如果将树中结点的各子树看成从左至右是有次序的（即不能互换），

     则称该树为有序树，否则为无序树；

10、二叉树不是特殊的一种树！！！

11、n0 = n2+1；

12、完全二叉树和满二叉树是两种特殊形态的树；

13、二叉树的四个性质；

14、哈夫曼树的建立、求WPL值、求哈夫曼编码；

15、哈夫曼编码的长度不是唯一的；

按先序遍历的顺序建立二叉树，

然后输出每个结点和它在树中的深度

Sample Input：

        ABD##E##C##

Sample Output：

        A(1)B(2)D(3)E(3)C(2)

  1. #include<bits/stdc++.h>
  2. #define MAX_TREE_SIZE 100//二叉树的最大结点数
  3. #define OK 1
  4. #define OVERFLOW -2
  5. #define ERROR 0
  6. //typedef TElemType SqBiTree[MAX_TREE_SIZE];//0号单元存储根节点
  7. //SqBiTree bt;
  8. //typedef int TElemType;
  9. typedef char TElemType;
  10. typedef int Status;
  11.   
  12. /* typedef struct BiTNode{//二叉树的结点
  13.     TElemType data;
  14.     struct BiTNode *lchild,*rchild;//左右孩子指针
  15. }BiTNode,*BiTree; */
  16.  
  17. typedef struct BiTNode{
  18.     TElemType data;
  19.     struct BiTNode *lchild,*rchild,*parent;
  20.     int deep;//结点的深度
  21. }BiTNode,*BiTree;
  22.  
  23. typedef enum PointerTag{Link,Thread};//定义一个枚举类型
  24.  
  25. typedef struct BiThrNode{//线索二叉树的结点
  26.     TElemType data;
  27.     struct BiThrNode *lchild,*rchild;//左右指针
  28.     PointerTag LTag,RTag;//左右标志
  29. }BiThrNode,*BiThrTree;
  30.  
  31. typedef struct BPTNode{
  32.     TElemType data;
  33.     int parent;
  34.     char LRTag;
  35. }BPTNode;
  36.  
  37. typedef struct BPTree{
  38.     BPTNode nodes[MAX_TREE_SIZE];
  39.     int num_node;
  40.     int root;
  41. }BPTree;
  42.  
  43. Status PrintElement(TElemType e)
  44. {   //最简单的Visit()函数
  45.     //调用实例：PreOrderTraverse(T,PrintElement)
  46.     printf("%d ",e);
  47.     return OK;
  48. }
  49.  
  50. Status Visit(TElemType e)
  51. {   
  52.     printf("%c",e);
  53.     return OK;
  54. }
  55.  
  56. Status CreatBiTree(BiTree &T)//按先序次序构建二叉树
  57. {
  58.     TElemType ch;
  59.     scanf("%c",&ch);
  60.     if(ch=='#'||ch=='\n') T=NULL;
  61.     else{
  62.         if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
  63.         T->data=ch;
  64.         CreatBiTree(T->lchild);
  65.         CreatBiTree(T->rchild);
  66.     }
  67.     /* if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
  68.     T->data=ch;//生成根据结点
  69.     CreatBiTree(T->lchild);//构造左子树
  70.     CreatBiTree(T->rchild);//构造右子树 */
  71.     return OK;
  72. }
  73.  
  74. Status CreatBiTree_depth(BiTree &T,int d)//按先序次序构建二叉树,并定义计算每个结点的深度
  75. {
  76.     TElemType ch;
  77.     scanf("%c",&ch);
  78.     if(ch=='#'||ch=='\n') T=NULL;
  79.     else{
  80.         if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
  81.         T->data=ch;T->deep=d;
  82.         CreatBiTree_depth(T->lchild,d+1);
  83.         CreatBiTree_depth(T->rchild,d+1);
  84.     }
  85.     /* if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
  86.     T->data=ch;//生成根据结点
  87.     CreatBiTree(T->lchild);//构造左子树
  88.     CreatBiTree(T->rchild);//构造右子树 */
  89.     return OK;
  90. }
  91.  
  92. Status BitreeDepth(BiTree T)//求二叉树的深度
  93. {
  94.     int depth,ldepth,rdepth;
  95.     if(T==NULL) depth=0;
  96.     else{
  97.         ldepth=BitreeDepth(T->lchild);
  98.         rdepth=BitreeDepth(T->rchild);
  99.         depth=1+(ldepth>rdepth?ldepth:rdepth);
  100.     }
  101.     return depth;
  102. }
  103.  
  104. /* Status PreOrderTraverse(BiTree T.Status(*Visit)(TElemType e))//先序遍历的递归算法
  105. {   //Visit()是对结点操作的应用函数
  106.     if(T)
  107.     {
  108.         if(Visit(T->data))
  109.             if(PreOrderTraverse(T->lchild.Visit))
  110.                 if(PreOrderTraverse(T->rchild.Visit)) return OK;
  111.         return ERROR;
  112.     }else return OK;
  113. } */
  114.  
  115. /* Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e))//中序遍历的非递归算法
  116. {
  117.     InitStack(S);Push(S,T);//根指针进栈
  118.     while(!StackEmpty(S))
  119.     {
  120.         while(GetTop(S.p)&&p)
  121.         {
  122.             Push(S.p->lchild);//向左走到尽头
  123.         }
  124.         Pop(S.p);//空指针出栈
  125.         if(!StackEmpty(S))
  126.         {
  127.             Pop(S.p);
  128.             if(!Visit(p->data)) return ERROR;
  129.             Push(S.p->rchild); 
  130.         }
  131.     }
  132.     return OK;
  133. } */
  134.  
  135. /* Status InOrderTraverse(BiTree T.Status(*Visit)(TElemType e))
  136. {
  137.     InitStack(S);p=T;
  138.     while(p||StackEmpty(S))
  139.     {
  140.         if(p){
  141.             Push(S,p);
  142.             p=p->lchild;
  143.         }else{
  144.             Pop(S,p);
  145.             if(!Visit(p->data)) return ERROR;
  146.             p=p->rchild;
  147.         }
  148.     }
  149.     return OK;
  150. } */
  151.  
  152. /* BiTNode*GoFarLeft(BiTree ,Stack *S)//找最左边最远的结点
  153. {
  154.     if(!T) return NULL;
  155.     while(T->lchild)
  156.     {
  157.         Push(S,T);
  158.         T=T->lchild;
  159.     }
  160.     return T;
  161. }  */
  162.  
  163. /* void InorderTree(BiTree T,void(*Visit)(TElemType &e))//更清晰的中序遍历的非递归算法
  164. {
  165.     Stack *S;BiTree t,p;p=T->lchild;
  166.     t=GoFarLeft(p,S);
  167.     while(t)
  168.     {
  169.         visit(t->data);
  170.         if(t->rchild) t=GoFarLeft(t->rchild,S);
  171.         else if(!StackEmpty(S)) t=Pop(S);
  172.         else t=NULL;
  173.     }
  174. } */
  175.  
  176. Status InOrderTraverse_Thr(BiThrTree T,Status(*Visit)(TElemType e))//以双向线索链表为存储结构时对二叉树进行遍历的算法
  177. {
  178.     BiThrNode *p;
  179.     p=T->lchild;//p指向根节点
  180.     while(p!=T)
  181.     {
  182.         while(p->LTag==Link) p=p->lchild;
  183.         if(!Visit(p->data)) return ERROR;
  184.         while(p->RTag==Thread&&p->rchild!=T)
  185.         {
  186.             p=p->rchild;Visit(p->data);//访问后继结点
  187.         }
  188.         p=p->rchild;
  189.     }
  190.     return OK;
  191. }
  192.  
  193. void InThreading(BiThrTree p)//二叉树先线索化函数
  194. {
  195.     BiThrNode *pre;
  196.     if(p)
  197.     {
  198.         InThreading(p->lchild);//左子树线索化
  199.         if(!p->lchild)//前驱线索
  200.         {
  201.             p->LTag=Thread;
  202.             p->lchild=pre;
  203.         }
  204.         if(!pre->rchild)//后继线索
  205.         {
  206.             pre->RTag=Thread;
  207.             p->lchild=p;
  208.         }
  209.         pre=p;//保持pre指向p的前驱
  210.         InThreading(p->rchild);//右子树线索化
  211.     }
  212. }
  213.  
  214. Status InorderThreading(BiThrTree&Thrt,BiThrTree T)//遍历线索化链表
  215. {
  216.     BiThrNode *pre;
  217.     if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)))) exit(OVERFLOW);
  218.     Thrt->LTag=Link;Thrt->RTag=Thread;
  219.     Thrt->rchild=Thrt;
  220.     if(!T) Thrt->lchild=Thrt;
  221.     else{
  222.         Thrt->lchild=T;pre=Thrt;
  223.         InThreading(T);
  224.         pre->rchild=Thrt;pre->RTag=Thread;
  225.         Thrt->rchild=pre;
  226.     }
  227.     return OK;
  228. }
  229.  
  230. Status PreOrderTraversal(BiTree T)//先序遍历的递归算法
  231. {
  232.     if(T)
  233.     {
  234.         printf("%c(%d)",T->data,T->deep);
  235.         PreOrderTraversal(T->lchild);
  236.         PreOrderTraversal(T->rchild);
  237.     }
  238.     return OK;
  239. }
  240.  
  241. Status InOrderTraversal(BiTree T)
  242. {
  243.     if(T)
  244.     {
  245.         InOrderTraversal(T->lchild);
  246.         Visit(T->data);
  247.         InOrderTraversal(T->rchild);
  248.     }
  249.     return OK;
  250. }
  251.  
  252. Status PostOrderTraversal(BiTree T)
  253. {
  254.     if(T)
  255.     {
  256.         PostOrderTraversal(T->lchild);
  257.         PostOrderTraversal(T->rchild);
  258.         Visit(T->data);
  259.     }
  260.     return OK;
  261. }
  262.  
  263. void CountLeaf(BiThrTree T,int &count)//统计叶子结点个数
  264. {
  265.     if(T)
  266.     {
  267.         if((!T->lchild)&&(!T->rchild)) count++;
  268.         CountLeaf(T->lchild,count);
  269.         CountLeaf(T->rchild,count);
  270.     }
  271. }
  272.  
  273. Status BitreeLeafCount(BiTree T)//统计叶子结点个数
  274. {
  275.     if(T==NULL) return 0;
  276.     else{
  277.         if(T->lchild==NULL&&T->rchild==NULL) return 1;
  278.         else return BitreeLeafCount(T->lchild)+BitreeLeafCount(T->rchild);
  279.     }
  280. }
  281.  
  282. Status BitreeCount(BiTree T)//求结点个数
  283. {
  284.     if(T==NULL) return 0;
  285.     else return BitreeCount(T->lchild)+BitreeCount(T->rchild);
  286. }
  287.  
  288. Status ChangeNode(BiTree bt)//交换左右子树
  289. {
  290.     BiTNode*temp;
  291.     if(bt==NULL) return 0;
  292.     ChangeNode(bt->lchild);
  293.     ChangeNode(bt->rchild);
  294.     temp=bt->lchild;
  295.     bt->lchild=bt->rchild;
  296.     bt->rchild=temp;
  297. }
  298.  
  299. int main(){
  300.     BiTree T;
  301.     CreatBiTree_depth(T,1);
  302.     PreOrderTraversal(T);
  303.     return 0;
  304. }

由先序遍历和中序遍历序列建立二叉树，

然后输出该二叉树的后序序列

Sample Input：

        abdcef dbaecf

Hint：

        dbefca

  1. #include<bits/stdc++.h>
  2. #define MAX_TREE_SIZE 100//二叉树的最大结点数
  3. #define OK 1
  4. #define OVERFLOW -2
  5. #define ERROR 0
  6. using namespace std;
  7. //typedef TElemType SqBiTree[MAX_TREE_SIZE];//0号单元存储根节点
  8. //SqBiTree bt;
  9. //typedef int TElemType;
  10. typedef char TElemType;
  11. typedef int Status;
  12.   
  13. /* typedef struct BiTNode{//二叉树的结点
  14.     TElemType data;
  15.     struct BiTNode *lchild,*rchild;//左右孩子指针
  16. }BiTNode,*BiTree; */
  17.  
  18. typedef struct BiTNode{
  19.     TElemType data;
  20.     struct BiTNode *lchild,*rchild,*parent;
  21.     int deep;//结点的深度
  22. }BiTNode,*BiTree;
  23.  
  24. typedef enum PointerTag{Link,Thread};//定义一个枚举类型
  25.  
  26. typedef struct BiThrNode{//线索二叉树的结点
  27.     TElemType data;
  28.     struct BiThrNode *lchild,*rchild;//左右指针
  29.     PointerTag LTag,RTag;//左右标志
  30. }BiThrNode,*BiThrTree;
  31.  
  32. typedef struct BPTNode{
  33.     TElemType data;
  34.     int parent;
  35.     char LRTag;
  36. }BPTNode;
  37.  
  38. typedef struct BPTree{
  39.     BPTNode nodes[MAX_TREE_SIZE];
  40.     int num_node;
  41.     int root;
  42. }BPTree;
  43.  
  44. Status PrintElement(TElemType e)
  45. {   //最简单的Visit()函数
  46.     //调用实例：PreOrderTraverse(T,PrintElement)
  47.     printf("%d ",e);
  48.     return OK;
  49. }
  50.  
  51. Status Visit(TElemType e)
  52. {   
  53.     printf("%c",e);
  54.     return OK;
  55. }
  56.  
  57. Status CreatBiTree(BiTree &T)//按先序次序构建二叉树
  58. {
  59.     TElemType ch;
  60.     scanf("%c",&ch);
  61.     if(ch=='#'||ch=='\n') T=NULL;
  62.     else{
  63.         if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
  64.         T->data=ch;
  65.         CreatBiTree(T->lchild);
  66.         CreatBiTree(T->rchild);
  67.     }
  68.     /* if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
  69.     T->data=ch;//生成根据结点
  70.     CreatBiTree(T->lchild);//构造左子树
  71.     CreatBiTree(T->rchild);//构造右子树 */
  72.     return OK;
  73. }
  74.  
  75. Status CreatBiTree_depth(BiTree &T,int d)//按先序次序构建二叉树,并定义计算每个结点的深度
  76. {
  77.     TElemType ch;
  78.     scanf("%c",&ch);
  79.     if(ch=='#'||ch=='\n') T=NULL;
  80.     else{
  81.         if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
  82.         T->data=ch;T->deep=d;
  83.         CreatBiTree_depth(T->lchild,d+1);
  84.         CreatBiTree_depth(T->rchild,d+1);
  85.     }
  86.     /* if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
  87.     T->data=ch;//生成根据结点
  88.     CreatBiTree(T->lchild);//构造左子树
  89.     CreatBiTree(T->rchild);//构造右子树 */
  90.     return OK;
  91. }
  92.  
  93. void CreatBiTreeP_I(char *pre,char *in,int n)//由先序遍历和中序遍历序列建立二叉树
  94. {
  95.     if(n<=0) return ;
  96.     int len=strchr(in,pre[0])-in;
  97.     CreatBiTreeP_I(pre+1,in,len);
  98.     CreatBiTreeP_I(pre+len+1,in+len+1,n-len-1);
  99.     printf("%c",pre[0]);
  100. }
  101.  
  102. Status BitreeDepth(BiTree T)//求二叉树的深度
  103. {
  104.     int depth,ldepth,rdepth;
  105.     if(T==NULL) depth=0;
  106.     else{
  107.         ldepth=BitreeDepth(T->lchild);
  108.         rdepth=BitreeDepth(T->rchild);
  109.         depth=1+(ldepth>rdepth?ldepth:rdepth);
  110.     }
  111.     return depth;
  112. }
  113.  
  114. /* Status PreOrderTraverse(BiTree T.Status(*Visit)(TElemType e))//先序遍历的递归算法
  115. {   //Visit()是对结点操作的应用函数
  116.     if(T)
  117.     {
  118.         if(Visit(T->data))
  119.             if(PreOrderTraverse(T->lchild.Visit))
  120.                 if(PreOrderTraverse(T->rchild.Visit)) return OK;
  121.         return ERROR;
  122.     }else return OK;
  123. } */
  124.  
  125. /* Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e))//中序遍历的非递归算法
  126. {
  127.     InitStack(S);Push(S,T);//根指针进栈
  128.     while(!StackEmpty(S))
  129.     {
  130.         while(GetTop(S.p)&&p)
  131.         {
  132.             Push(S.p->lchild);//向左走到尽头
  133.         }
  134.         Pop(S.p);//空指针出栈
  135.         if(!StackEmpty(S))
  136.         {
  137.             Pop(S.p);
  138.             if(!Visit(p->data)) return ERROR;
  139.             Push(S.p->rchild); 
  140.         }
  141.     }
  142.     return OK;
  143. } */
  144.  
  145. /* Status InOrderTraverse(BiTree T.Status(*Visit)(TElemType e))
  146. {
  147.     InitStack(S);p=T;
  148.     while(p||StackEmpty(S))
  149.     {
  150.         if(p){
  151.             Push(S,p);
  152.             p=p->lchild;
  153.         }else{
  154.             Pop(S,p);
  155.             if(!Visit(p->data)) return ERROR;
  156.             p=p->rchild;
  157.         }
  158.     }
  159.     return OK;
  160. } */
  161.  
  162. /* BiTNode*GoFarLeft(BiTree ,Stack *S)//找最左边最远的结点
  163. {
  164.     if(!T) return NULL;
  165.     while(T->lchild)
  166.     {
  167.         Push(S,T);
  168.         T=T->lchild;
  169.     }
  170.     return T;
  171. }  */
  172.  
  173. /* void InorderTree(BiTree T,void(*Visit)(TElemType &e))//更清晰的中序遍历的非递归算法
  174. {
  175.     Stack *S;BiTree t,p;p=T->lchild;
  176.     t=GoFarLeft(p,S);
  177.     while(t)
  178.     {
  179.         visit(t->data);
  180.         if(t->rchild) t=GoFarLeft(t->rchild,S);
  181.         else if(!StackEmpty(S)) t=Pop(S);
  182.         else t=NULL;
  183.     }
  184. } */
  185.  
  186. Status InOrderTraverse_Thr(BiThrTree T,Status(*Visit)(TElemType e))//以双向线索链表为存储结构时对二叉树进行遍历的算法
  187. {
  188.     BiThrNode *p;
  189.     p=T->lchild;//p指向根节点
  190.     while(p!=T)
  191.     {
  192.         while(p->LTag==Link) p=p->lchild;
  193.         if(!Visit(p->data)) return ERROR;
  194.         while(p->RTag==Thread&&p->rchild!=T)
  195.         {
  196.             p=p->rchild;Visit(p->data);//访问后继结点
  197.         }
  198.         p=p->rchild;
  199.     }
  200.     return OK;
  201. }
  202.  
  203. void InThreading(BiThrTree p)//二叉树先线索化函数
  204. {
  205.     BiThrNode *pre;
  206.     if(p)
  207.     {
  208.         InThreading(p->lchild);//左子树线索化
  209.         if(!p->lchild)//前驱线索
  210.         {
  211.             p->LTag=Thread;
  212.             p->lchild=pre;
  213.         }
  214.         if(!pre->rchild)//后继线索
  215.         {
  216.             pre->RTag=Thread;
  217.             p->lchild=p;
  218.         }
  219.         pre=p;//保持pre指向p的前驱
  220.         InThreading(p->rchild);//右子树线索化
  221.     }
  222. }
  223.  
  224. Status InorderThreading(BiThrTree&Thrt,BiThrTree T)//遍历线索化链表
  225. {
  226.     BiThrNode *pre;
  227.     if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)))) exit(OVERFLOW);
  228.     Thrt->LTag=Link;Thrt->RTag=Thread;
  229.     Thrt->rchild=Thrt;
  230.     if(!T) Thrt->lchild=Thrt;
  231.     else{
  232.         Thrt->lchild=T;pre=Thrt;
  233.         InThreading(T);
  234.         pre->rchild=Thrt;pre->RTag=Thread;
  235.         Thrt->rchild=pre;
  236.     }
  237.     return OK;
  238. }
  239.  
  240. Status PreOrderTraversal(BiTree T)//先序遍历的递归算法
  241. {
  242.     if(T)
  243.     {
  244.         printf("%c(%d)",T->data,T->deep);
  245.         PreOrderTraversal(T->lchild);
  246.         PreOrderTraversal(T->rchild);
  247.     }
  248.     return OK;
  249. }
  250.  
  251. Status InOrderTraversal(BiTree T)
  252. {
  253.     if(T)
  254.     {
  255.         InOrderTraversal(T->lchild);
  256.         Visit(T->data);
  257.         InOrderTraversal(T->rchild);
  258.     }
  259.     return OK;
  260. }
  261.  
  262. Status PostOrderTraversal(BiTree T)
  263. {
  264.     if(T)
  265.     {
  266.         PostOrderTraversal(T->lchild);
  267.         PostOrderTraversal(T->rchild);
  268.         Visit(T->data);
  269.     }
  270.     return OK;
  271. }
  272.  
  273. void CountLeaf(BiThrTree T,int &count)//统计叶子结点个数
  274. {
  275.     if(T)
  276.     {
  277.         if((!T->lchild)&&(!T->rchild)) count++;
  278.         CountLeaf(T->lchild,count);
  279.         CountLeaf(T->rchild,count);
  280.     }
  281. }
  282.  
  283. Status BitreeLeafCount(BiTree T)//统计叶子结点个数
  284. {
  285.     if(T==NULL) return 0;
  286.     else{
  287.         if(T->lchild==NULL&&T->rchild==NULL) return 1;
  288.         else return BitreeLeafCount(T->lchild)+BitreeLeafCount(T->rchild);
  289.     }
  290. }
  291.  
  292. Status BitreeCount(BiTree T)//求结点个数
  293. {
  294.     if(T==NULL) return 0;
  295.     else return BitreeCount(T->lchild)+BitreeCount(T->rchild);
  296. }
  297.  
  298. Status ChangeNode(BiTree bt)//交换左右子树
  299. {
  300.     BiTNode*temp;
  301.     if(bt==NULL) return 0;
  302.     ChangeNode(bt->lchild);
  303.     ChangeNode(bt->rchild);
  304.     temp=bt->lchild;
  305.     bt->lchild=bt->rchild;
  306.     bt->rchild=temp;
  307. }
  308.  
  309. char a[100005],b[100005];
  310. int main(){
  311.     while(~scanf("%s%s",a,b))
  312.     {
  313.         CreatBiTreeP_I(a,b,strlen(a));
  314.         printf("\n");
  315.     }
  316.     return 0;
  317. }

建立中序线索二叉树

并按中序遍历该二叉树

Sample Input:

        ABD##E##C##

Sample Output:

        DBEAC

  1. #include<bits/stdc++.h>
  2. #define MAX_TREE_SIZE 100//二叉树的最大结点数
  3. #define OK 1
  4. #define OVERFLOW -2
  5. #define ERROR 0
  6. using namespace std;
  7. //typedef TElemType SqBiTree[MAX_TREE_SIZE];//0号单元存储根节点
  8. //SqBiTree bt;
  9. //typedef int TElemType;
  10. typedef char TElemType;
  11. typedef int Status;
  12.   
  13. /* typedef struct BiTNode{//二叉树的结点
  14.     TElemType data;
  15.     struct BiTNode *lchild,*rchild;//左右孩子指针
  16. }BiTNode,*BiTree; */
  17.  
  18. typedef struct BiTNode{//二叉树的结点
  19.     TElemType data;
  20.     struct BiTNode *lchild,*rchild,*parent;
  21.     int deep;//结点的深度
  22. }BiTNode,*BiTree;
  23.  
  24. typedef enum PointerTag{Link,Thread};//定义一个枚举类型
  25.  
  26. typedef struct BiThrNode{//线索二叉树的结点
  27.     TElemType data;
  28.     struct BiThrNode *lchild,*rchild;//左右指针
  29.     PointerTag LTag,RTag;//左右标志
  30. }BiThrNode,*BiThrTree;
  31.  
  32. typedef struct BPTNode{
  33.     TElemType data;
  34.     int parent;
  35.     char LRTag;
  36. }BPTNode;
  37.  
  38. typedef struct BPTree{
  39.     BPTNode nodes[MAX_TREE_SIZE];
  40.     int num_node;
  41.     int root;
  42. }BPTree;
  43.  
  44. Status PrintElement(TElemType e)
  45. {   //最简单的Visit()函数
  46.     //调用实例：PreOrderTraverse(T,PrintElement)
  47.     printf("%d ",e);
  48.     return OK;
  49. }
  50.  
  51. Status Visit(TElemType e)
  52. {   
  53.     printf("%c",e);
  54.     return OK;
  55. }
  56.  
  57. Status CreatBiTree(BiTree &T)//按先序次序构建二叉树
  58. {
  59.     TElemType ch;
  60.     scanf("%c",&ch);
  61.     if(ch=='#'||ch=='\n') T=NULL;
  62.     else{
  63.         if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
  64.         T->data=ch;
  65.         CreatBiTree(T->lchild);
  66.         CreatBiTree(T->rchild);
  67.     }
  68.     /* if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
  69.     T->data=ch;//生成根据结点
  70.     CreatBiTree(T->lchild);//构造左子树
  71.     CreatBiTree(T->rchild);//构造右子树 */
  72.     return OK;
  73. }
  74.  
  75. Status CreatBiTree_depth(BiTree &T,int d)//按先序次序构建二叉树,并定义计算每个结点的深度
  76. {
  77.     TElemType ch;
  78.     scanf("%c",&ch);
  79.     if(ch=='#'||ch=='\n') T=NULL;
  80.     else{
  81.         if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
  82.         T->data=ch;T->deep=d;
  83.         CreatBiTree_depth(T->lchild,d+1);
  84.         CreatBiTree_depth(T->rchild,d+1);
  85.     }
  86.     /* if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
  87.     T->data=ch;//生成根据结点
  88.     CreatBiTree(T->lchild);//构造左子树
  89.     CreatBiTree(T->rchild);//构造右子树 */
  90.     return OK;
  91. }
  92.  
  93. void CreatBiTreeP_I(char *pre,char *in,int n)//由先序遍历和中序遍历序列建立二叉树
  94. {
  95.     if(n<=0) return ;
  96.     int len=strchr(in,pre[0])-in;
  97.     CreatBiTreeP_I(pre+1,in,len);
  98.     CreatBiTreeP_I(pre+len+1,in+len+1,n-len-1);
  99.     printf("%c",pre[0]);
  100. }
  101.  
  102. void Creat_BiThrTree(BiThrNode* &T)//按照先序序列构造线索二叉树
  103. {
  104.     char ch;scanf("%c",&ch);
  105.     if(ch=='#'||ch=='\n') T=NULL;
  106.     else{
  107.         T=(BiThrNode*)malloc(sizeof(BiThrNode));
  108.         if(!T) exit(OVERFLOW);
  109.         T->data=ch;//生成根结点
  110.         Creat_BiThrTree(T->lchild);//递归构造左子树
  111.         if(T->lchild) T->LTag=Link;//有左孩子
  112.         Creat_BiThrTree(T->rchild);//递归构造右子树
  113.         if(T->rchild) T->RTag=Link;//有右孩子
  114.     }
  115. }
  116.  
  117. Status BitreeDepth(BiTree T)//求二叉树的深度
  118. {
  119.     int depth,ldepth,rdepth;
  120.     if(T==NULL) depth=0;
  121.     else{
  122.         ldepth=BitreeDepth(T->lchild);
  123.         rdepth=BitreeDepth(T->rchild);
  124.         depth=1+(ldepth>rdepth?ldepth:rdepth);
  125.     }
  126.     return depth;
  127. }
  128.  
  129. /* Status PreOrderTraverse(BiTree T.Status(*Visit)(TElemType e))//先序遍历的递归算法
  130. {   //Visit()是对结点操作的应用函数
  131.     if(T)
  132.     {
  133.         if(Visit(T->data))
  134.             if(PreOrderTraverse(T->lchild.Visit))
  135.                 if(PreOrderTraverse(T->rchild.Visit)) return OK;
  136.         return ERROR;
  137.     }else return OK;
  138. } */
  139.  
  140. /* Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e))//中序遍历的非递归算法
  141. {
  142.     InitStack(S);Push(S,T);//根指针进栈
  143.     while(!StackEmpty(S))
  144.     {
  145.         while(GetTop(S.p)&&p)
  146.         {
  147.             Push(S.p->lchild);//向左走到尽头
  148.         }
  149.         Pop(S.p);//空指针出栈
  150.         if(!StackEmpty(S))
  151.         {
  152.             Pop(S.p);
  153.             if(!Visit(p->data)) return ERROR;
  154.             Push(S.p->rchild); 
  155.         }
  156.     }
  157.     return OK;
  158. } */
  159.  
  160. void ThInOrder(BiThrNode*T)//中序遍历线索二叉树的非递归算法
  161. {
  162.     BiThrNode *p=T->lchild;//p指向根结点
  163.     while(p!=T)
  164.     {
  165.         while(p->LTag==Link)
  166.         {
  167.             p=p->lchild;//找开始结点
  168.         }
  169.         printf("%c",p->data);//访问开始结点
  170.         while(p->RTag==Thread&&p->rchild!=T)
  171.         {
  172.             p=p->rchild;
  173.             printf("%c",p->data);
  174.         }
  175.         p=p->rchild;
  176.     }
  177. }
  178.  
  179. /* BiTNode*GoFarLeft(BiTree ,Stack *S)//找最左边最远的结点
  180. {
  181.     if(!T) return NULL;
  182.     while(T->lchild)
  183.     {
  184.         Push(S,T);
  185.         T=T->lchild;
  186.     }
  187.     return T;
  188. }  */
  189.  
  190. /* void InorderTree(BiTree T,void(*Visit)(TElemType &e))//更清晰的中序遍历的非递归算法
  191. {
  192.     Stack *S;BiTree t,p;p=T->lchild;
  193.     t=GoFarLeft(p,S);
  194.     while(t)
  195.     {
  196.         visit(t->data);
  197.         if(t->rchild) t=GoFarLeft(t->rchild,S);
  198.         else if(!StackEmpty(S)) t=Pop(S);
  199.         else t=NULL;
  200.     }
  201. } */
  202.  
  203. Status InOrderTraverse_Thr(BiThrTree T,Status(*Visit)(TElemType e))//以双向线索链表为存储结构时对二叉树进行遍历的算法
  204. {
  205.     BiThrNode *p;
  206.     p=T->lchild;//p指向根节点
  207.     while(p!=T)
  208.     {
  209.         while(p->LTag==Link) p=p->lchild;
  210.         if(!Visit(p->data)) return ERROR;
  211.         while(p->RTag==Thread&&p->rchild!=T)
  212.         {
  213.             p=p->rchild;Visit(p->data);//访问后继结点
  214.         }
  215.         p=p->rchild;
  216.     }
  217.     return OK;
  218. }
  219.  
  220. BiThrNode *pre;//全局变量，始终指向刚刚访问过的结点 
  221. void InThreading(BiThrNode* &p)//中序遍历并进行中序线索化
  222. {
  223.     if(p!=NULL)
  224.     {
  225.         InThreading(p->lchild);//左子树线索化
  226.         if(p->lchild==NULL)//前驱线索
  227.         {
  228.             p->lchild=pre;
  229.             p->LTag=Thread;
  230.         }else p->LTag=Link;
  231.  
  232.         if(pre->rchild==NULL)//后继线索
  233.         {
  234.             pre->rchild=p;
  235.             pre->RTag=Thread;
  236.         }else pre->RTag=Link;
  237.  
  238.         pre=p;//保持pre指向p的前驱
  239.         InThreading(p->rchild);//右子树线索化
  240.     }
  241. }
  242.  
  243. BiThrNode*Creat_BiThrTree_Thread(BiThrNode* &T)//中序遍历二叉树T，并将其中序线索化，root指向头结点
  244. {
  245.     BiThrNode*root;
  246.     root=(BiThrNode*)malloc(sizeof(BiThrNode));
  247.     if(!root) exit(OVERFLOW);
  248.     root->LTag=Link;
  249.     root->RTag=Thread;
  250.     root->rchild=root;
  251.     if(T==NULL) root->lchild=root;
  252.     else{
  253.         root->lchild=T;
  254.         pre=root;
  255.         InThreading(T);
  256.         pre->rchild=root;
  257.         pre->RTag=Thread;
  258.         root->rchild=pre;
  259.     }
  260.     return root;
  261. }
  262.  
  263. Status InorderThreading(BiThrTree&Thrt,BiThrTree T)//中序遍历线索化链表
  264. {
  265.     BiThrNode *pre;
  266.     if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)))) exit(OVERFLOW);
  267.     Thrt->LTag=Link;Thrt->RTag=Thread;
  268.     Thrt->rchild=Thrt;
  269.     if(!T) Thrt->lchild=Thrt;
  270.     else{
  271.         Thrt->lchild=T;pre=Thrt;
  272.         InThreading(T);
  273.         pre->rchild=Thrt;pre->RTag=Thread;
  274.         Thrt->rchild=pre;
  275.     }
  276.     return OK;
  277. }
  278.  
  279. Status PreOrderTraversal(BiTree T)//先序遍历的递归算法
  280. {
  281.     if(T)
  282.     {
  283.         printf("%c(%d)",T->data,T->deep);
  284.         PreOrderTraversal(T->lchild);
  285.         PreOrderTraversal(T->rchild);
  286.     }
  287.     return OK;
  288. }
  289.  
  290. Status InOrderTraversal(BiTree T)
  291. {
  292.     if(T)
  293.     {
  294.         InOrderTraversal(T->lchild);
  295.         Visit(T->data);
  296.         InOrderTraversal(T->rchild);
  297.     }
  298.     return OK;
  299. }
  300.  
  301. Status PostOrderTraversal(BiTree T)
  302. {
  303.     if(T)
  304.     {
  305.         PostOrderTraversal(T->lchild);
  306.         PostOrderTraversal(T->rchild);
  307.         Visit(T->data);
  308.     }
  309.     return OK;
  310. }
  311.  
  312. void CountLeaf(BiThrTree T,int &count)//统计叶子结点个数
  313. {
  314.     if(T)
  315.     {
  316.         if((!T->lchild)&&(!T->rchild)) count++;
  317.         CountLeaf(T->lchild,count);
  318.         CountLeaf(T->rchild,count);
  319.     }
  320. }
  321.  
  322. Status BitreeLeafCount(BiTree T)//统计叶子结点个数
  323. {
  324.     if(T==NULL) return 0;
  325.     else{
  326.         if(T->lchild==NULL&&T->rchild==NULL) return 1;
  327.         else return BitreeLeafCount(T->lchild)+BitreeLeafCount(T->rchild);
  328.     }
  329. }
  330.  
  331. Status BitreeCount(BiTree T)//求结点个数
  332. {
  333.     if(T==NULL) return 0;
  334.     else return BitreeCount(T->lchild)+BitreeCount(T->rchild);
  335. }
  336.  
  337. Status ChangeNode(BiTree bt)//交换左右子树
  338. {
  339.     BiTNode*temp;
  340.     if(bt==NULL) return 0;
  341.     ChangeNode(bt->lchild);
  342.     ChangeNode(bt->rchild);
  343.     temp=bt->lchild;
  344.     bt->lchild=bt->rchild;
  345.     bt->rchild=temp;
  346. }
  347.  
  348. /* void AllPath(BiTree T,Stack &S)//输出二叉树上从根到所有叶子结点的路径
  349. {
  350.     if(T)
  351.     {
  352.         Push(S,T->data);
  353.         if(!T->lchild&&!T->rchild) PrintStack(S);
  354.         else{
  355.             AllPath(T->lchild,S);
  356.             AllPath(T->rchild,S);
  357.         }
  358.         Pop(S);
  359.     }
  360. } */
  361.  
  362. /* void OutPath(BiTree T,Stack&S)//输出树中所有从跟到叶的路径
  363. {
  364.     while(T)
  365.     {
  366.         Push(S,T->data);
  367.         if(!T->firstchild) Printstack(S);
  368.         else OutPath(T->first,S);
  369.         Pop(S);
  370.         T=T->nextsibling;
  371.     }
  372. } */
  373.  
  374. int main(){
  375.     BiThrNode *root,*b;
  376.     Creat_BiThrTree(b);
  377.     root=Creat_BiThrTree_Thread(b);
  378.     ThInOrder(root);
  379.     return 0;
  380. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小丑西瓜9/article/detail/592545
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号