已知一棵二叉树是以二叉链表的形式存储的,其结点结构说明如下: struct node { int data; struct node *
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
先前序遍历整个二叉树,找到符合要求的结点,然后后序遍历该结点的整个子树,逐一释放结点。
//假设二叉树结构体如下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; }}
#include<stdlib.h>
/*①、求出以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;
}
进百度我的空间,里面有
地址:http://hi.baidu.com/wehgjh/home
或者你百度jkgyu的空间也行
下面是运行后截图
二叉排序树定义
首先二叉排序树也是一棵二叉树,所谓二叉树,就是“任何节点最多只允许两个子节点”,这两个子节点称为左右子节点。二叉排序树通常采用二叉链表作为存储结构。中序遍历二叉排序树可得到一个依据关键字的有序序列,一个无序序列可以通过构造一棵二叉排序树变成一个有序序列,构造树的过程即是对无序序列...
一棵度为2的树与一棵二叉树有何区别?
2、分支不同 度为2的树有两个分支,但分支没有左右之分;一棵二叉树也有两个分支,但有左右之分,左右子树的次序不能随意颠倒。3、次序不同 度为2的树从形式上看与二叉树很相似,但它的子树是无序的,而二叉树是有序的。即,在一般树中若某结点只有一个孩子,就无需区分其左右次序,而在二叉...
二叉树是一棵结点的度最大为二的树 错的吗.我怎么觉得对的
这是对的把.在树结构中,一个结点所拥有的后件的个数称为该结点的度,所有结点中最大的度称为树的度.二叉树:不存在度大于2的结点.五种基本形态:空二叉树,仅有根节点的二叉树,左子树为空的二叉树,右子树为空的二叉树,左右子树均不为空的二叉数 ...
...要求返回二叉树T的后序序列的第一个节点的指针 要求不用递归不用...
InitBiTree(T); \/\/ 初始化二叉树T printf("按先序次序输入二叉树中结点的值,输入0表示节点为空,输入范例:1 2 0 0 3 0 0\\n");CreateBiTree(T); \/\/ 建立二叉树T printf("先序递归遍历二叉树:\\n");PreOrderTraverse(T,visit); \/\/ 先序递归遍历二叉树T printf("\\n中序递归遍历二叉...
20.一棵度为2的有序树与一棵二叉树有何区别?
答:一棵度为二的有序树与一棵二叉树的区别在于:有序树的结点次序是相对于另一结点而言的,如果有序树中的子树只有一个孩子时,这个孩子结点就无须区分其左右次序,而二叉树无论其孩子数是否为2,均需确定其左右次序,也就是说二叉树的结点次序不是相对于另一结点而言而是确定的。希望我的回答对你...
二叉树的基本概念
2、二叉树的性质 性质1:二叉树第i层上的结点数目最多为2i-1(i>=1)性质2:深度为k的二叉树至多有2k-1个结点(k>=1)性质3:包含n个结点的二叉树的高度至少为(log2n)+1 性质4:在任意一棵二叉树中,若终端结点的个数为n0,度为2的结点数为n2,则n0=n2+1 3、性质4的证明 性质4:在...
已知一棵二叉树前序遍历和中序遍历分别是什么?
已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF,则该二叉树的后序遍历是DGEBHFCA。前序遍历的第一个节点为根节点,由前序遍历可知,A为根节点。中序遍历的根节点前面的节点均为左子树的节点,所以左子树上的节点为DBGE。去掉根节点和左子树节点,右子数节点为CHF。前序遍历的第二个...
如何判断一棵二叉树是左子树还是右子树?
端,所以HG是F的右子树;5、由于H、G在后序遍历序列G最后出现,所以G是H, G中的根,再看 中序中G左端只有一个H,所以H是G的左子树,得到最终原始二叉树。需要注意的几点:1、根是相对的,对于整棵树而言只有一个根,但对于每棵子树而言,又有自己的根。2、前序遍历时,一棵树的根永远在左...
什么是二叉树?
二叉树的每个结点至多只有二棵子树(不存在度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。二叉树的第i层至多有2^{i-1}个结点;深度为k的二叉树至多有2^k-1个结点;对任何一棵二叉树T,如果其终端结点数为n_0,度为2的结点数为n_2,则n_0=n_2+1。 一棵深度为k,且有2^k-1个节点的二叉树,...
二叉树是指度为2的_树。一棵结点数为N的二叉树,其所有结点的度的总和...
二叉树形式:O \/ \\ O O \/ \\ O O 我们看到,每个结点(除根结点外)都有一个条线进入,另外度等于所有线条的和。所以节点数为N的二叉树,结点的度总和为 N - 1
阚蓓芎香:[答案] #include#include/*①、求出以T为根的子树的结点个数.②、求出以T为根的子树的高度.*/typedef struct node{ int data; struct node * left; struct node * right;}BiTNode,*BiTree;/*①、求出以T为根的子树的结点...
海宁市19273498910: 已知一个二叉树存储于二叉链表中, - ?
阚蓓芎香: 定义单向链表,储存内容为二叉树节点的指针.判断当前二叉树节点是否还有子树,有的话就将子树节点一并存入链表,然后链表指针指向下一节点,检查其中的二叉树节点.如此循环,直到所有二叉树节点都存入链表为止.此时链表的长度就是节点总数.求深度需要两个这样的链表,进行广度优先的便利,每完成一层深度加一,全部叶节点遍历完就能得出深度.
海宁市19273498910: 已知一棵二叉树采用二叉链表存放,写依程序,要求统计出二叉树中叶子的个数,并输出二叉树中非终端节点 - ?
阚蓓芎香: void countleaf(bitnode *t,int *c) { if(t!=null) { if (t->lchild==null && t->rchild==null) {*c=*c+1; } countleaf(t->lchild,c); countleaf(t->rchild,c); } return; } typedef struct bitnode { char data; struct bitnode *lchild, *rchild; }bitnode, *bitree;
海宁市19273498910: 设一棵二叉树以二叉链表为存储结构,试写出求该二叉树中所有叶子结点数的算法. - ?
阚蓓芎香: //我做了一个程序,可以实现二叉树的左右子树的交换功能,#include<iostream.h>/* 二叉树类型的定义(二叉链表形式储存) */ typedef char datatype; // 树的结点数据类型为字符型,可以根据需要修改 typedef struct node *pointer; // 定义二叉...
海宁市19273498910: 数据结构算法设计题1.已知一颗二叉树采用二叉链表存放,写一算法,要求统计出二叉树中叶子结点个数并输出(输出无顺序要求)1.已知一个带头结点的... - ?
阚蓓芎香:[答案] 某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素,则采用( )存储方式最节省运算时间.(A)...已知带头结点的单链表L中的结点是按整数值递增排列的,试写一算法,将值为x 的结点插入到表L中,使得L仍然有序
海宁市19273498910: 设一棵二叉树以二叉链表为存储结构 - ?
阚蓓芎香: void Leaf(BiTree T) {if(T=null){ return 0; } elseif(T->lchild==null&&T->rchild==null){ return 1; } else return leaves(T->lchild)+leaves(T->rchild); }
海宁市19273498910: 已知一棵二叉树以二叉链表为存储结构,编写如下程序:对于树中每一个元素值为x的结点,删去以它为根的子 - ?
阚蓓芎香: 先前序遍历整个二叉树,找到符合要求的结点,然后后序遍历该结点的整个子树,逐一释放结点.//假设二叉树结构体如下 struct binTree { int data; binTree *lchild; binTree *rchild; }*BiTree;//函数如下 BiTree find(BiTree node, int x) { if(node) { if(...
海宁市19273498910: 已知一棵完全二叉树采用链表存放,写一算法,要求统计出二叉树中非终端节点的个数 - ?
阚蓓芎香: 1、计算出树的深度d.2、因为是完全二叉树,所以非终端节点个数={2^(d-1)}-1//递归求树的深度 int depth(TreeNode *T) { if(T==NULL)return 0; else { return max(depth(T->left),depth(T->right))+1;} }//计算完全二叉树,非叶节点的个数 int countNode(TreeNode *T) { int d=depth(T); return pow(2,d-1)-1; }
海宁市19273498910: 【例】假设二叉树采用二叉链表存储,结点结构为(lchild,data,rchild). - ?
阚蓓芎香: 1 2 3 4 5 6 7 8intnode_cnt(TREE t) {intl=0,r=0,c=0;if(t->lchild) l=node_cnt(t->lchild);if(t->rchild) l=node_cnt(t->rchild);if(t->lchild == NULL && t->rchild == NULL) c=1;returnl+r+c; }
海宁市19273498910: 已知二叉树以二叉链表做为存储结构,阅读算法并回答下列问题:(1)该算法的功能是什么(2)算法中的n的作 - ?
阚蓓芎香: 该算法的功能是前序遍历二叉树,统计二叉树中含有左右两个孩子的结点的个数.n的作用是统计二叉树中含有左右两个孩子的结点的个数.