# 二叉树（链表形式）

0
8

```  1 #include<iostream>
2 #include<malloc.h>
3 #define int long long
4 #define maxsize 100
5 using namespace std;
6 typedef char DataType;
7 typedef struct BiNode
8 {
9     DataType data;
10     struct BiNode *lchild,*rchild;
11 }BiNode;
12
13 //建立二叉树（建立扩展二叉树）
14 BiNode *CreatBiTree(BiNode *root)
15 {
16     char ch;
17     cin >> ch;
18     if(ch == '#')
19         root = NULL;
20     else
21     {
22         root = (BiNode *)malloc(sizeof(BiNode));
23         root->data = ch;
24         root->lchild = CreatBiTree(root->lchild);
25         root->rchild = CreatBiTree(root->rchild);
26     }
27     return root;
28 }
29
30 //前序遍历二叉树
31 void PreOrder(BiNode *root)
32 {
33     if(root == NULL)
34         return ;
35     else
36     {
37         cout << root->data << " ";
38         PreOrder(root->lchild);
39         PreOrder(root->rchild);
40     }
41 }
42
43 //中序遍历二叉树
44 void InOrder(BiNode *root)
45 {
46     if(root == NULL)
47         return ;
48     else
49     {
50         InOrder(root->lchild);
51         cout << root->data << " ";
52         InOrder(root->rchild);
53     }
54 }
55
56 //后序遍历二叉树
57 void PostOrder(BiNode *root)
58 {
59     if(root == NULL)
60         return ;
61     else
62     {
63         PostOrder(root->lchild);
64         PostOrder(root->rchild);
65         cout << root->data << " ";
66     }
67 }
68
69 //层序遍历二叉树
70 void LevelOrder(BiNode *root)
71 {
72     BiNode *q = NULL,*Q[maxsize];
73     int front = -1;
74     int rear = -1;
75     if(root == NULL)
76         return ;
77     Q[rear++] = root;
78     while(front != rear)
79     {
80         q = Q[front++];
81         cout << q->data << " ";
82         if(q->lchild != NULL)
83             Q[rear++] = q->lchild;
84         if(q->rchild != NULL)
85             Q[rear++] = q->rchild;
86     }
87 }
88
89 //销毁二叉树
90 void DestoryBiTree(BiNode *root)
91 {
92     if(root == NULL)
93         return ;
94     DestoryBiTree(root->lchild);
95     DestoryBiTree(root->rchild);
96     free(root);
97 }
98
99 signed main()
100 {
101     BiNode *root = NULL;
102     root = CreatBiTree(root);
103     cout << "该二叉树的根节点是：" << root->data;
104
105     cout << endl << "该二叉树的前序遍历序列是：";
106     PreOrder(root);
107
108     cout << endl << "该二叉树的中序遍历序列是：";
109     InOrder(root);
110
111     cout << endl << "该二叉树的后序遍历序列是：";
112     PostOrder(root);
113
114     cout << endl << "该二叉树的层序遍历序列是：";
115     LevelOrder(root);
116
117     DestoryBiTree(root);
118
119     return 0;
120 }```

<