二叉树（链表形式）

直接附上代码

  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 }

用顺序表建立的二叉树过于简单，且二叉树的顺序存储结构一般仅适合于存储完全二叉树，这里就不附上代码了