实验三二叉树

树是一种存储结构，可以顺序存储或者链表存储，作业里用的是链表存储。

链表存储的树就像链表的变形，把原来只有next previous 关系的链表改造成类似族谱关系的链表，然后我们生动形象地把这个类似族谱的东东叫做树。

二叉树与树不同的地方在于，二叉树的任意节点，最多只有两个子节点（想象成现在的二胎，左边的哥哥是左孩子，右边的妹妹是右孩子）

二叉树有许多性质，比如对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1

度指的是子节点数

终端节点也叫叶子，度为0，即没有子节点

下面给出证明：

设，n0为度=0的节点的总数，n1为度=1的节点的总数，n2为度=2的节点的总数

显然，总节点数T=n0+n1+n2;

总边数E=总节点数T-1

同时，总边数E=2*n2+n1

综上三式，n2=n0-1;

喂喂喂，道理我都懂，可是歪啥子忽然就冒出总边数E=总结点数T-1 呢？

证明见下图：

实验三二叉树

其他性质有用到再说。

2311，来看题目：（预置代码）

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <cctype>
using namespace std;

#define N 100

typedef char Element;
struct Node
{
    Element data;
    struct Node *lchild;
    struct Node *rchild;
};
typedef struct Node  BTNode;
typedef struct Node * BTree;

BTree Create_BTree(char s[]);

int main()
{
    char s[N];
    BTree root=NULL;
    gets(s);
    root=Create_BTree(s);
   /*   此处由测试代码自动添加，用于测试你所创建的二叉树是否正确，你无需关心具体测试代码*/
    return 0;
}
/*你的代码将被放在此处之后，请完成*/

题目要求：完成BTree Create_BTree(char s[])函数，该函数由字符串s创建一颗二叉树，其中字符串s是仅由‘(’、‘)’、‘,’以及大小写字符构成的二叉树的广义表表示，如A(B(D,),C(E,F(,H)))，字符串s以'\0'结尾。

在刚开始做的时候，自然而然选择了递归

1.读入字符

1.1 发现做不下去了_(:з)∠)_

虽然理论上讲递归是可以做的，但是实际操作时感觉特别繁琐，很难处理（，）三者之间的关系，所以递归就先放一放。

改变思路，扫描字符串，对'('','')''X'进行分类讨论，设立k区分左右子树

BTree NewNode(Element x)
{//这是别人的算法
BTree p = (BTree)malloc(sizeof(BTNode));
p->data = x;
p->lchild = NULL;
p->rchild = NULL;
return p;
}
BTree Create_BTree(char s[])
{
int i, k, top;
BTree path[N], p;
k = 0;
top = -1;
for (i = 0; s[i] != '\0'; i++)
{//A(B(D,),C(E,F(,H)))
switch (s[i])
{
case '(':
path[++top] = p;
k = 1;
break;
case ',':
k = 2;
break;
case ')':
top--;
break;
}
if (isalpha(s[i]))
{// isalpha(),用于判断是否为英文字母，头文件是 <cctype>（c++） <ctype.h>(c)
p = NewNode(s[i]);
if (k == 1)
path[top]->lchild = p;
else if (k == 2)
path[top]->rchild = p;
}
}
return path[0];
}

将以上代码转为伪码：

设置一个标记变量k，初始值为0；
设置一个临时节点p；
设置一个父节点数组path[];
设置一个标记变量top,其值为当前父节点的数组下标;

循环遍历广义表的字符串s；

如果s[i]是左括号：
则设置k为1；
把临时节点p加入path；
由于新加入了节点，所以top++，指向了p。p是接下来输入的节点的父节点。
否则如果s[i]是逗号：
则设置k为2。
否则如果s[i]是右括号：
则表示当前父节点的子孙输入完成
所以top--，指向了爷爷节点
否则如果s[i]是一个字母，用结点p来存储：
建立BTNode保存数据
如果k为1:
p是当前父节点的左孩子 path[top]->lchild=p;
如果k为2:
p是当前父节点的右孩子 path[top]->rchild=p;

（如果k==0，说明p是根节点，只用建立BTNode，进入下一循环就行）

	0		1			0			1				2			1	0	-1
A	(	B	(	D	,	)	,	C	(	E	,	F	(	,	H	)	)	)
	A		B			A			C				F			C	A	null

上面的表格是以A(B(D,),C(E,F(,H)))作为输入时，top值（第一行），path[top]值（第三行）的变化情况，一一对照比较好理解

2313 二叉树的创建II，和上面代码完全一致，把0~lenth改成left~right就行

2314 先序遍历

树的遍历一般通过递归实现。递归给人的感觉是什么呢，好像电影盗梦空间一样：路上走着走着，啪，进入梦境，一阵噼里啪啦以后，哗，退出了梦境，人呢，还是在原地，继续往下走。

void Pre_Order(BTree root)
{
if (root->data >= 'a' && root->data <= 'z' || root->data >= 'A' && root->data <= 'Z')
printf("%c", root->data);
if (root->lchild != NULL)
Pre_Order(root->lchild);
if (root->rchild != NULL)
Pre_Order(root->rchild);
}

结合上面的程序，我们以//A(B(D,),C(E,F(,H)))为例。

实验三二叉树

中序后序，对照上面自己实现一下

2317 层序遍历

层序遍历是什么呢？就是把树从第一行一行行扫描。以A(B(D,),C(E,F(,H)))为例，层序遍历输出的应该是ABCDEFH

一般来说层序遍历都会用队来实现，因为队先进先出的特性和我们 “小行先出” 的需求比较吻合

伪码如下：

if(根节点不空)

把root压入队列

while（队列不空）

输出队首

if(队首的左孩子不空) 把左孩子压入队列

if（队首的右孩子不空）把右孩子压入队列

队首出队

这个伪码和代码基本没差了_(:з」∠)_

void Level_Order(BTree root)
{
queue<BTree> q;
if (root)
{
q.push(root);
while (q.size())
{
printf("%c", q.front()->data);
if (！q.front()->lchild )  q.push(q.front()->lchild);
if (！q.front()->rchild)   q.push(q.front()->rchild);
q.pop();
}
}
}

队列实现还是比较巧妙的，因为第N的节点，肯定是第N-1行所有节点的子节点之和，我们遍历N-1的时候，就顺便把N放入了队列中

队列中的元素	执行操作
A	root压入队
BC	A的子节点（BC）压入队，A出队
CD	B的子节点（D）压入队，B出队
DEF	C的子节点（EF）压入队，C出队
EF	D无子节点入队，D出队
F	E无子节点入队，E出队
H	F的子节点（H）入队，F出队

上面表格应该从右往左看......执行了右边操作以后，队列中剩下来这些元素

秒客网

实验三二叉树

相关文章

实验三 二叉树

相关文章

实验三二叉树