C++ 实现二叉树的构造，插入，删除，遍历

  1 #ifndef _TOU_H_
  2 #define _TOU_H_
  3 #include <iostream>
  4 #include <cstdlib>
  5 using namespace std;
  6 #define datatype char
  7 void visit(datatype item) 
  8 {
  9     cout << item <<" ";
 10 }
 11 
 12 typedef 
 13 struct node
 14 {
 15     datatype data;
 16     struct node* leftchild;
 17     struct node* rightchild;
 18 }bitreenode;
 19 void initiate(bitreenode**root)//初始化二叉树
 20 {
 21     *root = (bitreenode*)malloc(sizeof(bitreenode));
 22     (*root)->leftchild = NULL;
 23     (*root)->rightchild = NULL;
 24 }
 25 
 26 bitreenode* insertleftnode(bitreenode*curr, datatype x)//向该节点的左子树插入节点
 27 {
 28     if (curr == NULL)
 29     {
 30         return NULL;
 31     }
 32     bitreenode* t = curr->leftchild;//保存原来节点的左子树节点
 33     bitreenode* s = (bitreenode*)malloc(sizeof(bitreenode));
 34     s->data = x;
 35     s->leftchild = t;//新插入节点的左子树为原节点的左子树
 36     s->rightchild = NULL;
 37     
 38     curr->leftchild = s;// 新节点成为curr的左子树
 39     return curr->leftchild;//返回新插入节点的指针
 40 }
 41 
 42 bitreenode* insertrightnode(bitreenode* curr, datatype x)
 43 {
 44     if (curr == NULL)
 45     {
 46         return NULL;
 47     }
 48     bitreenode* t = curr->rightchild;
 49     bitreenode* s = (bitreenode*)malloc(sizeof(bitreenode));
 50     s->data = x;
 51     s->rightchild = t;//新插入节点的右子树为原节点的右子树
 52     s->leftchild = NULL;
 53 
 54     curr->rightchild = s;// 新节点成为curr的左子树
 55     return curr->rightchild;//返回新插入节点的指针
 56 }
 57 
 58 void destroy(bitreenode **root)
 59 {
 60     if ((*root) != NULL && (*root)->leftchild != NULL)
 61         destroy(&(*root));
 62     if ((*root) != NULL && (*root)->rightchild != NULL)
 63         destroy(&(*root)->rightchild);
 64     free(*root);
 65 }
 66 
 67 bitreenode* deletelefttree(bitreenode* curr)
 68 {
 69     if (curr == NULL || curr->leftchild == NULL) {
 70         return NULL;
 71     }
 72     destroy(&curr->leftchild);
 73     curr->leftchild = NULL;
 74     return curr;
 75 }
 76 
 77 bitreenode* deleterighttree(bitreenode* curr)
 78 {
 79     if (curr == NULL || curr->rightchild == NULL)
 80         return NULL;
 81     destroy(&curr->rightchild);
 82     curr->rightchild = NULL;
 83     return curr;
 84 }
 85 
 86 void proorder(bitreenode* t, void visit(datatype item))//前序遍历
 87 {
 88     if (t != NULL) {
 89         visit(t->data);
 90         proorder(t->leftchild, visit);
 91         proorder(t->rightchild, visit);
 92     }
 93 }
 94 
 95 void inorder(bitreenode* t, void visit(datatype item))//中序遍历
 96 {
 97     if (t != NULL) {
 98         inorder(t->leftchild, visit);
 99         visit(t->data);
100         inorder(t->rightchild, visit);
101     }
102 }
103 
104 void postorder(bitreenode* t,void visit(datatype item))//后序遍历
105 {
106     if (t != NULL) {
107         postorder(t->leftchild, visit);
108         postorder(t->rightchild, visit);
109         visit(t->data);
110     }
111 }
112 
113 void printibitree(bitreenode* br, int n)
114 {
115     int i;
116     if (br == NULL)return;//递归出口
117     printibitree(br->rightchild, n + 1);//遍历打印右子树
118     for (int i = 0; i < n; i++)cout << " ";
119     if (n >= 0)
120     {
121         cout << " " << br->data << endl;
122     }
123     printibitree(br->leftchild, n + 1);
124 }
125 #endif

bitreenode.h

 1 #include "tou.h"
 2 #include <iostream>
 3 using namespace std;
 4 int main()
 5 {
 6     bitreenode * root;
 7     initiate(&root);
 8     bitreenode* p, *pp;
 9     p = insertleftnode(root, 'a');
10     p = insertleftnode(p, 'b');
11     p = insertleftnode(p, 'd');
12     p = insertrightnode(p, 'g');
13     p = insertrightnode(root->leftchild, 'c');
14     pp = p;
15     insertrightnode(p, 'e');
16     insertrightnode(pp, 'f');
17     //proorder(root,visit(root->data));
18 
19     cout << "前序遍历:" ;
20     proorder(root->leftchild, visit); cout << endl;
21     cout << "中序遍历:" ;
22     inorder(root->leftchild, visit); cout << endl;
23     cout << "后序遍历:" ;
24     postorder(root->leftchild, visit); cout << endl;
25     
26 
27     system("pause");
28     return 0;
29 }