5.1树和二叉树的定义
5.1.1树的定义
n（n≥0）个结点的有限集合。
当n＝0时，称为空树；
任意一棵非空树满足以下条件：
⑴ 有且仅有一个特定的称为根的结点；
⑵ 当n＞1时，除根结点之外的其余结点被分成m（m>0）个互不相交的有限集合T1,T2,…
,Tm，其中每个集合又是一棵树，并称为这个根结点的子树。
5.1.2树的基本术语
-
结点的度：结点所拥有的子树的个数。
-
树的度：树中各结点度的最大值。
-
叶子结点：度为0的结点，也称为终端结点。
-
分支结点：度不为0的结点，也称为非终端结点。
-
孩子、双亲：树中某结点子树的根结点称为这个结点的孩子结点，这个结点称为它孩子结点的双亲结点；
-
兄弟：具有同一个双亲的孩子结点互称为兄弟。
-
路径：如果树的结点序列n1, n2, …, nk有如下关系：结点ni是ni+1的双亲（1<=i<k），则把n1, n2,…, nk称为一条由n1至nk的路径；路径上经过的边的个数称为路径长度。
-
祖先、子孙：在树中，如果有一条路径从结点x到结点y，那么x就称为y的祖先，而y称为x的子孙。
-
结点所在层数：根结点的层数为1；对其余任何结点，若某结点在第k层，则其孩子结点在第k+1层。
-
树的深度：树中所有结点的最大层数，也称高度。
-
层序编号：将树中结点按照从上层到下层、同层从左到右的次序依次给他们编以从1开始的连续自然数。
-
有序树、无序树：如果一棵树中结点的各子树从左到右是有次序的，称这棵树为有序树；反之，称为无序树。
-
森林：m (m≥0)棵互不相交的树的集合。
5.1.3二叉树的定义
二叉树(Binary Tree)是n(n≥0)个结点所构成的集合，它或为空树(n= 0); 或为非空树，
对于非空树T:
(1) 有且仅有一个称之为根的结点；
(2)除根结点以外的其余结点分为两个互不相交的子集T1和T2, 分别称为T的左子树和右子树，且兀和乃本身又都是二叉树。二叉树与树一样具有递归性质，二叉树与树的区别主要有以下两点：
(1 )二叉树每个结点至多只有两棵子树（即二叉树中不存在度大千2 的结点）；
(2). 二叉树的子树有左右之分，其次序不能任意颠倒。
二叉树的递归定义表明二叉树或为空，或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。由千这两棵子树也是二叉树，则由二叉树的定义，它们也可以是空树
5.2案例引入
案例5.1：数据压缩问题
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
struct Num
{
char ch;
int num;
}an[7000], temp;
void sort1(Num *bn)
{
Num te;
int i, j;
for (j = 0; j<26; j++)
for (i = 0; i < 25; i++)
{
if (bn[i].num < bn[i + 1].num)
{
te = bn[i];
bn[i] = bn[i + 1];
bn[i + 1] = te;
}
}
}
void sort2(Num *bn, int n)
{
Num te;
int i, j;
for (j = 0; j<26; j++)
for (i = 0; i < 25; i++)
{
if (bn[i].ch > bn[i + 1].ch&&bn[i + 1].num > 0)
{
te = bn[i];
bn[i] = bn[i + 1];
bn[i + 1] = te;
}
}
}
typedef struct
{
int weight;
int parent, lchild, rchild;
int vis;
char ch;
char strc[60];
int len;
int num;
}HTNode, *HuffmanTree;
void Select(HuffmanTree &HT, int k, int &s1, int &s2)
{
int i;
HTNode h1, h2;
int t1, t2;
t1 = t2 = 0;
h1 = HT[1];
h1.weight = 999999;
for (i = 1; i <= k; i++)
{
if (HT[i].weight <= h1.weight &&HT[i].vis == 0)
{
h1 = HT[i];
t1 = i;
}
}
h2 = HT[2];
h2.weight = 999999;
for (i = 1; i <= k; i++)
{
if (HT[i].weight <= h2.weight&&t1 != i&&HT[i].vis == 0)
{
h2 = HT[i];
t2 = i;
}
}
if (h1.weight == h2.weight&&HT[t1].num > HT[t2].num)
{
int temp;
temp = t1;
t1 = t2;
t2 = temp;
}
s1 = t1;
s2 = t2;
HT[s1].vis = 1;
HT[s2].vis = 1;
return;
}
void code(HuffmanTree &HT, int len, char str[], int n, char cc)
{
int i;
for (i = 0; i < len - 1; i++)
HT[n].strc[i] = str[i];
HT[n].strc[i] = cc;
HT[n].strc[i + 1] = '\0';
if (HT[n].lchild != 0)
code(HT, len + 1, HT[n].strc, HT[n].lchild, '0');
if (HT[n].rchild != 0)
code(HT, len + 1, HT[n].strc, HT[n].rchild, '1');
}
void CreateHuffmanTree(HuffmanTree &HT, int n, char *str, int n1)
{
int s1, s2;
s1 = s2 = 0;
if (n <= 1)
return;
int m = 2 * n - 1;
HT = new HTNode[m + 1];
for (int i = 1; i <= m; i++)
{
HT[i].parent = 0; HT[i].lchild = 0; HT[i].rchild = 0; HT[i].vis = 0; HT[i].len = 0; HT[i].num = i; HT[i].weight = 0;
}
for (int i = 1; i <= n; i++)
{
HT[i].weight = an[i - 1].num;
HT[i].ch = an[i - 1].ch;
}
for (int i = n + 1; i <= m; i++)
{
Select(HT, i - 1, s1, s2);
HT[s1].parent = i;
HT[s2].parent = i;
HT[i].lchild = s1;
HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
int len = HT[m].len;
HT[m].strc[len] = '1';
if (HT[m].lchild)
code(HT, 1, "", HT[m].lchild, '0');
if (HT[m].rchild)
code(HT, 1, "", HT[m].rchild, '1');
return;
}
int main()
{
HuffmanTree h;
int n, n1;
char str[700], str2[700];
while (cin >> str)
{
if (str[0] == '0'&&str[1] == '\0')
break;
n1 = 0;
for (int i = 0; i < 27; i++)
{
an[i].num = 0;
an[i].ch = 'a' + i;
}
n = strlen(str);
for (int i = 0; i < n; i++)
{
an[str[i] - 'a'].num++;
str2[i] = str[i];
str2[i + 1] = '\0';
}
sort1(an);
for (int i = 0; i < 26; i++)
{
if (an[i].num != 0)
n1++;
}
sort2(an, n1);
CreateHuffmanTree(h, n1, str, n1);
if (n1 == 1)
{
h = new HTNode[3];
h[1].weight = n; h[1].parent = h[1].lchild = h[1].rchild = 0;
h[1].ch = str[0]; h[1].strc[0] = '0'; h[1].strc[1] = '\0';
}
int f = 0;
for (int i = 0; i < 26; i++)
if (an[i].num > 0)
{
f++;
cout << an[i].ch << ":" << an[i].num ;
if (f == n1)
cout << endl;
else
cout << " ";
}
for (int i = 1; i <= 2 * n1 - 1; i++)
{
cout << i << " " << h[i].weight << " " << h[i].parent << " " << h[i].lchild << " " << h[i].rchild << endl;
}
for (int i = 1; i < n1; i++)
cout << h[i].ch << ":" << h[i].strc << " ";
cout << h[n1].ch << ":" << h[n1].strc;
cout << endl;
for (int i = 0; i < n; i++)
{
for (int j = 1; j <= n1; j++)
if (h[j].ch == str[i])
cout << h[j].strc;
}
cout << endl;
cout << str << endl;
for (int i = 1; i <= 2 * n1 - 1; i++)
{
h[i].parent = 0; h[i].lchild = 0; h[i].rchild = 0; h[i].vis = 0; h[i].len = 0; h[i].num = i;
}
}
return 0;
}
案例5.2：利用二叉树求解表达式的值
#include <iostream>
using namespace std;
//定义表达式树
typedef int TreeElemType;
typedef struct TreeNode {
TreeElemType data;
struct TreeNode* lchild, *rchild;
}TreeNode,*ExpTree;
//定义树栈
typedef struct ETStackNode {
ExpTree ETStackdata;
struct ETStackNode* next;
}ETStackNode,*ETLinkStack;
//定义算符栈
typedef char ElemType;
typedef struct ChStack {
ElemType ChStackdata;
struct ChStack* next;
}ChStackNode, *ChLinkStack;
//算符优先级比较表
char CList[7][7] =
{
{ '>','>','<','<','<','>','>' },
{ '>','>','<','<','<','>','>' },
{ '>','>','>','>','<','>','>' },
{ '>','>','>','>','<','>','>' },
{ '<','<','<','<','<','=',' ' },
{ '>','>','>','>',' ','>','>' },
{ '<','<','<','<','<',' ','=' },
};
//定义七种算符
char *Op = "+-*/()#";
//树栈初始化
void EXTInitStack(ETLinkStack &LS)
{
LS = NULL;
}
// 树栈添加元素
void EXTPush(ETLinkStack &LS, ExpTree ET)
{
ETStackNode* p = new ETStackNode;
p->ETStackdata = ET;
p->next = LS;
LS = p;
}
//树栈弹出栈顶元素
void EXTPop(ETLinkStack &LS, ExpTree &ET)
{
if (LS == NULL) return;
ET = LS->ETStackdata;
ETStackNode* p = LS;
LS = LS->next;
delete p;
}
//树栈获取栈顶元素
ExpTree EXTGetTop(ETLinkStack &LS)
{
if (LS) return LS->ETStackdata;
}
//算符栈初始化
void ChInitStack(ChLinkStack &CS)
{
CS = NULL;
}
//算符栈添加元素
void ChPush(ChLinkStack& CS, ElemType e)
{
ChStackNode* p = new ChStackNode;
p->ChStackdata = e;
p->next = CS;
CS = p;
}
//算符栈弹出栈顶元素
void ChPop(ChLinkStack& CS, ElemType &e)
{
if (CS == NULL) return;
e = CS->ChStackdata;
ChStackNode* p = CS;
CS = CS->next;
delete p;
}
//算符栈获取栈顶元素值
ElemType ChGetTop(ChLinkStack &CS)
{
if (CS != NULL) return CS->ChStackdata;
}
//判断ch是否为算符
bool In(char ch)
{
int i = 0;
while (Op && Op[i] != ch)
i++;
return i < 7;
}
//创建表达式树结点
//以T为根节点，*lchild,*rchild分别为左右孩子
void CreateExpTree(ExpTree &T, TreeNode* lchild, TreeNode* rchild, TreeElemType data)
{
T = new TreeNode;
T->data = data;
T->lchild = lchild;
T->rchild = rchild;
}
//将数值型字符串转换成int型数字
int Atoi(char *str)
{
int res = 0;
while (*str)
res = res * 10 + (*str++ - '0');
return res;
}
//判断算符优先级
char Precede(char c1, char c2)
{
int i = 0, j = 0;
while (Op[i] && Op[i] != c1)
i++;
while (Op[j] && Op[j] != c2)
j++;
return CList[i][j];
}
//表达式树的创建算法
ExpTree InitExpTree()
{
ETLinkStack EXPT;
ChLinkStack OPTR;
EXTInitStack(EXPT);
ChInitStack(OPTR);
ChPush(OPTR, '#');
char ch;
cin >> ch;
while (ch != '#' || ChGetTop(OPTR) != '#')
{
if (!In(ch))
{
char data[20] = { '\0' };
int i = 0;
data[i++] = ch;
cin >> ch;
while (!In(ch))
{
data[i++] = ch;
cin >> ch;
}
ExpTree T;
CreateExpTree(T, NULL, NULL, Atoi(data));
EXTPush(EXPT, T);
}
else
{
switch (Precede(ChGetTop(OPTR),ch))
{
case '<':
ChPush(OPTR, ch);
cin >> ch;
break;
case '>':
char theta;
ChPop(OPTR, theta);
TreeNode* t1, *t2;
EXTPop(EXPT, t2); EXTPop(EXPT, t1);
ExpTree T;
CreateExpTree(T, t1, t2, theta);
EXTPush(EXPT, T);
break;
case '=':
ChPop(OPTR, theta);
cin >> ch;
break;
}
}
}
return EXTGetTop(EXPT);
}
// 中序遍历表达式树
/*
void InOrderTree(ExpTree T)
{
if (T)
{
InOrderTree(T->lchild);
if (T->lchild)
{
char ch = T->data;
cout << ch;
}
else
cout << T->data;
InOrderTree(T->rchild);
}
}
*/
//求值
int GetValue(char ch, int a, int b)
{
switch (ch)
{
case '+':
return a + b;
case '-':
return a - b;
case '*':
return a*b;
case '/':
return a / b;
}
}
//遍历表达树进行表达式求值
int EvaluateExpTree(ExpTree T)
{
int lvalue = 0, rvalue = 0;
if (T->lchild == NULL&&T->rchild == NULL)
return T->data;
else
{
lvalue = EvaluateExpTree(T->lchild);
rvalue = EvaluateExpTree(T->rchild);
return GetValue(T->data, lvalue, rvalue);
}
}
//主函数
int main()
{
ExpTree T = InitExpTree();
cout << EvaluateExpTree(T) << endl;
return 0;
}