二叉树

二叉树

二叉树的相关概念

1.子节点，根节点，兄弟节点，双亲节点 2.度：拥有多少个子节点，0,1,2 3.深度：二叉树的行数 4.满二叉树：节点个数为2^k-1 完全二叉树：最下面那层的右边可以少些节点

二叉树的性质

1.二叉树的第i层最多的节点数为2^(i-1) 2.深度为k的二叉树节点数最多有2^k-1 3.设度为0的节点数个数为n0,度为1的节点数个数为n1，度为2的节点数个数为n2，则节点总数n=n1+n2+n0 又因为节点总数n=孩子节点+根节点=n1+n2*2+1，所以n0=n2+1

树的建立

#include<iostream> using namespace std; #define maxsize 100 typedef char datatype; typedef struct { datatype data; int parent; }ptree; ptree *T[maxsize]; ptree *create() { datatype data; int num; int rear; ptree *root, *s; rear = 0; root = NULL; cin >> data >> num; while (data != '#') { s = NULL; if (data != '0') { s = (ptree*)malloc(sizeof(ptree)); s->data = data; s->parent = num; } T[rear] = s; if (T[rear]->parent == 0)root = T[rear]; rear++; cin >> data >> num; } return root; } int main() { ptree p; p = *create(); return 0; }

二叉树的存储

bitree* createbitree() { char ch; int fornt, rear;//队头和队尾指针 bitree *root, *s; fornt = 1;rear = 0; root = NULL;//置空二叉树 ch = getchar();//输入第一个字符 while (ch != '\n') { s = NULL; if (ch != '@') { s = (bitree*)malloc(sizeof(bitree)); s->data = ch; s->lchild = NULL; s->rchild = NULL; } rear++; Q[rear] = s;//入队 if (rear == 1) root = s; else { if (s && Q[fornt])//孩子节点和双亲节点都存在 if (rear % 2 == 0)Q[fornt]->lchild = s;//rear为偶数，新节点是左孩子 else Q[fornt]->rchild = s;//新节点是右孩子 if (rear % 2 == 1)fornt++;//两个孩子处理完毕出队列 } ch=getchar(); } return root; } bitree *creat() /*建立二叉树的递归算法*/ { bitree *t; int x; scanf("%d", &x); if (x == 0) t = NULL; /*以x=0表示输入结束*/ else { t = (bitree*)malloc(sizeof(bitree));/*动态生成结点t,分别给结点t的数据域、左右孩子域 赋值,给左右孩子域赋值时用到了递归的思想。*/ t->data = x; t->lchild = creat(); t->rchild = creat(); } return t; }

二叉树的遍历

1.前序遍历 （1）访问根节点 （2）遍历左子树 （3）遍历右子树 2.中序遍历 （1）遍历左子树 （2）访问根节点 （3）遍历右子树 3.后序遍历 （1）遍历左子树 （2）遍历右子树 （3）访问根节点

void inorder(bitree *t) /*中序遍历二叉树的递归算法*/ { if (t != NULL) { inorder(t->lchild); printf("M", t->data); inorder(t->rchild); } } void inorderf(bitree *t) /*前序遍历二叉树的递归算法*/ { if (t != NULL) { printf("M", t->data); inorder(t->lchild); inorder(t->rchild); } } void inorderb(bitree *t) /*后序遍历二叉树的递归算法*/ { if (t != NULL) { inorder(t->lchild); inorder(t->rchild); printf("M", t->data); } }

小例子

#include<stdio.h> #include<stdlib.h> #define M 100 typedef struct node /*二叉链表结点结构*/ { int data; /*数据域*/ int rtag, ltag;//用来判断孩子节点是否存在，0是存在，1是不存在 struct node *lchild, *rchild;/*左、右孩子域*/ } bitree; bitree *pre = NULL; bitree *que[M]; /*定义一个指针数组，说明队列中的元素类型为bitree指针类型*/ int front = 0, rear = 0; /*初始化循环队列*/ bitree *creat() /*建立二叉树的递归算法*/ { bitree *t; int x; scanf("%d", &x); if (x == 0) t = NULL; /*以x=0表示输入结束*/ else { t = (bitree*)malloc(sizeof(bitree));/*动态生成结点t,分别给结点t的数据域、左右孩子域 赋值,给左右孩子域赋值时用到了递归的思想。*/ t->data = x; t->lchild = creat(); t->rchild = creat(); } return t; } void inorder(bitree *t) /*中序遍历二叉树的递归算法*/ { if (t != NULL) { inorder(t->lchild); printf("M", t->data); inorder(t->rchild); } } void inorderf(bitree *t) /*前序遍历二叉树的递归算法*/ { if (t != NULL) { printf("M", t->data); inorder(t->lchild); inorder(t->rchild); } } void inorderb(bitree *t) /*后序遍历二叉树的递归算法*/ { if (t != NULL) { inorder(t->lchild); inorder(t->rchild); printf("M", t->data); } } void enqueue(bitree *t) /*把bitree类型的结点*t入队列*/ {if (front != (rear + 1) % M) /*判断队列是否已满*/ { rear = (rear + 1) % M; que[rear] = t; } } bitree *delqueue() { if (front == rear) /*判断队列不为空*/ return NULL; front = (front + 1) % M; return (que[front]); } void levorder(bitree *t) /*层次遍历二叉树的算法，说实话，思想不错*/ { bitree *p; if (t != NULL) { enqueue(t); /*根结点入队*/ while (front != rear) /*当当前队列不为空时*/ { p = delqueue(); printf("M", p->data); if (p->lchild != NULL) enqueue(p->lchild); if (p->rchild != NULL) enqueue(p->rchild); } } } void inthread(bitree *p)//add thread for bitree { if (p != NULL) { inthread(p->lchild); if (p->lchild == NULL) { p->ltag = 1; } else p->ltag = 0; if (p->rchild == NULL) { p->rtag = 1; } else p->rtag = 0; if (pre != NULL)//就是为没有两个孩子的节点找到前趋和后继 { if (pre->rtag == 1) { pre->rchild = p; } if (p->ltag == 1) { p->lchild = pre; } } pre = p; inthread(p->rchild); } } bitree* inordernext(bitree*p)//find next bitree node,this way is good { bitree *q; if (p->rtag == 1)return p->rchild; else { q = p->rchild; while (q->ltag == 0)q = q->lchild; return q; } } void inorderb1(bitree *p) /*后序非遍历二叉树的递归算法*/ { bitree* q, *root1;//root1 记录下根节点位置 root1 = p; if (p != NULL) { while (p->ltag == 0) { p = p->lchild; } do { if (p != root1) printf("M", p->data); if (p->rtag == 1) { p = p->rchild; } else { q = p->rchild; while (q->ltag == 0) { q = q->lchild; } p = q; } } while (p != NULL); printf("M", root1->data); putchar(10); } } void inorderf1(bitree *p) /*前序非遍历二叉树的递归算法*/ { bitree* q, *root1;//root1 记录下根节点位置 root1 = p; if (p != NULL) { printf("M", root1->data); while (p->ltag == 0) { p = p->lchild; } do { if (p != root1) printf("M", p->data); if (p->rtag == 1) { p = p->rchild; } else { q = p->rchild; while (q->ltag == 0) { q = q->lchild; } p = q; } } while (p != NULL); putchar(10); } } void inorder1(bitree *p) /*中序非遍历二叉树的递归算法*/ { bitree* q; if (p != NULL) { while (p->ltag == 0) { p = p->lchild; } do { printf("M", p->data); if (p->rtag == 1) { p = p->rchild; } else { q = p->rchild; while (q->ltag == 0) { q = q->lchild; } p = q; } } while (p != NULL); putchar(10); } } int main() /*主函数*/ { bitree *root; root = creat(); printf("\n中序："); inorder(root); printf("\n后序："); inorderb(root); printf("\n前序："); inorderf(root); putchar(10); inthread(root); printf("\n非遍历中序："); inorder1(root); printf("\n非遍历后序："); inorderb1(root); printf("\n非遍历前序："); inorderf1(root); return 0; }

线索二叉树

#include<iostream> using namespace std; #define maxsize 100 typedef char datatype; typedef struct node { datatype data; int ltag, rtag; struct node* lchild, *rchild; }bitree; bitree *Q[maxsize]; bitree *pre=NULL; bitree* createbitree()//create bitree { char ch; int fornt, rear; bitree *root, *s; fornt = 1;rear = 0; root = NULL; ch = getchar(); while (ch != '\n') { s = NULL; if (ch != '@') { s = (bitree*)malloc(sizeof(bitree)); s->data = ch; s->lchild = NULL; s->rchild = NULL; } rear++; Q[rear] = s; if (rear == 1) root = s; else { if (s && Q[fornt]) if (rear % 2 == 0)Q[fornt]->lchild = s; else Q[fornt]->rchild = s; if (rear % 2 == 1)fornt++; } ch=getchar(); } return root; } bitree *inorderfornt(bitree *p)//find fornt bitree node { bitree *q; if (p->ltag == 1)return p->lchild; else { q = p->lchild; while (q->rtag == 0)q = q->rchild; return q; } } bitree* inordernext(bitree*p)//find next bitree node,this way is good { bitree *q; if (p->rtag == 1)return p->rchild; else { q = p->rchild; while (q->ltag == 0)q = q->lchild; return q; } } void insernode(bitree* add, bitree *p)//在双亲节点和右边的子节点进行插入新元素add,如果子左节点则相反就行 { bitree *s,*s1; s1 = p; int i = 1; int x; cout << "please input the location(insert in this node and right child): \n"; cin >> x; if (s1 != NULL) { while (s1->ltag == 0) { s1 = s1->lchild; } } while (1)//进行插入操作 { if (x == i) { s = inordernext(s1); add->ltag = 1; add->lchild = s1; add->rtag = s1->rtag; add->rchild = s1->rchild; s1->rtag = 0; s1->rchild = add; if (s != NULL&&s->ltag == 1)s->lchild = add; break; } s1 = inordernext(s1);i++; } } void display(bitree*s) { if (s) { display(s->lchild); cout<< s->data; display(s->rchild); } } void inthread(bitree *p)//add thread for bitree { if (p != NULL) { inthread(p->lchild); if (p->lchild == NULL) { p->ltag = 1; } else p->ltag = 0; if (p->rchild == NULL) { p->rtag = 1; } else p->rtag = 0; if (pre != NULL)//就是为没有两个孩子的节点找到前趋和后继 { if (pre->rtag == 1) {pre->rchild = p; } if (p->ltag == 1) {p->lchild = pre; } } pre = p; inthread(p->rchild); } } void inorder(bitree*q)//display bitree { if (q != NULL) { while (q->ltag == 0) { q = q->lchild; } do { cout << q->data; q = inordernext(q); } while (q != NULL); cout << endl; } } void main() { bitree q,q1; int x; q = *createbitree(); display(&q);cout << endl; inthread(&q); inorder(&q); cout << "please input you want to add element:\n"; cin >> q1.data; insernode(&q1, &q); inorder(&q); }

哈弗曼编码

#include<iostream> #include<string> #include <algorithm> using namespace std; #define maxsize 100 typedef char datatype; typedef struct { float weight; int lchild, rchild, parent; }hufmtree; hufmtree T[maxsize]; int boot,nn; void huffman() { int n; int i, j, p1, p2;//记录最小的两个权重的下标值,p1第一小 float small1, small2; cout << "please input the number of weigh:" << endl;cin >> n; nn = n; for (i = 0;i < maxsize;i++) { T[i].lchild = T[i].rchild = T[i].parent = 0; T[i].weight = 0.0; }//进行初始化 for (i = 1;i <=n;i++) { cin >> T[i].weight; }//读入n个数的权值 for (i = n+1;i < maxsize;i++) { p1= 0; p2 = 0; small1 = 1000.0; small2 = 1000.0; for (j = 1;j <i;j++) { //cout <<"date:"<<T[j].weight<<"\tparent:"<< T[j].parent<<" \t"; if (T[j].parent == 0) { if (T[j].weight < small1) { small2 = small1;small1 = T[j].weight;p2 = p1;p1 = j; } else { if (T[j].weight < small2) { small2 = T[j].weight;p2 = j; } } //cout << "minor1:" << small1 << " \tminor2:" << small2<<endl; } } if (small2 == 1000)break; T[p1].parent = i; T[p2].parent = i ; T[i].lchild = p1 ; T[i].rchild = p2 ; T[i].weight = T[p1].weight + T[p2].weight; //cout << p1+1 << p2+1<<" ";cout << T[i].weight;system("pause"); } int x = 1;//为根节点位置赋值 x = T[x].parent; while (T[x].parent != 0) { x = T[x].parent; } boot = x; } void humfcode(int num) { int x=num; string code; x=T[x].parent; while (x != 0) { if (T[x].lchild == num) { code += "0"; } if (T[x].rchild == num) { code += "1"; } num = x;x = T[x].parent; } reverse(code.begin(), code.end()); cout <<endl<< code; } void hufmdecode() { int decode[maxsize]; int x,i; x = boot; cout << "please input code(5 to stop):" << endl; for ( i = 0;i < maxsize;i++) { cin >> decode[i]; if (decode[i] == 5)break; } for (i = 0;i < maxsize;i++) { if (decode[i] == 0) { x = T[x].lchild; } else if (decode[i] == 1) { x = T[x].rchild; } else if (decode[i] == 5)break; } if (T[x].weight == 0) { cout << "Not find this element;" << endl; } else cout << "weight is:"<<T[x].weight << endl; } void displayhufm(int x) { if (T[x].weight!=0)//节点的输入是从0开始的，所以以一个的输入读不出来，需要改进(曼哈树从1开始建立) { if(T[x].lchild!=0)displayhufm(T[x].lchild); cout << T[x].weight << "\t"; if(T[x].rchild!=0)displayhufm(T[x].rchild); } } void main() { int x; do { cout << "\t1.建立哈夫曼树。" << endl; cout << "\t2.输出哈夫曼树。" << endl; cout << "\t3.进行哈夫曼编码。" << endl; cout << "\t4.哈夫曼解码。" << endl; cout << "\t5.退出。" << endl; cout << "请选择：\n"; cin >> x; switch (x) { case 1:huffman();break; case 2:displayhufm(boot);break; case 3: {for (int i = 1;i <=nn;i++) { cout << endl << T[i].weight << "的编码是：";humfcode(i); }cout << endl;break;} case 4: {hufmdecode();} } system("pause"); system("cls"); } while (x != 5); }