欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

二叉树(链表形式)

程序员文章站 2022-11-09 10:50:17
直接附上代码 1 #include 2 #include 3 #define int long long 4 #define maxsize 100 5 using namespace std; 6 typedef char DataType; 7 typed ......

直接附上代码

  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 }

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