问题来源：《编程之美》3.10 分层遍历二叉树
给定一棵二叉树，要求分层遍历该二叉树，即从上到下按层次访问该树，每一层单独输出一行，每一层要求访问的顺序为从左到右。
我们在遍历的过程中将该层节点的孩子节点压入一个队列，这样就可以实现从上到下一层一层地遍历该二叉树。
C++的程序描述如下：
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
其中BinTree的定义如下：
[cpp]
1.
2.
3.
4.
5.
6.
1、 重建二叉树
已知先序和中序遍历的结果，请重建二叉树。
给定二叉树节点的数据结构如下：
struct node_t{
node_t *nLeft;
node_t *nRight
char value;
}
输入：char *preorder 先序序列
char * midOrder 中序序列
输出：node_t *pRoot 二叉树的根节点
#inlcude
using namespace std;
int num = sizeof(preOrder);//总结点数
node_t *reBuild(char* preOrder, char* midOder,int n){//n为中序遍历节点个数
node_t* ans;
if(n <= 0)
return NULL;
int left;
ans = (struct node_t*)malloc(sizeof(node_t));//新建一个节点
ans->value = *preOrder;
char*t =midOrder;
for(int i=0; i
if(midOrder[i] == *preOder)
break;
)
left = i;//左边的节点
ans->nLeft = reBuild(preOrder+1,midOder,left);
ans->nRight = reBuild(preOder+left+1,midOrder+i+1,n-left-1);
reuturn ans;
}
int main(){
char *preOrder;// 先序序列
char * midOrder;// 中序序列
node_t *pRoot;//二叉树的根节点
pRoot = reBuild(preOrder,midOrder,sizeof(midOrder));
return 0;
}
求二叉树中节点的最大距离
分类： 数据结构2012-10-24 15:36 5382人阅读 评论(1) 收藏 举报
问题来源：《编程之美》3.8 求二叉树节点的最大距离
如果把二叉树看成一个图，父子节点之间的连线看成是双向的，我们姑且定义"距离"为两个节点之间的个数。
写一个程序求一棵二叉树中相距最远的两个节点之间的距离。
如下图所示，粗箭头的边表示最长距离：
树中相距最远的两个节点是A, B
分析可知：对于二叉树，若要两个节点U，V相距最远，有两种情况：
1，从U节点到V节点之间的路径经过根节点
2，从U节点到V节点之间的路径不经过根节点，这种情况下，U，V节点必定在根节点的左子树或者右子树上，这样就转化为求以根节点的孩子节点为根节点的二叉树中最远的两个节点间的距离
上面所说的经过根节点，是指路径中包含根节点，例如：加入上图中只有左子树FGHA, 那么最长距离的两个节点是F, A，该路径中包含根节点F，也称为经过根节点。
于是我们可以递归求解，按照二叉树的中序遍历方式遍历二叉树，在遍历的过程中寻找相距最远的两个节点。
程序描述如下：
[cpp]
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
int *maxLen中始终存储的是当前两个节点间的最远距离，在遍历的过程中更新。
下面的程序描述是为了测试上面的代码是否正确，包括建立二叉树，销毁二叉树，打印二叉树：
[cpp]
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
求二叉树的深度和宽度
分类： 数据结构2013-10-07 22:52 6149人阅读 评论(5) 收藏 举报
[cpp]
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
运行结果：
#include
#include
#include
using namespace std;
#define MaxSize 100
typedef char ElemType;
typedef struct node
{
ElemType data;//数据类型
struct node *lchild;//指向左孩子
struct node *rchild;//指向右孩子
}BTNode;
void CreateBTNode(BTNode *&b,char *str)//由str串创建二叉链
{
BTNode *St[MaxSize],*p=NULL;
int top=-1,k,j=0;
char ch;
b=NULL;//建立二叉链初始时为空
ch=str[j];
while(ch!='\0')//str未扫描完时循环
{
switch(ch)
{
case'(':top++;St[top]=p;k=1;break;//为左结点
case')':top--;break;
case',':k=2;break;//为右结点
default:p=(BTNode *)malloc(sizeof(BTNode));
p->data=ch;
p->lchild=p->rchild=NULL;
if(b==NULL)//p指向二叉树的根结点
b=p;
else//已建立二叉树根结点
{
switch(k)
{
case 1:St[top]->lchild=p;break;
case 2:St[top]->rchild=p;break;
}
}
}
j++;
ch=str[j];
}
}
void DispBTNode(BTNode *b)//以括号表示法输出二叉树
{
if(b!=NULL)
{
printf(" %c",b->data);
if(b->lchild!=NULL||b->rchild!=NULL)
{
printf("(");
DispBTNode(b->lchild);
if(b->rchild!=NULL) printf(",");
DispBTNode(b->rchild);
printf(")");
}
}
}
void PerOrder(BTNode *b)//先序遍历的递归算法
{
if(b!=NULL)
{
printf(" %c ",b->data);//访问根结点
PerOrder(b->lchild);//递归访问左子树
PerOrder(b->rchild);//递归访问右子树
}
}
void PerOrder1(BTNode *b)//先序遍历的非递归算法
{
BTNode *St[MaxSize],*p;
int top=-1;
if(b!=NULL)
{
top++;//根结点入栈
St[top]=b;
while(top>-1)//桟不为空时循环
{
p=St[top];//退桟并访问该结点
top--;
printf(" %c ",p->data);
if(p->rchild!=NULL)//右孩子入桟
{
top++;
St[top]=p->rchild;
}
if(p->lchild!=NULL)//左孩子入桟
{
top++;
St[top]=p->lchild;
}
}
printf("\n");
}
}
void InOrder(BTNode *b)//中序遍历的递归算法
{
if(b!=NULL)
{
InOrder(b->lchild);//递归访问左子树
printf(" %c ",b->data);//访问根结点
InOrder(b->rchild);//递归访问右子树
}
}
void InOrder1(BTNode *b)//中序遍历的非递归算法
{
BTNode *St[MaxSize],*p;
int top=-1;
if(b!=NULL)
{
p=b;
while(top>-1||p!=NULL)
{
while(p!=NULL)
{
top++;
St[top]=p;
p=p->lchild;
}
if(top>-1)
{
p=St[top];
top--;
printf(" %c ",p->data);
p=p->rchild;
}
}
printf("\n");
}
}
void PostOrder(BTNode *b)//后序遍历的递归算法
{
if(b!=NULL)
{
PostOrder(b->lchild);//递归访问左子树
PostOrder(b->rchild);//递归访问右子树
printf(" %c ",b->data);//访问根结点
}
}
void PostOrder1(BTNode *b)//后序遍历的非递归算法
{
BTNode *St[MaxSize],*p;
int flag,top=-1;//桟指针初值
if(b!=NULL)
{
do
{
while(b!=NULL)//将b的所有左结点入桟
{
top++;
St[top]=b;
b=b->lchild;
}
p=NULL;//p指向当前结点的前一个访问的结点
flag=1;//设置b的访问标记为已访问过
while(top!=-1&&flag)
{
b=St[top];//取出当前的桟顶元素
if(b->rchild==p)//右子树不存在或已被访问,访问之
{
printf(" %c ",b->data);//访问*b结点
top--;
p=b;//p指向刚被访问的结点
}
else
{
b=b->rchild;//指向右子树
flag=0;//设置未被访问的标记
}
}
}while(top!=-1);
printf("\n");
}
}
void TravLevel(BTNode *b)//层次遍历
{
BTNode *Qu[MaxSize];//定义顺序循环队列
int front,rear;//定义队首和队尾指针
front=rear=0;//置队列为空队列
if(b!=NULL)
printf(" %c ",b->data);
rear++;//结点指针进入队列
Qu[rear]=b;
while(rear!=front)//队列不为空
{
front=(front+1)%MaxSize;
b=Qu[front];
if(b->lchild!=NULL)//队头出队列
{
printf(" %c ",b->lchild->data);//输出左孩子，并入队列
rear=(rear+1)%MaxSize;
Qu[rear]=b->lchild;
}
if(b->rchild!=NULL)//输出右孩子，并入队列
{
printf(" %c ",b->rchild->data);
rear=(rear+1)%MaxSize;
Qu[rear]=b->rchild;
}
}
printf("\n");
}
void main()
{
BTNode *b;
CreateBTNode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");
printf(" 二叉树 b:");DispBTNode(b);printf("\n\n");
printf(" 层次遍历序列:");
TravLevel(b);
printf("\n");
printf(" 先序遍历序列:\n");
printf(" 递归算法:");PerOrder(b);printf("\n");
printf(" 非递归算法:");PerOrder1(b);printf("\n");
printf(" 中序遍历序列:\n");
printf(" 递归算法:");InOrder(b);printf("\n");
printf(" 非递归算法:");InOrder1(b);printf("\n");
printf(" 后序遍历序列:\n");
printf(" 递归算法:");PostOrder(b);printf("\n");
printf(" 非递归算法:");PostOrder1(b);printf("\n");
}
输出二叉树中所有从根结点到叶子结点的路径
分类： 数据结构2013-10-07 20:38 3178人阅读 评论(0) 收藏 举报
[cpp]
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
运行结果：
本文来源：https://www.2haoxitong.net/k/doc/ba9ddf704afe04a1b171de68.html
文档为doc格式