二叉树(链表形式)
程序员文章站
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 }
用顺序表建立的二叉树过于简单,且二叉树的顺序存储结构一般仅适合于存储完全二叉树,这里就不附上代码了