二叉树(链表形式)

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 }

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

<

发布回复

请输入评论!
请输入你的名字