9.5 二叉树C++

struct node
{
int value;
node *leftchild, *rightchild;
//int id; // 结点编号。
//node *parent; // 指向父亲结点。
} arr[N];
int top=-1;
node * head = NULL;
#define NEW(p) p=&arr[++top]; p->leftchild=NULL; 
p->rightchild=NULL; p->value=0

如果一个二叉树的结点严格按照从上到下、从左到右的顺序填充，就可以用一个一维数组保存。
下面假设这个树有 n 个结点，待操作的结点是 r（0≤r＜n）。

 1. 前序遍历

void preorder(node *p)
{
if (p==NULL) return;
// 处理结点p
cout<value<<' ';
preorder(p->leftchild);
preorder(p->rightchild);
}

2. 中序遍历

void inorder(node *p)
{
if (p==NULL) return;
inorder(p->leftchild);
// 处理结点p
cout<value<<' ';
inorder(p->rightchild);
}

3. 后序遍历

void postorder(node *p)
{
if (p==NULL) return;
postorder(p->leftchild);
postorder(p->rightchild);
// 处理结点p
cout<value<<' ';
}

假如二叉树是通过动态内存分配建立起来的，在释放内存空间时应该使用后序遍历。

4. 宽度优先遍历（BFS）
首先访问根结点，然后逐个访问第一层的结点，接下来逐个访问第二层的结点……

node *q[N];
void BFS(node *p)
{
if (p==NULL) return;
int front=1,rear=2;
q[1]=p;
while (frontvalue<<' ';
if (t->leftchild!=NULL) q[rear++]=t->leftchild;
if (t->rightchild!=NULL) q[rear++]=t->rightchild;
}
}

对于完全二叉树，可以直接遍历：

for (int i=0; i 
(4) 二叉树重建 
【问题描述】二叉树的遍历方式有三种：前序遍历、中序遍历和后序遍历。现在给出其中两种遍历的结果，请输出第三种遍历的结果。
 【分析】
 前序遍历的第一个元素是根，后序遍历的最后一个元素也是根。所以处理时需要到中序遍历中找根，然后递归求出树。
 注意！输出之前须保证字符串的最后一个字符是''。
 
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) 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[i]=true;
DFS(tree,0);
maxd=0;
memset(T, 0, sizeof(T));
for (int i=1; i<=n; i++) T[i]=true;
DFS(p,0);
return maxd;
}