二叉树

(1) 二叉树的链表存储法!

struct node {  int value;  node *leftchild, *rightchild; //int id;    // 结点编号。
//node *parent;	// 指向父亲结点。
} 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）。

操作	宏定义		r 的取值范围
r的父亲	file:///C:/Users/123/AppData/Local/Temp/ksohtml11960/wps12.jpg		r≠0
r的左儿子			2r＋1＜n
r的右儿子			2r＋2＜n
r的左兄弟			r 为偶数且0＜r≤n-1
r的右兄弟			r 为奇数且 r＋1＜n
判断r是否为叶子	#define isleaf(r)	((r)>=n/2)	r＜n

(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(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; }