(1) 二叉树的链表存储法! struct node { int value; node *leftchild, *rightchild; //int id; // 结点编号。 | | | | | } arr[N]; int top=-1; node * head = NULL; #define NEW(p) p=&arr[ p-> | ++top]; p->leftchild=NULL; rightchild=NULL; p->value=0 | |
(2) 完全二叉树的一维数组存储法! file:///C:/Users/123/AppData/Local/Temp/ksohtml11960/wps11.png 如果一个二叉树的结点严格按照从上到下、从左到右的顺序填充,就可以用一个一维数组保存。 下面假设这个树有 n 个结点,待操作的结点是 r(0≤r<n)。 操作 | | | | | file:///C:/Users/123/AppData/Local/Temp/ksohtml11960/wps12.jpg | | | | | | | | | | | | | | |
(3) 二叉树的遍历! 1. 前序遍历 void preorder(node *p) { if (p==NULL) return; // 处理结点p cout<<p->value<<' '; preorder(p->leftchild); preorder(p->rightchild); } 2. 中序遍历 void inorder(node *p) { if (p==NULL) return; inorder(p->leftchild); // 处理结点p cout<<p->value<<' '; inorder(p->rightchild); } |
3. 后序遍历 void postorder(node *p) { if (p==NULL) return; postorder(p->leftchild); postorder(p->rightchild); // 处理结点p cout<<p->value<<' '; } |
假如二叉树是通过动态内存分配建立起来的,在释放内存空间时应该使用后序遍历。 4. 宽度优先遍历(BFS)首先访问根结点,然后逐个访问第一层的结点,接下来逐个访问第二层的结点…… node *q[N]; void BFS(node *p) { if (p==NULL) return; int front=1,rear=2; q[1]=p; while (front<rear) { node *t = q[front++]; // 处理结点t cout<<t->value<<' '; if (t->leftchild!=NULL) q[rear++]=t->leftchild; if (t->rightchild!=NULL) q[rear++]=t->rightchild; } } |
对于完全二叉树,可以直接遍历: for (int i=0; i<n; i++) cout<<a<<' '; (4) 二叉树重建 【问题描述】二叉树的遍历方式有三种:前序遍历、中序遍历和后序遍历。现在给出其中两种遍历的结果,请输出第三种遍历的结果。 【分析】 前序遍历的第一个元素是根,后序遍历的最后一个元素也是根。所以处理时需要到中序遍历中找根,然后递归求出树。 注意!输出之前须保证字符串的最后一个字符是'\0'。 1. 中序+后序→前序 void preorder(int n, char *pre, char *in, char *post) { if (n<=0) return; int p=strchr(in, post[n-1])-in; pre[0]=post[n-1]; preorder(p, pre+1, in, post); preorder(n-p-1, pre+p+1, in+p+1, post+p); } |
2. 前序+中序→后序 void postorder(int n, char *pre, char *in, char *post) { if (n<=0) return; int p=strchr(in, pre[0])-in; postorder(p, pre+1, in, post); postorder(n-p-1, pre+p+1, in+p+1, post+p); post[n-1]=pre[0]; } |
3. 前序+后序→中序 “中+前”和“中+后”都能产生唯一解,但是“前+后”有多组解。下面输出其中一种。 bool check(int n, char *pre, char *post) // 判断pre、post是否属于同一棵二叉树 { bool b; for (int i=0; i<n; i++) { b=false; for (int j=0; j<n; j++) if (pre==post[j]) { b=true; break; } if (!b) return false; } return true; } void inorder(int n, char *pre, char *in, char *post) { if (n<=0) return; int p=1; while (check(p, pre+1, post)==false && p<n) p++; if (p>=n) p=n-1; // 此时,如果再往inorder里传p,pre已经不含有效字符了。 inorder(p, pre+1, in, post); in[p]=pre[0]; inorder(n-p-1, pre+p+1, in+p+1, post+p); } |
(5) 求二叉树的直径* 从任意一点出发,搜索距离它最远的点,则这个最远点必定在树的直径上。再搜索这个最远点的最远点,这两个最远点的距离即为二叉树的直径。 求树、图(连通图)的直径的思想是相同的。 // 结点编号从1开始,共n个结点。 struct node { int v; node *parent, *leftchild, *rightchild; } a[1001], *p; int maxd; bool T[1003]; #define t(x) T[((x)==NULL)?0 ![](static/image/smiley/default/sad.gif) (x)-a+1)] | node *p; void DFS(node * x, int l) { if (l>maxd) maxd=l, p=x; if (x==NULL) return; t(x)=false; if (t(x->parent)) DFS(x->parent, l+1); if (t(x->leftchild)) DFS(x->leftchild, l+1); if (t(x->rightchild)) DFS(x->rightchild, l+1); } int distance(node *tree) // tree已经事先读好 { maxd=0; memset(T, 0, sizeof(T)); for (int i=1; i<=n; i++) T=true; DFS(tree,0); maxd=0; memset(T, 0, sizeof(T)); for (int i=1; i<=n; i++) T=true; DFS(p,0); return maxd; } |
|