3.1 树与树的表示
3.1.1 查找的方法
@H_403_11@ 查找
3.1.2 树
@H_403_11@ 树
定义: @H_403_11@ n(n≥0) 个结点构成的有限集合。
- 当 @H_403_11@ n=0 时,称为 空树 ;
-树中有一个称为“ 根(Root ) ”的特殊结点, 用 r 表示;
- 其余结点可分为m(m>0) 个 互不相交的 有限集,其中每个集合本身又是一棵树,称为原来树的“ 子树 (SubTree )”。@H_403_11@ 树的性质
@H_403_11@ 树的表示
儿子-兄弟表示法
所需的总空间为 @H_403_11@ @H_324_403@@H_569_404@3N (N为节点数)。
3.2 二叉树及存储结构
@H_403_11@ 二叉树
定义:一个有穷的结点集合。
- 这个集合 可以为空;
- 若不为空,则它是由 根结点 和称为其 左子树 @H_403_11@ TL 和 右子树 @H_403_11@ TR 的两个不相交的二叉树组成。@H_403_11@ 特殊二叉树
@H_403_11@ 二叉树的性质
@H_403_11@ 二叉树的存储结构
顺序存储(主要针对 @H_403_11@ 完全二叉树 );
链式存储
@H_403_11@ 在此处再次说一说 :
typedef struct PloyNode *Polynomial;//这句有什么用呢?
typedef struct PolyNode{//这两个typedef有什么联系吗?
int coef;
int expon;
Polynomial link;//这里是定义了一个相当于next后继指针吗?
}
如果按这样定义好了之后,如何定义一个这样的链表?@H_403_11@ 网上有一个经典的解释 :
1.typedef struct PloyNode *Polynomial;
这句是说:定义了一个结构体变量的指针,以后你可以直接用Polynomial来代表struct PolyNode *这个数据.
2.typedef struct PolyNode{
int coef;
int expon;
Polynomial link; }
这个也是一个定义,定义了一个结构体变量,简化了结构体变量的定义。你可以用PolyNode来代表整个结构体变量。再来说一下他们之间的联系: 第一个是定义的一个简化的指针变量:struct PolyNode * ; 第二个定义了一个简化的结构体变量PolyNode来代替:typedef struct PolyNode;
综上是否可理解为:指针变量Polynomial具有结构体PolyNode的结构,即L=(Polynomial)malloc(sizeof(PolyNode))这样就生成一个新的PloyNode结点。
3.3 二叉树的遍历
运用递归函数进行遍历
非递归遍历(使用堆栈)
层序遍历(使用队列)
例1:输出二叉树中的 叶子结点。
例2. 求二叉树的高度
例3. 由 任意两种 遍历序列确定二叉树,对么?(其中一个必须是中序遍历)
3.4 小白专场:树的同构
程序:
//输入样例1(对应图1):
//
//8
//A 1 2
//B 3 4
//C 5 -
//D - -
//E 6 -
//G 7 -
//F - -
//H - -
//8
//G - 4
//B 7 6
//F - -
//A 5 1
//H - -
//C 0 -
//D - -
//E 2 -
//输出样例1:
//
//Yes
//输入样例2(对应图2):
//
//8
//B 5 7
//F - -
//A 0 3
//C 6 -
//H - -
//D - -
//G 4 -
//E 1 -
//8
//D 6 -
//B 5 -
//E - -
//H - -
//C 0 2
//G - 3
//F - -
//A 1 4
//输出样例2:
//
//No
//给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2,则我们称两棵树是“同构”的。
//author: Paul-Huang
//data: 18/6/2017
#include<stdio.h>
#include <stdlib.h>
#include<process.h>//引入头文件
#define MaxTree 10
#define Null -1
#define ElementType char
#define Tree int
//建立动态链表
struct TreeNode
{
ElementType node;
Tree Left;
Tree Right;
}Tree1[MaxTree],Tree2[MaxTree];
Tree BuildTree(struct TreeNode T[]);
int Isomprphic(Tree root1,Tree root2);
int main()
{
Tree R1,R2;
R1 = BuildTree(Tree1);
R2 = BuildTree(Tree2);
if (Isomprphic(R1,R2)){
printf("Yes\n");
}
else{
printf("No\n");
}
system("pause");//暂停往下执行 按下任意键继续
return 1;
}
Tree BuildTree(struct TreeNode T[])
{
Tree check[MaxTree],Root = Null; //root = Null 空树则返回Null
char cl,cr;
int i,N;
scanf("%d\n",&N);
if (N) {
for ( i = 0; i < N; i++)
check[i] = 0;
//输入数值,并建立链表
for (i = 0; i < N; i++)
{
scanf("%c %c %c\n",&T[i].node,&cl,&cr);
if (cl != '-'){
T[i].Left = cl - '0';
check[T[i].Left] = 1;
}
else{
T[i].Left = Null;
}
if (cr != '-'){
T[i].Right = cr - '0';
check[T[i].Right] = 1;
}
else{
T[i].Right = Null;
}
}
//查找二叉树的根
for (i = 0; i < N; i++)
if (!check[i])
break;
Root = i;
}
return Root;
}
int Isomprphic(Tree root1,Tree root2)
{
if ((root1 == Null) && (root2 == Null))/* both empty */
return 1;
if (((root1 == Null) && (root2 != Null)) || ((root1 != Null) && (root2 == Null)))
return 0;/* one of them is empty */
if (Tree1[root1].node != Tree2[root2].node)
return 0; /* roots are different */
if ((Tree1[root1].Left == Null) && (Tree2[root2].Left == Null))
/* both have no left subtree */
return Isomprphic(Tree1[root1].Right,Tree2[root2].Right);
if ((Tree1[root1].Right == Null) && (Tree2[root2].Right == Null))
/* both have no right subtree */
return Isomprphic(Tree1[root1].Left,Tree2[root2].Left);
if ((Tree1[root1].Left != Null) && (Tree2[root2].Left != Null) &&
((Tree1[Tree1[root1].Left].node) == (Tree2[Tree2[root2].Left].node)))
/* no need to swap the left and the right */
return (Isomprphic(Tree1[root1].Left,Tree2[root2].Left)&&
Isomprphic(Tree1[root1].Right,Tree2[root2].Right));
else/* need to swap the left and the right */
return (Isomprphic(Tree1[root1].Left,Tree2[root2].Right) &&
Isomprphic(Tree1[root1].Right,Tree2[root2].Left));
}