4. 设二叉树的存储结构为二叉链表，试写出算法（C函数）：将所有结点的左右子树互换。

2024-05-09

1. 4. 设二叉树的存储结构为二叉链表，试写出算法（C函数）：将所有结点的左右子树互换。

二叉树 (binary tree) 是另一种树型结构，它的特点是每个结点至多只有二棵子 树 (即二叉树中不存在度大于 2的结点 )，并且，二叉树的子树有左右之分，其次序不能任意颠倒 . 二叉树是一种数据结构 :

                       Binary_tree=(D,R)

其中： D是具有相同特性的数据元素的集合 ;若 D等于空 ,则 R等于空称为空的二叉树 ;若 D等于空则 R是 D上某个二元关系 H的集合，即 R=，且 
(1) D 中存在唯一的称为根的元素 r，它的关系 H下无前驱 ; 
(2) 若 D-不等于空，则 D-=，且 Dl交 Dr等于空 ;
(3) 若 Dl不等于空 ,则在 Dl中存在唯一的元素 xl,〈 r,xl〉属于 H，且存在 Dl上的关系 Hl属于 H； 若 Dr不等于空 ,则在 Dr中存在唯一的元素 xr,〈   r,xr〉 >属于 H, 且存 Dr上的关 系 Hr属于 H； H=; 
(4) (Dl, Hl) 是一棵合本定义的二叉树，称为根 r的左子树 ,(Dr,Hr)是一棵符合定义的二叉树，称为根的右子树。 

其中，图 6.2 是各种形态的二叉树 . 



(1) 为空二叉树    (2)只有一个根结点的二叉树     (3)右子树为空的二叉树    (4)左子树为空的二叉树    (5)完全二叉树 

二叉树的基本操作： 

(1)INITIATE(BT ） 初始化操作。置 BT为空树。 

(2)ROOT(BT)\ROOT(x) 求根函数。求二叉树 BT的根结点或求结点 x所在二叉树的根结点。
  若 BT是空树或 x不在任何二叉树上，则函数值为 “空 ”。 

(3)PARENT(BT,x) 求双亲函数。求二叉树 BT中结点 x的双亲结点。若结点 x是二叉树 BT 的根结点
   或二叉树 BT中无 x结点，则函数值为 “空 ”。 

(4)LCHILD(BT,x) 和 RCHILD(BT,x) 求孩子结点函数。分别求二叉树 BT中结点 x的左孩 子和右孩子结点。
   若结点 x为叶子结点或不在二叉树 BT中，则函数值为 “空 ”。 

(5)LSIBLING(BT,x) 和 RSIBING(BT,x) 求兄弟函数。分别求二叉树 BT中结点 x的左兄弟和右兄弟结点。
   若结点 x是根结点或不在 BT中或是其双亲的左 /右子树根 ,则函树值 为 “空 ”。 

(6)CRT_BT(x,LBT,RBT) 建树操作。生成一棵以结点 x为根，二叉树 LBT和 RBT分别为左， 右子树的二叉树。 

(7)INS_LCHILD(BT,y,x) 和 INS_RCHILD(BT,x) 插入子树操作。将以结点 x为根且右子树为空的二叉树
  分别置为二叉树 BT中结点 y的左子树和右子树。若结点 y有左子树 /右子树，则插入后是结点 x的右子树。 

(8)DEL_LCHILD(BT,x) 和 DEL-RCHILD(BT,x) 删除子树操作。分别删除二叉树 BT中以结点 x为根的左子树或右子树。
   若 x无左子树或右子树，则空操作。 

(9)TRAVERSE(BT) 遍历操作。按某个次序依此访问二叉树中各个结点，并使每个结点只被访问一次。 

(10)CLEAR(BT) 清除结构操作。将二叉树 BT置为空树。 

5.2.2   二叉树的存储结构

一 、顺序存储结构 
        连续的存储单元存储二叉树的数据元素。例如图 6.4(b)的完全二叉树 , 可以向量 (一维数组 ) bt(1:6)作它的存储结构，将二叉树中编号为 i的结点的数据元素存放在分量 bt[i]中 ,如图 6.6(a) 所示。但这种顺序存储结构仅适合于完全二叉树 ,而一般二叉树也按这种形式来存储 ,这将造成存 贮浪费。如和图 6.4(c)的二叉树相应的存储结构图 6.6(b)所示，图中以 “0”表示不存在此结点 . 



二、 链式存储结构 
    由二叉树的定义得知二叉树的结点由一个数据元素和分别指向左右子树的两个分支构成 ,则表 示二叉树的链表中的结点至少包含三个域 :数据域和左右指针域 ,如图 (b)所示。有时 ,为了便于找 到结点的双亲 ,则还可在结点结构中增加一个指向其双亲受的指针域，如图 6.7(c)所示。 



5.3  遍历二叉树         

         遍历二叉树 (traversing binary tree)的问题， 即如何按某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。 其中常见的有三种情况：分别称之为先 (根 )序遍历，中 (根 )序遍历和后 (根 )序遍历。 

5.3.1 前序遍历

    前序遍历运算：即先访问根结点，再前序遍历左子树，最后再前序遍历右子树。前序遍历运算访问二叉树各结点是以根、左、右的顺序进行访问的。例如： 



    按前序遍历此二叉树的结果为： Hello!How are you? 

proc preorder(bt:bitreprtr) 
  if (bt<>null)[ 
    print(bt^); 
    preorder(bt^.lchild); 
    preorder(bt^.rchild);] 
end; 

5.3.2 中序遍历

    中序遍历运算：即先中前序遍历左子树，然后再访问根结点，最后再中序遍历右子树。中序遍历运算访问二叉树各结点是以左、根、右的顺序进行访问的。例如： 



    按中序遍历此二叉树的结果为： a*b-c 

proc inorder(bt:bitreprtr)
  if (bt<>null)[ 
    inorder(bt^.lchild); 
    print(bt^); 
    niorder(bt^.rchild);] 
end; 

5.3.3 后序遍历

    后序遍历运算：即先后序遍历左子树，然后再后序遍历右子树，最后访问根结点。后序遍历运算访问二叉树各结点是以左、右、根的顺序进行访问的。例如： 



    按后序遍历此二叉树的结果为： Welecome to use it! 

proc postorder(bt:bitreprtr) 
  if (bt<>null)[ 
    postorder(bt^.lchild); 
    postorder(bt^.rchild);] 
    print(bt^); 
end; 

  

五、例：
   1.用顺序存储方式建立一棵有31个结点的满二叉树，并对其进行先序遍历。
   2.用链表存储方式建立一棵如图三、4所示的二叉树，并对其进行先序遍历。
   3.给出一组数据：R=，试编程序，先构造一棵二叉树，然后以中序遍历访问所得到的二叉树，并输出遍历结果。
   4.给出八枚金币a,b,c,d,e,f,g,h，编程以称最少的次数，判定它们蹭是否有假币，如果有，请找出这枚假币，并判定这枚假币是重了还是轻了。
       
 
中山纪念中学三鑫双语学校信息学竞赛组编写 2004.7.15

4. 设二叉树的存储结构为二叉链表，试写出算法（C函数）：将所有结点的左右子树互换。

2. 假设二叉树以二叉链表作为存储结构，试设计一个计算二叉树叶子结点树的递归算 法 要求用递归算法啊

1、首先要定义两个类：结点类和二叉树类。

2、二叉树类的组成：建立树的函数、遍历函数、删除函数。求结点数函数。

3、采用递归的思想，遇到标识符表示该结点为空，否则开辟空间创建新结点，同时调用递归开辟左结点和右结点。

4、前序遍历函数。

5、删除函数的思路：如果当前结点不为空，采用递归访问左结点和右结点、回收当前结点的空间。

6、求结点数函数的思路：如果当前结点为空，返回0、如果当前结点的左右孩子都为空，放回1。

7、求树高函数的思路：如果当前结点为空，返回0、递归访问左孩子和右孩子、比较左右孩子的高度，返回 较大值+1。

3. 数据结构试题；设一棵二叉树以二叉链表为存储结构，试写一算法求该二叉树上度为2的结点个数

算法步骤：
设根节点为 r。
情况1，如果 r 既有左孩子又有右孩子，则返回 1 + 递归求左子树度为2节点个数 + 递归求右子树度为2节点个数。
情况2，如果 r 只有左孩子，则返回 递归求左子树度为2节点个数。
情况3，如果 r 只有右孩子，则返回 递归求右子树度为2节点个数。
情况4，如果 r 既没有左孩子又没有右孩子，则返回 0。

数据结构试题；设一棵二叉树以二叉链表为存储结构，试写一算法求该二叉树上度为2的结点个数

4. 这是一道数据结构的题：试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结构

用递归：
a=当前节点是否为排序树，是为1，不是为0
f(x)=1 当x为叶节点 
f(x)= a&&f(x->lchid)&&f(x-rchild)  当x非叶节点
----------------------------------------------------------------------
int IsAVTree(BiTree t)
{
int a=1;
if(t->Child==NULL&&t->Rchild==NULL)  return 1;  //叶子节点判断
if((t->Lchild->data>t->data)||(t->Rchild->datadata)) 
{
a=0;
a=a&&(isAVTree(t->Lchild))&&(IsAVTree(t->Rchild));
}
return a;
}
扩展资料：构成递归需具备的条件：
一、子问题须与原始问题为同样的事，且更为简单；
二、不能无限制地调用本身，须有个出口，化简为非递归状况处理。
在数学和计算机科学中，递归指由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况。
例如，下列为某人祖先的递归定义：
某人的双亲是他的祖先（基本情况）。某人祖先的双亲同样是某人的祖先（递归步骤）。斐波纳契数列（Fibonacci Sequence），又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8。
参考资料来源：百度百科-递归

5. 以二叉链表为存储结构,写出求二叉树高度和宽度的算法

原题：
以二叉链表为存储结构，分别写出求二叉树高度及宽度的算法。所谓宽度是指在二叉树的各层上，具有结点数最多的那一层上的结点总数。
标准答案：
①求树的高度
思想：对非空二叉树，其深度等于左子树的最大深度加1。
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，让根结点入队列，最后出队列，若有左右子树，则左右子树根结点入队列，如此反复，直到队列为空。
int
Width(BinTree
*T)
{
int
front=-1,rear=-1;/*
队列初始化*／
int
flag=0,count=0,p;
/*
p用于指向树中层的最右边的结点，标志flag记录层中结点数的最大值。*／if(T!=Null)
{
rear++;
q[rear]=T;
flag=1;
p=rear;
}
while(front<p)
{
front++;
T=q[front];
if(T->lchild!=Null)
{
rear++;
q[rear]=T->lchild;
count++;
}
if(T->rchild!=Null)
{
rear++;
q[rear]=T->rchild;
count++;
}
if(front==p)
/*
当前层已遍历完毕*/
{
if(flag<count)
flag=count;
count=0;
p=rear;
/*
p指向下一层最右边的结点*/
}
}
/*
endwhile*/
return(flag);
}

以二叉链表为存储结构,写出求二叉树高度和宽度的算法

6. 假定一棵二叉树用二叉链表存储试编写求出二叉树中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度结点个数

7. 编写递归算法，按先序顺序输出二叉链表存储的二叉树中所有度为2的结点

编写递归算法，按先序顺序输出二叉链表存储的二叉树中所有度为2的结点 您好亲，错误。二叉树中，并不是每个结点的度都是2。结点的度，是指它直接子结点的个数。对于二叉树，如果一个结点的左右子结点都存在，度是2;如果只有左子结点或右子结点，度是1;如果是叶子结点，度为0。在一棵非空二叉树里，可能没有度为1或2的结点，但必然有度为0的结点。并且，度为0的结点数总是比度为2的结点数多1。因此，题目表述不成立，二叉树中，并不是每个结点的度都是2，只能说度最大是2。希望可以帮到您！【摘要】
编写递归算法，按先序顺序输出二叉链表存储的二叉树中所有度为2的结点【提问】
编写递归算法，按先序顺序输出二叉链表存储的二叉树中所有度为2的结点 您好亲，错误。二叉树中，并不是每个结点的度都是2。结点的度，是指它直接子结点的个数。对于二叉树，如果一个结点的左右子结点都存在，度是2;如果只有左子结点或右子结点，度是1;如果是叶子结点，度为0。在一棵非空二叉树里，可能没有度为1或2的结点，但必然有度为0的结点。并且，度为0的结点数总是比度为2的结点数多1。因此，题目表述不成立，二叉树中，并不是每个结点的度都是2，只能说度最大是2。希望可以帮到您！【回答】

编写递归算法，按先序顺序输出二叉链表存储的二叉树中所有度为2的结点

8. 以二叉链表为存储结构,写出求二叉树高度和宽度的算法

原题:
以二叉链表为存储结构，分别写出求二叉树高度及宽度的算法。所谓宽度是指在二叉树的各层上，具有结点数最多的那一层上的结点总数。
标准答案:
①求树的高度
思想:对非空二叉树，其深度等于左子树的最大深度加1。
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，让根结点入队列，最后出队列，若有左右子树，则左右子树根结点入队列，如此反复，直到队列为空。
int
Width(BinTree
*T)
{
int
front=-1,rear=-1;/*
队列初始化*/
int
flag=0,count=0,p;
/*
p用于指向树中层的最右边的结点，标志flag记录层中结点数的最大值。*/if(T!=Null)
{
rear++;
q[rear]=T;
flag=1;
p=rear;
}
while(front<p)
{
front++;
T=q[front];
if(T->lchild!=Null)
{
rear++;
q[rear]=T->lchild;
count++;
}
if(T->rchild!=Null)
{
rear++;
q[rear]=T->rchild;
count++;
}
if(front==p)
/*
当前层已遍历完毕*/
{
if(flag<count)
flag=count;
count=0;
p=rear;
/*
p指向下一层最右边的结点*/
}
}
/*
endwhile*/
return(flag);
}
最新文章
热门文章
推荐阅读