树是一种存储结构,可以顺序存储或者链表存储,作业里用的是链表存储。
链表存储的树就像链表的变形,把原来只有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题目要求: 完成BTree Create_BTree(char s[])函数,该函数由字符串s创建一颗二叉树,其中字符串s是仅由‘(’、‘)’、‘,’以及大小写字符构成的二叉树的广义表表示,如A(B(D,),C(E,F(,H))),字符串s以'\0'结尾。#include #include #include #include using namespace std;#define N 100typedef 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;}/*你的代码将被放在此处之后,请完成*/
在刚开始做的时候,自然而然选择了递归
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(),用于判断是否为英文字母,头文件是将以上代码转为伪码:(c++) (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 |
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队列实现还是比较巧妙的,因为第N的节点,肯定是第N-1行所有节点的子节点之和,我们遍历N-1的时候,就顺便把N放入了队列中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(); } }}
队列中的元素 | 执行操作 |
A | root压入队 |
BC | A的子节点(BC)压入队,A出队 |
CD | B的子节点(D)压入队,B出队 |
DEF | C的子节点(EF)压入队,C出队 |
EF | D无子节点入队,D出队 |
F | E无子节点入队,E出队 |
H | F的子节点(H)入队,F出队 |
上面表格应该从右往左看......执行了右边操作以后,队列中剩下来这些元素