已知一棵二叉树是以二叉链表的形式存储的求出以T为根的子树的结点个数和高度 已知一棵二叉树以二叉链表为存储结构，编写如下程序：对于树中每...

5.1树的概念

树的递归定义如下：（1）至少有一个结点（称为根）（2）其它是互不相交的子树

1.树的度——也即是宽度，简单地说，就是结点的分支数。以组成该树各结点中最大的度作为该树的度，如上图的树，其度为3;树中度为零的结点称为叶结点或终端结点。树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。
2.树的深度——组成该树各结点的最大层次，如上图，其深度为4；
3.森林——指若干棵互不相交的树的集合，如上图，去掉根结点A，其原来的二棵子树T1、T2、T3的集合就为森林；
4.有序树——指树中同层结点从左到右有次序排列，它们之间的次序不能互换，这样的树称为有序树，否则称为无序树。
5.树的表示
树的表示方法有许多，常用的方法是用括号：先将根结点放入一对圆括号中，然后把它的子树由左至右的顺序放入括号中，而对子树也采用同样的方法处理；同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。如上图可写成如下形式：
(A(B(E(K,L),F),C(G),D(H(M),I,J)))
5. 2 二叉树
1.二叉树的基本形态：
二叉树也是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：

(1)空二叉树——(a)；
(2)只有一个根结点的二叉树——(b)；
(3)右子树为空的二叉树——(c)；
(4)左子树为空的二叉树——(d)；
(5)完全二叉树——(e)
注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。

2.两个重要的概念：
(1)完全二叉树——只有最下面的两层结点度小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树；
(2)满二叉树——除了叶结点外每一个结点都有左右子女且叶结点都处在最底层的二叉树,。
如下图：

完全二叉树

满二叉树

3.二叉树的性质
(1) 在二叉树中，第i层的结点总数不超过2^(i-1)；

(2) 深度为h的二叉树最多有2h-1个结点(h>=1)，最少有h个结点；
(3) 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，

则N0=N2+1；

(4) 具有n个结点的完全二叉树的深度为int（log2n）+1
(5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：

若I为结点编号则 如果I<>1，则其父结点的编号为I/2；
如果2*I<=N，则其左儿子（即左子树的根结点）的编号为2*I；若2*I>N，则无左儿子；
如果2*I+1<=N，则其右儿子的结点编号为2*I+1；若2*I+1>N，则无右儿子。
4.二叉树的存储结构：
(1）顺序存储方式

type node=record

data:datatype

l,r:integer;

end;

var tr:array[1..n] of node;

(2)链表存储方式，如：
type btree=^node；

node=record

data:datatye;

lchild,rchild:btree;

end;

5.普通树转换成二叉树：凡是兄弟就用线连起来，然后去掉父亲到儿子的连线，只留下父母到其第一个子女的连线。

6.二叉树的遍历运算（递归定义）
(1)先序遍历
访问根；按先序遍历左子树；按先序遍历右子树
(2)中序遍历
按中序遍历左子树；访问根；按中序遍历右子树
(3)后序遍历
按后序遍历左子树；按后序遍历右子树；访问根

例1.用顺序存储方式建立一棵有31个结点的满二叉树，并对其进行先序遍历。
program erchashu1;
var b:array[1..31] of char;
e:array[1..63] of byte;
n,h,i,k:integer;
procedure tree(t:integer);
begin
if e[t]=0 then exit
else
begin
write(b[t]);e[t]:=0;
t:=2*t;tree(t);
t:=t+1;tree(t);
end;
end;
begin
repeat
write('n=');readln(n);
until (n>0) and (n<6);
fillchar(e,sizeof(e),0);
k:=trunc(exp(n*ln(2)))-1;
for i:=1 to k do e[i]:=1;
for i:=1 to 26 do b[i]:=chr(64+i);
for i:=1 to 5 do b[26+i]:=chr(48+i);
h:=1 ;tree(h);
writeln;
end.

例2.用顺序存储方式建立一棵如图所示的二叉树，并对其进行先序遍历。

program tree1;
const n=15;
type node=record
data:char;
l,r:0..n;
end;
var tr:array[1..n] of node;
e:array[1..n] of 0..1;
i,j:integer;

procedure jtr;
var i:integer;
begin
for i:=1 to n do
with tr[i] do
readln(data,l,r);
end;
procedure search(m:integer);
begin
with tr[m] do
begin
write(data);
if l<>0 then search(l);
if r<>0 then search(r);
end;
end;
begin
jtr;search(1);writeln;
end.

例3 用链表存储方式生成上述二叉树，中序遍历之。

1.将上述二叉树用广义表表示为A(B(D,E(G)),C(F(,H)))

2.根据广义表串（以#结束）生成二叉树。

program ltree;
const n=8;
type trlist=^node;
node=record
da:char;
l,r:trlist;
end;
var s:array[1..n] of trlist;
p,root:trlist;
ch:char;
top,k:integer;
procedure creat(var head:trlist);
begin
read(ch);
top:=0;
while ch<>'#' do
begin
case ch of
'A'..'Z':begin new(p);p^.da:=ch;p^.l:=nil;p^.r:=nil;
if top<>0 then
case k of
1:s[top]^.l:=p;
2:s[top]^.r:=p;
end
end;
'(':begin top:=top+1;s[top]:=p;k:=1;end;
')': top:=top-1;
',': k:=2;
end;
read(ch);
end;
head:=s[1];
end;
procedure inorder(head:trlist);
begin
if head^.l<>nil then inorder(head^.l);
write(head^.da);
if head^.r<>nil then inorder(head^.r);
end;
begin
write('Input tree string:');
creat(root);
inorder(root);
end.

5.3 二叉树的应用
1. 哈夫曼树与哈夫曼码

树的路径长度：一棵树的每一个叶结点到根结点的路径长度的和。

带权二叉树：给树的叶结点赋上某个实数值（称叶结点的权）。

带权路径长度：各叶结点的路径长度与其权值的积的总和。

哈夫曼树（最优二叉树）：带权路径长度最小的二叉树。

如何构建哈夫树：（思想是：权越大离跟越近）

program gojiantree;
const n=4;m=7;
type node=record
w:real;
parent,lchild,rchild:0..m
end;
htree=array[1..m] of node;
var htree1:htree;
procedure gjtree(var ht:htree);
var i,j:integer;
small1,small2:real;
p1,p2:0..m;
begin
for i:=1 to m do
with ht[i] do
begin
w:=0;lchild:=0;rchild:=0;parent:=0;
end;
for i:=1 to n do read(ht[i].w);
for i:=n+1 to m do
begin
p1:=0;p2:=0;
small1:=1000;small2:=1000;
for j:=1 to i-1 do
if ht[j].parent=0 then
if ht[j].w<small1 then
begin small2:=small1;small1:=ht[j].w;p2:=p1;p1:=j end
else if ht[j].w<small2 then begin small2:=ht[j].w;p2:=j end;
ht[p1].parent:=i;
ht[p2].parent:=i;
ht[i].lchild:=p1;
ht[i].rchild:=p2;
ht[i].w:=ht[p1].w+ht[p2].w;
end;
end;
begin
gjtree(htree1);
end.

哈夫曼码：哈夫曼树的非叶结点到左右孩子的路径分别用0，1 表示，从根到叶的路径序列即为哈夫曼码。

哈夫曼码是不会发生译码多义性的不等长编码，广泛应用实际中。

（原因是任何一字符的编码不是更长编码的前缀部分，为什么？）

2.排序二叉树

排序二叉树：每一个参加排列的数据对应二叉树的一个结点，且任一结点如果有左（右）子树，则左（右）子树各结点的数据必须小（大）于该结点的数据。中序遍历排序二叉树即得排序结果。程序如下：

program pxtree;
const
a:array[1..8] of integer=(10,18,3,8,12,2,7,3);
type point=^nod;
nod=record
w:integer;
right,left:point ;
end;
var root,first:point;k:boolean;i:integer;
procedure hyt(d:integer;var p:point);
begin
if p=nil then
begin
new(p);
with p^ do begin w:=d;right:=nil;left:=nil end;
if k then begin root:=p; k:=false end;
end
else with p^ do if d>=w then hyt(d,right) else hyt(d,left);
end;
procedure hyt1(p:point);
begin
with p^ do
begin
if left<>nil then hyt1(left);
write(w:4);
if right<>nil then hyt1(right);
end
end;
begin
first:=nil;k:=true;
for i:=1 to 8 do hyt(a[i],first);
hyt1(root);writeln;
end.

3.堆排序

堆：设有数据元素的集合（R1,R2,R3,...Rn)它们是一棵顺序二叉树的结点且有

Ri<=R2i 和Ri<=R2i+1(或>=)

堆的性质：堆的根结点上的元素是堆中的最小元素，且堆的每一条路径上的元素都是有序的。

堆排序的思想是：

1）建初始堆（将结点[n/2],[ n/2]-1,...3,2,1分别调成堆）

2）当未排序完时

输出堆顶元素，删除堆顶元素，将剩余的元素重新建堆。

程序如下：

program duipx;
const n=8;
type arr=array[1..n] of integer;
var a:arr;i:integer;
procedure sift(var a:arr;l,m:integer);
var i,j, t:integer;
begin
i:=l;j:=2*i;t:=a[i];
while j<=m do
begin
if (j<m) and (a[j]>a[j+1]) then j:=j+1;
if t>a[j] then
begin a[i]:=a[j];i:=j;j:=2*i; end
else exit;
end;
a[i]:=t;
end;
begin
for i:=1 to n do read(a[i]);
for i:=(n div 2) downto 1 do
sift(a,i,n);
for i:=n downto 2 do
begin
write(a[1]:4);
a[1]:=a[i];
sift(a,1,i-1);
end;
writeln(a[1]:4);
end

int depth(T)
{
if(!T)
depthval=0;
else
{
depthLeft=depth(T->lchild);
depthRight=depth(T->rchild);
depthval=(depthLeft>depthRight?depthLeft:depthRight);
}
return depthval;
}

已知一棵二叉树是以二叉链表的形式存储的，其结点结构说明如下： struct node { int data; struct node *~

#include
#include

/*①、求出以T为根的子树的结点个数。
②、求出以T为根的子树的高度。*/

typedef struct node
{
int data;
struct node * left;
struct node * right;
}BiTNode,*BiTree;

/*①、求出以T为根的子树的结点个数。*/
void CountLeaf (BiTree T, int& count)
{ //递归方法，
if ( T )
{
if ((!T->lchild)&& (!T->rchild))
count++;
CountLeaf( T->lchild, count); // 统计左子树中叶子结点个数
CountLeaf( T->rchild, count); // 统计右子树中叶子结点个数
}
}

/*②、求出以T为根的子树的高度。*/
int Depth(BinTree *T)
{
int dep1,dep2;
if(T==Null) return(0);
else
{
dep1=Depth(T->lchild);
dep2=Depth(T->rchild);
return dep1 > dep2 ? dep1 +1 : dep2 + 1;
}

先前序遍历整个二叉树，找到符合要求的结点，然后后序遍历该结点的整个子树，逐一释放结点。
//假设二叉树结构体如下struct binTree{ int data; binTree *lchild; binTree *rchild;}*BiTree;//函数如下BiTree find(BiTree node, int x){ if(node) { if(node->data==x) delete(node); else { find(node->lchild); find(node->rchild); } }}BiTree delete(BiTree tree){ if(node) { delete(node->lchild); delete(node->rchild); free(node); node=NULL; }}

假定一棵二叉树用二叉链表存储试编写求出二叉树中1度结点个数的算法
答：/ 设0度结点 1度结点 2度结点个数分别为x0 x1 x2 / x0+x1+x2 = node_count;//三种结点数之和为总结点数 0*x0 + 1*x1 + 2*x2 = node_count - 1;//树枝数等于结点数减1（去掉根结点）一式乘2减二式得 2*x0 + x1 = node_count + 1;因此只要知道叶子数和总结点数就可得1...

C++: 设计算法将一棵以二叉链表形式存储的二叉树转换为顺序存储形式存储...
答：{ char data;BTNode* lchild;BTNode* rchild;}BTNode;void Ctree(struct BTNode* t,char A[],int i){ if(t!=NULL){ A[i]=t->data;Ctree(t->lchild,A,i*2);Ctree(t->rchild,A,i*2+1);} else { A[i]=' ';} } int main(void){ //建立二叉链表存储结构的二叉树,以p1为...

以二叉链表作为二叉树的储存结构,在具有n个结点的二叉链表中n(n>0...
答：在具有n个结点的二叉链表中n（n＞0），空链域的个数为n+1。二叉链表结构描述：typedef struct CSNode{ ElemType data;struct CSNode *firstchild ， *netsibling;} CSNode，* CSTree;由于二叉树的存储结构比较简单，处理起来也比较方便，所以有时需要把复杂的树，转换为简单的二叉树后再作处理。

以二叉树链表作为二叉树的存储结构,编写算法计算返回二叉树的高度
答：这么说不知道楼主明白了没有，举例就是：如果只有一个根节点，那么高度就是1，如果有一个根节点再加上根节点的两个孩子，或者其中一个孩子，那么高度就是2；那根据这样 如果用递归的思想，我想算法就比较好写了，就是统计一下根节点的左右孩子的高对呗，看哪个的高度更大那二叉树高度就是那个呗。

假设二叉树用二叉链表存储结构。编写一个算法统计二叉树的结点个数.
答：int BiTreeCount(BiTree T){ int rNum,lNum;if(!T)return 0;else { lNum = BiTreeCount(T->lchild);rNum = BiTreeCount(T->rchild);return rNum + lNum + 1;} }

...二叉树中结点值最大的结点的父结点。二叉链表的
答：p = p->rchild;//走向p的右子树 } return OK;}【摘要】(2)已知非空二叉树采用二叉链存储，请写出一算法，找出二叉树中结点值最大的结点的父结点。二叉链表的结点定义如下: struct node {int key;struct node *lchild,*rchild;怎样回答【提问】亲～你好，很高兴为您服务，您的问题我已了解，稍...

设某棵二叉树中度数为0的结点数为N0,度数为1的结点数为N1,若采用二叉链...
答：先算二叉树的节点数 其度为2的节点数为度为0的个数-1 所以节点的总数为 N0+N0-1+N1=2N0+N1-1，则总共的指针数为 2*(2N0+N1-1)= 4N0+2N1-2 所以空余的指针数为 4N0+2N1-2-2N0-N1+1=2N0+N1-1 但是 根节点是没有指针指向的所以结果为 2N0+N1 ...

设一棵非空的二叉排序树用二叉链表表示,
答：思想：1.先查找到该节点。2.然后遍历该节点右子树的所有叶子节点 （A：可以将指针移向其右孩子，然后遍历该指针整个树 B：也可以直接中序遍历整个树，不遍历其左边的叶子节点 C：也可以直接用栈对该树遍历。这里我用的第一种方法）下面是我编的代码（已调试正确），不懂再问我哈。include<stdio.h...

以二叉链表为存储结构,写出求二叉树高度和宽度的算法
答：Int Depth(BinTree *T){int dep1,dep2;if(T==Null) return(0);else{dep1=Depth(T->lchild);dep2=Depth(T->rchild);if(dep1>dep2) return(dep1+1);else return(dep2+1);} 树的宽度：按层遍历二叉树，采用一个队列q，让根结点入队列，最后出队列，若有左右子树，则左右子树根结点入...

急!~编写一个C++语言程序,对二叉树实现操作
答：4. 将二叉树每个结点的左右子树交换位置。【数据描述】//- - - - - - 二叉树的二叉链表存储表示 - - - - - - - typedef struct BiTNode{ TElemType data;Struct BiTNode * lchild, * rchild; //左右孩子指针 }BiTNode, * BiTree;【算法描述】1. 建立一棵二叉树 Status Create...