1 链表
#include#include typedef struct node { int data; struct node * lchild; struct node * rchild; }node; void Init(node *t) { t = NULL; } node * Insert(node *t , int key) { if(t == NULL) { node * p; p = (node *)malloc(sizeof(node)); p->data = key; p->lchild = NULL; p->rchild = NULL; t = p; } else { if(key < t->data) t->lchild = Insert(t->lchild, key); else t->rchild = Insert(t->rchild, key); } return t; //important! } node * creat(node *t) { int i, n, key; scanf("%d", &n); for(i = 0; i < n; i++) { scanf("%d", &key); t = Insert(t, key); } return t; } void InOrder(node * t) //中序遍历输出 { if(t != NULL) { InOrder(t->lchild); printf("%d ", t->data); InOrder(t->rchild); } } int main() { node * t = NULL; t = creat(t); InOrder(t); return 0; }
2 数组
#include#include #define N 1000 int l[N], r[N], key[N], flag, root; void insert(int index, int x) { if(x <= key[index]) { if(l[index] == -1) l[index] = flag; else insert(l[index], x); } else { if(r[index] == -1) r[index] = flag; else insert(r[index], x); } } void InOrder(int index) { if(l[index] != -1) InOrder(l[index]); printf("%d ", key[index]); if(r[index] != -1) InOrder(r[index]); } int main() { int i, x, n; memset(l, -1, sizeof(l)); memset(r, -1, sizeof(r)); scanf("%d", &n); root = -1; flag = 0; for(i = 0; i < n; i++) { scanf("%d", &x); if(root == -1) key[++root] = x; else { key[++flag] = x; insert(root, x); } } InOrder(root); return 0; }
二叉排序树的删除操作
有3种方式：
#include#include #include using namespace::std; typedef struct node { int data; struct node * lchild; struct node * rchild; }node; void Init(node *t) { t = NULL; } node * Insert(node *t , int key) { if(t == NULL) { node * p; p = (node *)malloc(sizeof(node)); p->data = key; p->lchild = NULL; p->rchild = NULL; t = p; } else { if(key < t->data) t->lchild = Insert(t->lchild, key); else t->rchild = Insert(t->rchild, key); } return t; //important! } node * creat(node *t) { int i, n, key; scanf("%d", &n); for(i = 0; i < n; i++) { scanf("%d", &key); t = Insert(t, key); } return t; } void InOrder(node * t) //中序遍历输出 { if(t != NULL) { InOrder(t->lchild); printf("%d ", t->data); InOrder(t->rchild); } } //1.完成节点的删除操作 node * deleteNode1(node *t) { //如果t有左子树 if(t->lchild) { node *r = t->lchild; node *prer = t->lchild; //找到其左子树中最有的节点 while(r->rchild != NULL) { prer = r; r = r->rchild; } //如果r不是t的左孩子 //将r的左孩子作为r的父亲节点prer的右孩子 if(prer != r) { prer->rchild = r->lchild; //被删除节点t的做子树做为r的右子树 r->lchild = t->lchild; } ////被删结点t的右子树作为r的右子树 r->rchild = t->rchild; free(t); return r; } //若t没有左子树，直接用t的右孩子取代它 else { node *q = t->rchild; free(t); return q; } } //2.完成节点的删除操作 node * deleteNode2(node *t) { if(t->lchild) { node *r = t->lchild; while(r->rchild != NULL) { r = r->rchild; } r->rchild = t->rchild; node *q = t->lchild; free(t); return q; } else { node *q = t->rchild; free(t); return q; } } //3.1.完成节点的删除操作 //基本上与第一种情况类似，之不过这次不进行节点指针的移动，而是删 //除“值” node *deleteNode3(node *t) { //如果t有左子树 if(t->lchild) { node *r = t->lchild; node *prer = t->lchild; //找到其左子树中最有的节点 while(r->rchild != NULL) { prer = r; r = r->rchild; } t->data = r->data; if(prer != r) { prer->rchild = r->lchild; } else { t->lchild = r->lchild; } free(r); return t; } //若t没有左子树，直接用t的右孩子取代它 else { node *q = t->rchild; free(t); return q; } } //递归操作，寻找x的合适位置，主要是调用deleteNode()函数 node * Delete(node *t,int x) { if(t) { if(t->data == x) //t = deleteNode1(t); //t = deleteNode2(t); t = deleteNode3(t); else if(t->data > x) t->lchild = Delete(t->lchild,x); else t->rchild = Delete(t->rchild,x); } return t; } int main() { node * t = NULL; t = creat(t); InOrder(t); cout << endl; cout << "要删除的节点是：" << endl; int k; cin >> k ; Delete(t,k); InOrder(t); return 0; }
参考：