二叉树链表C++实现(转)

[cpp] view plaincopy

1. （1）用递归方法创建二叉链表  
2. （2）用递归算法对二叉树进行先序遍历，中序遍历和后序遍历，并输出遍历结果  
3. （3）对二叉树进行层次遍历，并输出遍历序列  
4. （4）求二叉树的深度并输出  
5.   
6.   
7. #include <stdio.h>//头文件  
8. #include <stdlib.h>  
9. #include <malloc.h>  
10. typedef struct BiTNode  
11. {  
12.     char data;  
13.     struct BiTNode *lchild,*rchild;  
14. }   
15. BiTNode,*BiTree;//定义结点类型  
16. typedef struct QNode  
17. {  
18.     BiTNode data;  
19.     struct QNode *next;  
20.    } //定义队列的节点类型  
21. QNode,*QueuePtr;  
22. typedef struct  
23. {  
24.     QueuePtr  front;  
25.     QueuePtr  rear;  
26.  }  
27. LinkQueue;//队列  
28. void InitQueue(LinkQueue *Q)//创建队列  
29. {  
30.     Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));  
31.     Q->front->next=NULL;  
32. }  
33. void EnQueue(LinkQueue *Q,BiTNode e)//将元素入队  
34. {   
35.  QueuePtr p;  
36.    p=(QueuePtr)malloc(sizeof(QNode));//为结点开辟空间  
37.    p->data=e;  
38.    p->next=NULL;  
39.    Q->rear->next=p;  
40.    Q->rear=p;  
41. }  
42. BiTNode DeQueue(LinkQueue *Q)//将元素出列并返回元素的值。  
43. {     
44. BiTNode e;QueuePtr p;  
45.     p=Q->front->next;  
46.     e=p->data;  
47.     Q->front->next=p->next;  
48.     if(Q->rear==p)  
49.     Q->rear=Q->front;  
50.     free(p);//释放节点  
51.     return (e);  
52.   
53. }  
54. int QueueEmpty(LinkQueue *Q)//判断队列是否为空  
55. {  
56.     if(Q->front==Q->rear )  
57.         return 1;  
58.     else  
59.         return 0;  
60. }  
61. BiTree CreateBiTree()//创建树  
62. {  
63.     char p;BiTree T;  
64.     scanf("%c",&p);  
65.     if(p==' ')  
66.         T=NULL;  
67.     else  
68.     {  
69.         T=(BiTNode *)malloc(sizeof(BiTNode));//为结点开辟空间  
70.         T->data=p;  
71.         T->lchild=CreateBiTree();  
72.         T->rchild=CreateBiTree();  
73.     }  
74.     return (T);  
75. }  
76.   
77. void PreOrder(BiTree T)//先序  
78. {  
79.      if(T!=NULL)  
80.    {  
81.        printf("%c",T->data);  
82.       PreOrder(T->lchild);  
83.        PreOrder(T->rchild);  
84.         
85.     }  
86. }  
87. void InOrder(BiTree T)//中序  
88. {  
89.      if(T!=NULL)  
90.    {  
91.        InOrder(T->lchild);  
92.         printf("%c",T->data);  
93.        InOrder(T->rchild);  
94.         
95.     }  
96. }  
97. void PostOrder(BiTree T)//后序  
98. {  
99.      if(T!=NULL)  
100.    {  
101.        PostOrder(T->lchild);  
102.        PostOrder(T->rchild);  
103.        printf("%c",T->data);  
104.     }  
105. }  
106.   
107. void LevelOrder(BiTree T)//层次遍历  
108.  {  
109.     LinkQueue Q; BiTNode p;  
110.     InitQueue(&Q);  
111.     EnQueue(&Q,*T);  
112.     while(!QueueEmpty(&Q))  
113.     {  
114.         p = DeQueue(&Q);  
115.         printf("%c",p.data);  
116.         if(p.lchild!=NULL)  
117.         EnQueue(&Q,*(p.lchild));  
118.         if(p.rchild!=NULL)  
119.         EnQueue(&Q,*(p.rchild));  
120.     }  
121. }  
122. int Depth(BiTree T)/* 深度 */  
123.  {  
124.    int num1,num2;  
125.    if(T==NULL)  
126.    return(0);  
127.    num1=Depth(T->lchild);  
128.    num2=Depth(T->rchild);  
129.    if(num1>num2)  
130.    return(num1+1);  
131.    else  
132.    return(num2+1);  
133.    }  
134. void main()//主函数  
135. {  
136.     BiTree Ta;int num;  
137.     Ta=CreateBiTree();  
138.      printf("先序遍历:");  
139.      printf("\n");  
140.      PreOrder(Ta);  
141.      printf("\n");  
142.      printf("中序遍历:");  
143.      printf("\n");  
144.      InOrder(Ta);  
145.      printf("\n");  
146.      printf("后序遍历:");  
147.      printf("\n");  
148.      PostOrder(Ta);  
149.      printf("\n");  
150.     printf("层次遍历:");  
151.     printf("\n");  
152.     LevelOrder(Ta);  
153.      printf("\n");  
154.      num=Depth(Ta);  
155.      printf("深度为：%d",num);  
156.       
157. }