#include "iostream"
#include<stdlib.h>
#define Maxsize 100
using namespace std;
typedef char ElemType;
typedef struct node
{
ElemType data;
struct node *lchild;
struct node *rchild;
}BTNode;
//创造二叉树
void CreateBTree(BTNode * &b, char *str)
{
BTNode *St[Maxsize], *p; //St顺序栈
int top=-1,k,j=0;
char ch;
b=NULL;
ch=str[j];
while(ch!=' ')
{
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)
b=p;
else
{
switch(k)
{
case 1:St[top]->lchild=p;break;
case 2:St[top]->rchild=p;break;
}
}
}
j++;
ch=str[j];
}
}
//销毁二叉树
void DestroyBtree(BTNode *&b)
{
if(b!=NULL)
{
DestroyBtree(b->lchild);
DestroyBtree(b->rchild);
free(b);
}
}
//查找结点
BTNode *FindNode(BTNode *b,ElemType x)
{
BTNode *p;
if(b==NULL)
{
return NULL;
}
else if(b->data==x)
{
return b;
}
else
{
p=FindNode(b->lchild, x);
if(p!=NULL)
{
return p;
}
else
{
return FindNode(b->rchild, x);
}
}
}
//查找孩子结点
BTNode *LchildNode(BTNode *p)
{
return p->lchild;
}
BTNode *RchildNode(BTNode *p)
{
return p->rchild;
}
//求高度
int BTHeight(BTNode *b)
{
int lchildh,rchildh;
if(b==NULL) return 0;
else
{
lchildh=BTHeight(b->lchild);
rchildh=BTHeight(b->rchild);
return (lchildh>rchildh)? (lchildh+1):(rchildh+1);
}
}
//输出二叉树
void DispBTree(BTNode *b)
{
if(b!=NULL)
{
cout<<b->data;
if(b->lchild!=NULL || b->rchild!=NULL)
{
cout<<"(";
DispBTree(b->lchild);
if(b->rchild!= NULL) cout<<",";
DispBTree(b->rchild);
cout<<")";
}
}
}
int main()
{
BTNode *b;
char str[]="A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))";
CreateBTree(b, str);
cout<<"初始化二叉树为："<<endl;
DispBTree(b);
cout<<endl;
cout<<"H结点的左结点："<<LchildNode(FindNode(b,'H'))->data<<" 右结点："<<RchildNode(FindNode(b,'H'))->data<<endl;
cout<<"二叉树的高度为:"<<endl;
cout<<BTHeight(b)<<endl;
DestroyBtree(b);
return 0;
}
2、实现二叉树的各种遍历算法
#include <stdio.h>
#include <malloc.h>
#include <stdbool.h>
#define MAX_SIZE 100
typedef char ElemType;
typedef struct node
{
ElemType data; // 数据元素
struct node *lchild; // 指向左孩子结点
struct node *rchild; // 指向右孩子结点
}BTNode; // 声明二叉链结点类型
//由括号表示串str创建二叉链b
static void create_btree(BTNode *&b, char *str) // 创建二叉树(形参b:指针的引用)
{
BTNode *p;
BTNode *St[MAX_SIZE]; // 定义一个顺序栈
int k;
int j = 0;
int top = -1; // 栈顶指针初始化
char ch;
b = NULL; // 建立的二叉树初始时为空
ch = str[j]; // 取第一个字符
while(ch != ' ') // 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的存储空间
p->data = ch;
p->lchild = p->rchild = NULL;
if(b == NULL) // 若b为空,p置为二叉树的根结点
b = p;
else // 已建立二叉树根结点
{
switch(k)
{
case 1:
St[top]->lchild = p;
break;
case 2:
St[top]->rchild = p;
break;
}
}
break;
}
// 取下一个字符
j++;
ch = str[j];
}
}
//以括号表示法输出二叉树b
// "A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))"
static void disp_btree(BTNode *b)
{
if(b != NULL)
{
printf("%c", b->data);
if(b->lchild != NULL || b->rchild != NULL)
{
printf("("); // 有孩子结点时才输出(
disp_btree(b->lchild); // 递归处理左子树
if(b->rchild != NULL) // 有右孩子结点时才输出,
printf(",");
disp_btree(b->rchild); // 递归处理右子树
printf(")"); // 有孩子结点时才输出)
}
}
}
//释放二叉树b的所有结点
static void destroy_btree(BTNode *&b) // 销毁二叉树(形参b:指针的引用)
{
if(b != NULL)
{
destroy_btree(b->lchild);
destroy_btree(b->rchild);
free(b);
}
}
//二叉树b的层次遍历算法
static void trav_level(BTNode *b)
{
BTNode *que[MAX_SIZE]; // 定义环形队列(指针数组)
int que_front, que_rear; // 定义队头和队尾指针
que_front = que_rear = 0; // 设置队列为空队
if(b != NULL)
printf("%c ", b->data);
que_rear++;
que[que_rear] = b; // 根结点进队
while(que_rear != que_front) // 队列不为空
{
que_front = (que_front + 1) % MAX_SIZE; // 计算队头指针
b = que[que_front]; // 出队结点b
if(b->lchild != NULL) // 输出左孩子,并进队
{
printf("%c ", b->lchild->data);
que_rear = (que_rear + 1) % MAX_SIZE; // 计算队尾指针
que[que_rear] = b->lchild;
}
if(b->rchild != NULL) // 输出右孩子,并进队
{
printf("%c ", b->rchild->data);
que_rear = (que_rear + 1) % MAX_SIZE; // 计算队尾指针
que[que_rear] = b->rchild;
}
}
printf("
");
}
//二叉树b的先序遍历递归算法
static void pre_order(BTNode *b)
{
if(b == NULL)
return;
printf("%c ", b->data); // 访问根结点
pre_order(b->lchild); // 递归访问左子树
pre_order(b->rchild); // 递归访问右子树
}
/*二叉树b的先序遍历非递归算法
static void pre_order1(BTNode *b)
{
BTNode *p;
BTNode *st[MAX_SIZE]; // 定义一个顺序栈(指针数组)
int top = -1; // 定义栈顶指针
if(b == NULL)
return;
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("
");
}
*/
//二叉树b的中序遍历递归算法
static void in_order(BTNode *b)
{
if(b == NULL)
return;
in_order(b->lchild); // 递归访问左子树
printf("%c ", b->data); // 访问根结点
in_order(b->rchild); // 递归访问右子树
}
/*二叉树b的中序遍历非递归算法
// A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))
static void in_order1(BTNode *b)
{
BTNode *p;
BTNode *st[MAX_SIZE];
int top = -1;
if(b == NULL)
return;
p = b; // A
while(top > -1 || p != NULL)
{
while(p != NULL) // 扫描结点p的所有左下结点并进栈
{
top++;
st[top] = p;
p = p->lchild;
}
if(top > -1)
{
p = st[top]; // 出栈结点p并访问
top--;
printf("%c ", p->data);
p = p->rchild;
}
}
printf("
");
}
*/
//二叉树b的后序遍历递归算法
static void post_order(BTNode *b)
{
if(b == NULL)
return;
post_order(b->lchild); // 递归访问左子树
post_order(b->rchild); // 递归访问右子树
printf("%c ", b->data); // 访问根结点
}
/*二叉树b的后序遍历非递归算法
static void post_order1(BTNode *b)
{
int top = -1; // 栈指针设置初值
BTNode *st[MAX_SIZE]; // 定义顺序栈
BTNode *p;
bool flag;
if(b == NULL)
return;
do
{
while(b != NULL) // 将b结点的所有左下结点进栈
{
top++;
st[top] = b;
b = b->lchild;
}
p = NULL; // p指向当前结点的前一个已访问的结点
flag = true; // flag为真表示正在处理栈顶结点
while(top != -1 && flag)
{
b = st[top]; // 取出当前的栈顶元素
if(b->rchild == p) // 右子树不存在或已被访问,访问之
{
printf("%c ", b->data); // 访问b结点
top--;
p = b; // p指向被访问的结点
}
else
{
b = b->rchild; // b指向右子树
flag = false; // 表示当前不是处理栈顶结点
}
}
}while(top != -1);
printf("
");
}
*/
int main()
{
BTNode *b;
create_btree(b, "A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");
printf("二叉树b:");
disp_btree(b);
printf("
");
printf("层次遍历序列:");
trav_level(b);
printf("先序遍历序列:
");
printf(" 递归算法:");
pre_order(b);
printf("
");
/* printf(" 非递归算法:");
pre_order1(b);
printf("
");*/
printf("中序遍历序列:
");
printf(" 递归算法:");
in_order(b);
printf("
");
/* printf(" 非递归算法:");
in_order1(b);
printf("
");*/
printf("后序遍历序列:
");
printf(" 递归算法:");
post_order(b);
printf("
");
/* printf(" 非递归算法:");
post_order1(b);
printf("
");*/
destroy_btree(b);
}
3、由遍历序列构造二叉树
#include <stdio.h>
#include <malloc.h>
#include <stdbool.h>
#define MAX_SIZE 100
#define MAX_WIDTH 40
#define WIDTH 4
//写在开头：由前序和后序不能唯一确定一颗二叉树
typedef char ElemType;
typedef struct node
{
ElemType data; // 数据元素
struct node *lchild; // 指向左孩子结点
struct node *rchild; // 指向右孩子结点
}BTNode; // 声明二叉链结点类型
//由括号表示串str创建二叉链b
static void create_btree(BTNode *&b, char *str) // 创建二叉树(形参b:指针的引用)
{
BTNode *p;
BTNode *St[MAX_SIZE]; // 定义一个顺序栈
int k;
int j = 0;
int top = -1; // 栈顶指针初始化
char ch;
b = NULL; // 建立的二叉树初始时为空
ch = str[j]; // 取第一个字符
while(ch != ' ') // 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的存储空间
p->data = ch;
p->lchild = p->rchild = NULL;
if(b == NULL) // 若b为空,p置为二叉树的根结点
b = p;
else // 已建立二叉树根结点
{
switch(k)
{
case 1:
St[top]->lchild = p;
break;
case 2:
St[top]->rchild = p;
break;
}
}
break;
}
// 取下一个字符
j++;
ch = str[j];
}
}
//以括号表示法输出二叉树b
// "A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))"
static void disp_btree(BTNode *b)
{
if(b != NULL)
{
printf("%c", b->data);
if(b->lchild != NULL || b->rchild != NULL)
{
printf("("); // 有孩子结点时才输出(
disp_btree(b->lchild); // 递归处理左子树
if(b->rchild != NULL) // 有右孩子结点时才输出,
printf(",");
disp_btree(b->rchild); // 递归处理右子树
printf(")"); // 有孩子结点时才输出)
}
}
}
//释放二叉树b的所有结点
static void destroy_btree(BTNode *&b) // 销毁二叉树(形参b:指针的引用)
{
if(b != NULL)
{
destroy_btree(b->lchild);
destroy_btree(b->rchild);
free(b);
}
}
//由先序和中序遍历序列构造二叉树
// pre:ABDEHJKLMNCFGI
// in:DBJHLKMNEAFCGI
// A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))
static BTNode *create_btree_by_pre_in(char *pre, char *in, int n)
{
BTNode *b;
char *p;
int k;
if(n <= 0)
return NULL;
b = (BTNode *)malloc(sizeof(BTNode)); // 创建二叉树结点b
b->data = *pre;
for(p = in; p < in + n; p++) // 在中序序列in中查找等于*pre字符的位置
{
if(*p == *pre) // pre指向根结点
{
break; // 在中序序列in中找到后退出循环
}
}
k = p - in; // 确定根结点在中序序列in中的位置
b->lchild = create_btree_by_pre_in(pre + 1, in, k); // 递归构造左子树
b->rchild = create_btree_by_pre_in(pre + k + 1, p + 1, n - k - 1); // 递归构造右子树
return b;
}
//以凹入表示法输出一颗二叉树b，这个学习一下就可
static void disp_btree1(BTNode *b)
{
BTNode *p;
BTNode *st[MAX_SIZE];
int top = -1;
int i;
int n;
int level[MAX_SIZE][2];
char type; // 存放左右孩子标记
if(b != NULL)
{
top++;
st[top] = b; // 根结点进栈
level[top][0] = WIDTH;
level[top][1] = 2; // 2表示根
while(top > -1) // 栈不空时循环
{
p = st[top]; // 取栈顶结点,并凹入显示该结点值
n = level[top][0]; // 取根结点的显示场宽,即左边的空格个数
switch(level[top][1])
{
case 0: // 左结点之后输出(L)
type = 'L';
break;
case 1: // 右结点之后输出(R)
type = 'R';
break;
case 2: // 根结点之后输出(B)
type = 'B';
break;
}
for(i = 1; i < n; i++) // 其中n为显示场宽,字符以右对齐显示
printf(" ");
printf("%c(%c)", p->data, type);
for(i = n + 1; i <= MAX_WIDTH; i += 2)
printf("--");
printf("
");
top--; // 出栈
if(p->rchild != NULL)
{
top++;
st[top] = p->rchild; // 右孩子进栈
level[top][1] = 1; // 1表示是右子树
level[top][0] = n + WIDTH; // 显示场宽增WIDTH
}
if(p->lchild != NULL)
{
top++;
st[top] = p->lchild; // 左孩子进栈
level[top][1] = 0; // 0表示是左子树
level[top][0] = n + WIDTH; // 显示场宽增WIDTH
}
}
}
}
//由中序和后序遍历序列构造二叉树
// post:DJLNMKHEBFIGCA
// in:DBJHLKMNEAFCGI
// A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))
static BTNode *create_btree_by_post_in(char *post, char *in, int n)
{
BTNode *b;
char root;
char *p;
int k;
if(n <= 0)
return NULL;
root = *(post + n - 1); // 取根结点值
b = (BTNode *)malloc(sizeof(BTNode)); // 创建二叉树结点b(动态分配存储空间)
b->data = root;
for(p = in; p < in + n; p++) // 在中序序列in中查找根结点
{
if(*p == root)
{
break;
}
}
k = p - in; // k为根结点在in中的下标
b->lchild = create_btree_by_post_in(post, in, k); // 递归构造左子树
b->rchild = create_btree_by_post_in(post + k, p + 1, n - k - 1); // 递归构造右子树
return b;
}
int main()
{
BTNode *b;
ElemType pre[] = "ABDEHJKLMNCFGI";
ElemType in[] = "DBJHLKMNEAFCGI";
ElemType post[] = "DJLNMKHEBFIGCA";
int n = 14; // 二叉树*有14个结点
b = create_btree_by_pre_in(pre, in, n);
printf("先序序列:%s
", pre);
printf("中序序列:%s
", in);
printf("构造一颗二叉树b:
");
printf(" 括号表示法:");
disp_btree(b);
printf("
");
printf(" 凹入表示法:
");
disp_btree1(b);
printf("
");
printf("中序序列:%s
", in);
printf("后序序列:%s
", post);
b = create_btree_by_post_in(post, in, n);
printf("构造一颗二叉树b:
");
printf(" 括号表示法:");
disp_btree(b);
printf("
");
printf(" 凹入表示法:
");
disp_btree1(b);
printf("
");
destroy_btree(b);
}
4、构造哈夫曼树和生成哈夫曼编码
#include <stdio.h>
#include <string.h>
#define N (50) // 树中叶子结点数最大值
#define M (2 * N - 1) // 树中结点总数最大值
//注：二叉树中叶子结点个数为n,则二叉树中结点总数为(2 * n - 1)
typedef struct
{
char data[5]; // 结点值
int weight; // 权重
int parent; // 双亲结点
int lchild; // 左孩子结点
int rchild; // 右孩子结点
}HTNode; // 声明哈夫曼树结点类型
typedef struct
{
char cd[N]; // 存放哈夫曼编码
int start;
}HCode; // 声明哈夫曼编码类型
//由含有n个叶子结点的ht构造完整的哈夫曼树
static void create_huffman_tree(HTNode ht[], int n)
{
int i;
int k;
int lnode;
int rnode;
int min1;
int min2;
// 所有结点的相关域设置初值为-1
for(i = 0; i < 2 * n - 1; i++)
ht[i].parent = ht[i].lchild = ht[i].rchild = -1;
for(i = n; i < 2 * n - 1; i++) // 构造哈夫曼树的分支结点
{
min1 = min2 = 32767; //2^15
lnode = rnode = -1;
for(k = 0; k <= i - 1; k++) // 查找最小和次小的结点
{
if(ht[k].parent == -1) // 只在尚未构造二叉树的结点中查找
{
if(ht[k].weight < min1)
{
min2 = min1;
rnode = lnode;
min1 = ht[k].weight;
lnode = k;
}
else if(ht[k].weight < min2)
{
min2 = ht[k].weight;
rnode = k;
}
}
}
ht[lnode].parent = i; // 合并两个最小和次小的结点
ht[rnode].parent = i;
ht[i].weight = ht[lnode].weight + ht[rnode].weight; // 计算双亲结点的权重
ht[i].lchild = lnode; // 设置双亲结点的左孩子
ht[i].rchild = rnode; // 设置双亲结点的右孩子
}
}
//由哈夫曼树ht构造哈夫曼编码hcd
static void create_huffman_code(HTNode ht[], HCode hcd[], int n)
{
int i;
int f;
int c;
HCode hc;
for(i = 0; i < n; i++) // 根据哈夫曼树构造所有叶子结点的哈夫曼编码
{
hc.start = n;
c = i;
f = ht[i].parent;
while(f != -1) // 循环直到树根结点
{
if(ht[f].lchild == c) // 处理左孩子结点
hc.cd[hc.start--] = '0';
else // 处理右孩子结点
hc.cd[hc.start--] = '1';
c = f;
f = ht[f].parent;
}
hc.start++; // start指向哈夫曼编码最开始字符
hcd[i] = hc;
}
}
//输出哈夫曼编码
static void display_huffman_code(HTNode ht[], HCode hcd[], int n)
{
int i;
int k;
int sum = 0;
int m = 0;
int j;
printf("输出哈夫曼编码:
");
for(i = 0; i < n; i++)
{
j = 0;
printf(" %s: ", ht[i].data);
for(k = hcd[i].start; k <= n; k++)
{
printf("%c", hcd[i].cd[k]);
j++;
}
m += ht[i].weight;
sum += ht[i].weight * j;
printf("
");
}
printf("
平均长度 = %g
", 1.0 * sum / m);
}
int main()
{
int n = 15;
int i;
HTNode ht[M];
HCode hcd[N];
char *str[] = {"The", "of", "a", "to", "and", "in", "that", "he", "is", "at", "on", "for", "His", "are", "be"};
int fnum[] = {1192, 677, 541, 518, 462, 450, 242, 195, 190, 181, 174, 157, 138, 124, 123};
for(i = 0; i < n; i++)
{
strcpy(ht[i].data, str[i]);
ht[i].weight = fnum[i];
}
create_huffman_tree(ht, n); // 创建哈夫曼树
create_huffman_code(ht, hcd, n); // 构造哈夫曼编码
display_huffman_code(ht, hcd, n); // 输出哈夫曼编码
}
5、求二叉树中的结点个数等
#include<stdio.h>
#include<malloc.h>
#define MaxSize 100
typedef char ElemType;
typedef struct node
{
ElemType data;
struct node *lchild;
struct node *rchild;
}BTNode;
//由括号表示串str创建二叉链b
void CreateBTree(BTNode *&b,char *str)
{
BTNode *St[MaxSize],*p;
int top=-1,k,j=0;char ch;
b=NULL;
ch=str[j];
while(ch!=' ')
{
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)
b=p;
else
{
switch(k)
{
case 1:St[top]->lchild=p;break;
case 2:St[top]->rchild=p;break;
}
}
}
j++;ch=str[j];
}
}
//销毁二叉树
void DestroyBTree(BTNode *&b)
{
if(b!=NULL)
{
DestroyBTree(b->lchild);
DestroyBTree(b->rchild);
free(b);
}
}
//找结点
BTNode *FindNode(BTNode *b,ElemType x)
{
BTNode *p;
if(b==NULL)
return NULL;
else if(b->data==x)
return b;
else
{
p=FindNode(b->lchild,x);
if(p!=NULL)
return p;
else
return FindNode(b->rchild,x);
}
}
//左、右孩子
BTNode *LchildNode(BTNode *p)
{
return p->lchild;
}
BTNode *RchildNode(BTNode *p)
{
return p->rchild;
}
//求高度
int BTHeight(BTNode *b)
{
int lchildh,rchildh;
if(b==NULL)return(0);
else
{
lchildh=BTHeight(b->lchild);
rchildh=BTHeight(b->rchild);
return (lchildh>rchildh)?(lchildh+1):(rchildh+1);
}
}
//输出二叉树
void DispBTree(BTNode *b)
{
if(b!=NULL)
{
printf("%c",b->data);
if(b->lchild!=NULL||b->rchild!=NULL)
{
printf("(");
DispBTree(b->lchild);
if(b->rchild!=NULL)printf(",");
DispBTree(b->rchild);
printf(")");
}
}
}
//结点个数
int Nodes(BTNode *b)
{
int num1,num2;
if(b==NULL)
return 0;
else if(b->lchild==NULL&&b->rchild==NULL)
return 1;
else
{
num1=Nodes(b->lchild);
num2=Nodes(b->rchild);
return (num1+num2+1);
}
}
//叶子结点个数
int LeafNodes(BTNode *b)
{
int num1,num2;
if(b==NULL)
return 0;
else if(b->lchild==NULL&&b->rchild==NULL)
return 1;
else
{
num1=LeafNodes(b->lchild);
num2=LeafNodes(b->rchild);
return (num1+num2);
}
}
//结点层次
int Level(BTNode *b,ElemType x,int h)
{
int l;
if(b==NULL)
return 0;
else if(b->data==x)
return h;
else
{
l=Level(b->lchild,x,h+1);
if(l!=0)return l;
else return(Level(b->rchild,x,h+1));
}
}
//二叉树宽度
int BTWidth(BTNode *b)
{
struct
{
int lno;
BTNode *p;
}Qu[MaxSize];
int front,rear;
int lnum,max,i,n;
front=rear=0;
if(b!=NULL)
{
rear++;Qu[rear].p=b;
Qu[rear].lno=1;
while(rear!=front)
{
front++;b=Qu[front].p;
lnum=Qu[front].lno;
if(b->lchild!=NULL)
{
rear++;Qu[rear].p=b->lchild;
Qu[rear].lno=lnum+1;
}
if(b->rchild!=NULL)
{
rear++;Qu[rear].p=b->rchild;
Qu[rear].lno=lnum+1;
}
}
max=0;lnum=1;i=1;
while(i<=rear)
{
n=0;
while(i<=rear&&Qu[i].lno==lnum)
{
n++;
i++;
}
lnum=Qu[i].lno;
if(n>max)max=n;
}
return max;
}
else return 0;
}
int main()
{
ElemType x='K';
BTNode *b,*p,*lp,*rp;
CreateBTree(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");
printf("输出二叉树b：");DispBTree(b);printf("
");
printf("二叉树b的结点个数：%d
",Nodes(b));
printf("二叉树的叶子结点个数：%d
",LeafNodes(b));
printf("二叉树b中值为%c结点的层次：%d
",x,Level(b,x,1));
printf("二叉树b的宽度：%d
",BTWidth(b));
DestroyBTree(b);
}
6、求二叉树中从根节点到叶子结点的路径
#include<stdio.h>
#include<malloc.h>
#define MaxSize 100
typedef char ElemType;
typedef struct node
{
ElemType data;
struct node *lchild;
struct node *rchild;
}BTNode;
//括号法创建二叉树
void CreateBTree(BTNode *&b,char *str)
{
BTNode *St[MaxSize],*p;
int top=-1,k,j=0;char ch;
b=NULL;
ch=str[j];
while(ch!=' ')
{
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)
b=p;
else
{
switch(k)
{
case 1:St[top]->lchild=p;break;
case 2:St[top]->rchild=p;break;
}
}
}
j++;ch=str[j];
}
}
//销毁二叉树
void DestroyBTree(BTNode *&b)
{
if(b!=NULL)
{
DestroyBTree(b->lchild);
DestroyBTree(b->rchild);
free(b);
}
}
//查找结点
BTNode *FindNode(BTNode *b,ElemType x)
{
BTNode *p;
if(b==NULL)
return NULL;
else if(b->data==x)
return b;
else
{
p=FindNode(b->lchild,x);
if(p!=NULL)
return p;
else
return FindNode(b->rchild,x);
}
}
//左、右孩子结点
BTNode *LchildNode(BTNode *p)
{
return p->lchild;
}
BTNode *RchildNode(BTNode *p)
{
return p->rchild;
}
//求高度
int BTHeight(BTNode *b)
{
int lchildh,rchildh;
if(b==NULL)return(0);
else
{
lchildh=BTHeight(b->lchild);
rchildh=BTHeight(b->rchild);
return (lchildh>rchildh)?(lchildh+1):(rchildh+1);
}
}
//输出二叉树
void DispBTree(BTNode *b)
{
if(b!=NULL)
{
printf("%c",b->data);
if(b->lchild!=NULL||b->rchild!=NULL)
{
printf("(");
DispBTree(b->lchild);
if(b->rchild!=NULL)printf(",");
DispBTree(b->rchild);
printf(")");
}
}
}
//先序遍历，所有叶子结点到根节点的逆路径
void AllPath1(BTNode *b,ElemType path[],int pathlen)
{
if(b!=NULL)
{
if(b->lchild==NULL&&b->rchild==NULL)
{
printf("%c到根结点逆路径：%c->",b->data,b->data);
for(int i=pathlen-1;i>0;i--)
printf("%c->",path[i]);
printf("%c
",path[0]);
}
else
{
path[pathlen]=b->data;
pathlen++;
AllPath1(b->lchild,path,pathlen);
AllPath1(b->rchild,path,pathlen);
}
}
}
//最长的逆路径
void LongPath1(BTNode *b,ElemType path[],int pathlen,ElemType longpath[],int &longpathlen)
{
if(b==NULL)
{
if(pathlen>longpathlen)
{
for(int i=pathlen-1;i>=0;i--)
longpath[i]=path[i];
longpathlen=pathlen;
}
}
else
{
path[pathlen]=b->data;
pathlen++;
LongPath1(b->lchild,path,pathlen,longpath,longpathlen);
LongPath1(b->rchild,path,pathlen,longpath,longpathlen);
}
}
//后序非递归遍历
void AllPath2(BTNode *b)
{
BTNode *st[MaxSize];
int top=-1;
BTNode *p,*r;
bool flag;
p=b;
do
{
while(p!=NULL)
{
top++;
st[top]=p;
p=p->lchild;
}
r=NULL;
flag=true;
while(top>=-1&&flag)
{
p=st[top];
if(p->rchild==r)
{
if(p->lchild==NULL&&p->rchild==NULL)
{
printf("%c到根结点逆路径：",p->data);
for(int i=top;i>0;i--)
printf("%c->",st[i]->data);
printf("%c
",st[0]->data);
}
top--;
r=p;
}
else
{
p=p->rchild;
flag=false;
}
}
}while(top>-1);
}
//层次遍历
void AllPath3(BTNode *b)
{
struct snode
{
BTNode *node;
int parent;
}Qu[MaxSize];
int front,rear,p;
front=rear=-1;
rear++;
Qu[rear].node=b;
Qu[rear].parent=-1;
while(front<rear)
{
front++;
b=Qu[front].node;
if(b->lchild==NULL&&b->rchild==NULL)
{
printf("%c到根结点逆路径：",b->data);
p=front;
while(Qu[p].parent!=-1)
{
printf("%c->",Qu[p].node->data);
p=Qu[p].parent;
}
printf("%c
",Qu[p].node->data);
}
if(b->lchild!=NULL)
{
rear++;
Qu[rear].node=b->lchild;
Qu[rear].parent=front;
}
if(b->rchild!=NULL)
{
rear++;
Qu[rear].node=b->rchild;
Qu[rear].parent=front;
}
}
}
int main()
{
BTNode *b;
ElemType path[MaxSize],longpath[MaxSize];
int i,longpathlen=0;
CreateBTree(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");
printf("二叉树b：");DispBTree(b);printf("
");
printf("先序遍历方法：
");AllPath1(b,path,0);
LongPath1(b,path,0,longpath,longpathlen);
printf("第一条最长逆路径长度：%d
",longpathlen);
printf("第一条最长逆路径：");
for(i=longpathlen-1;i>=0;i--)
printf("%c",longpath[i]);
printf("
");
printf("后序非递归遍历方法：
");AllPath2(b);
printf("层次遍历方法：
");AllPath3(b);
DestroyBTree(b);
}
7、简单算术表达式二叉树的构建和求值
#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include <stdlib.h>
#define MAX_SIZE 100
typedef char ElemType;
typedef struct node
{
ElemType data; // 数据元素
struct node *lchild; // 指向左孩子结点
struct node *rchild; // 指向右孩子结点
}BTNode; // 声明二叉链结点类型
//以括号表示法输出二叉树b
static void disp_btree(BTNode *b)
{
if(b != NULL)
{
printf("%c", b->data);
if(b->lchild != NULL || b->rchild != NULL)
{
printf("("); // 有孩子结点时才输出(
disp_btree(b->lchild); // 递归处理左子树
if(b->rchild != NULL) // 有右孩子结点时才输出,
printf(",");
disp_btree(b->rchild); // 递归处理右子树
printf(")"); // 有孩子结点时才输出)
}
}
}
//释放二叉树b的所有结点
static void destroy_btree(BTNode *&b) // 销毁二叉树(形参b:指针的引用)
{
if(b != NULL)
{
destroy_btree(b->lchild);
destroy_btree(b->rchild);
free(b);
}
}
//建立简单算术表达式s[i...j]对应的二叉树
/**
* @功能:用于生成简单算术表达式对应的二叉树，递归函数。
* @param s:存放简单算术表达式字符串
* @i:该字符串或其子串的起始位置
* @j:该字符串或其子串的终止位置
* 如果i=j，说明子串只有一个字符，即为叶子结点，则创建只有一个根结点的二叉树并返回。
* 如果i≠j，根据运算规则，在串中找"+"或"-"号，以最后的"+"或"-"为根(体现从左到右的原则)；
* 当没有"+"或"-"号时，则进一步找"*"或"/"(体现先乘除后加减的原则)，同样以最后的运算符
* 为根，将串分为两部分，即左子树和右子树。创建一个根结点，将找到的运算符放入，递归
* 调用自身进入左子树的建树工作，之后递归调用自身进入右子树的建树工作。
*/
static BTNode *cr_tree(char s[], int i, int j)
{
int oper_num = 0; // 记录运算符的个数
BTNode *p;
int k;
int pos;
if(i == j) // 处理i=j的情况,说明只有一个字符
{
p = (BTNode *)malloc(sizeof(BTNode));
p->data = s[i];
p->lchild = p->rchild = NULL;
return p;
}
//以下为i≠j的情况
for(k = i; k <= j; k++) // 首先查找+和-运算符
{
if(s[k] == '+' || s[k] == '-')
{
oper_num++; // oper_num记录+或者-的个数
pos = k; // pos记录最后一个+或者-的位置
}
}
if(oper_num == 0) // 没有+或者-的情况
{
for(k = i; k <= j; k++)
{
if(s[k] == '*' || s[k] == '/')
{
oper_num++; // oper_num记录*或者/的个数
pos = k; // pos记录最后一个*或者/的位置
}
}
}
if(oper_num != 0) // 有运算符的情况,创建一个存放它的结点
{
p = (BTNode *)malloc(sizeof(BTNode));
p->data = s[pos];
p->lchild = cr_tree(s, i, pos - 1); // 递归处理s[i...pos - 1]构造左子树
p->rchild = cr_tree(s, pos + 1, j); // 递归处理s[pos + 1, j]构造右子树
}
else // 没有任何运算符,返回NULL
return NULL;
}
//计算二叉树对应表达式的值
/**
* @功能:计算二叉树对应表达式的值，递归函数。
* 若为空树，则返回0，否则若b所指结点为叶子结点，则返回其data值，否则求出
* 左子树的值v1，再求出右子树的值v2，根据b所指结点的运算符对v1和v2进行相应
* 的计算并返回计算后的结果。
*/
static double compute(BTNode *b)
{
double v1, v2;
if(b == NULL)
return 0;
if(b->lchild == NULL && b->rchild == NULL) // 叶子结点直接返回结点值
return b->data - '0';
v1 = compute(b->lchild); // 递归求出左子树的值v1
v2 = compute(b->rchild); // 递归求出右子树的值v2
switch(b->data) // 根据b结点做相应运算
{
case '+':
return v1 + v2;
case '-':
return v1 - v2;
case '*':
return v1 * v2;
case '/':
if(v2 != 0)
return v1 / v2;
else
abort(); // 除0异常退出
}
}
int main()
{
BTNode *b;
char s[MAX_SIZE] = "1+2*3-4/5";
printf("算术表达式%s
", s);
b = cr_tree(s, 0, strlen(s) - 1);
printf("对应二叉树:");
disp_btree(b);
printf("
算术表达式的值:%g
", compute(b));
destroy_btree(b);
}
