数据结构代码

第5章 树

typedef struct BiTNode{
	ElemType data;
	struct BiTNode *lchild,*rchild;
}BiTnode,*BiTtree;
1
2
3
4

线索二叉树的存储结构
typedef struct ThreaNode{
	ElemType data;
	int ltag,rtag;
	struct BiTNode *lchild,*rchild;
}ThreaNode,*ThreaNode;
1
2
3
4
5
6

1先序遍历-递归

先序遍历-递归
void preOrder1(BiTree T){
	if(T!=Null){
		visit（T）;
		preOrder(T->lchild);
		preOrder(T->rchild);
	}
}
1
2
3
4
5
6
7
8

2先序遍历-非递归

先序遍历-非递归
void preOrder2(BiTree T){
InitStack(S);	//初始化栈S
BiTree P=T;	//p是遍历指针
	while(p||!IsEmpty(s)){	//p和s都非空
		if(p){
			visit(p);
			pop(s,p);
			p=p->lchild;
		}
		else{
			pop(s,p);
			p=p->rchild;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3中序遍历-递归

中序遍历-递归
void InOrder1(BiTree T){
	if(T!=Null){
	InOrder(T->lchild);
	visit(T);
	InOrder(T->rchild);
	}
}
1
2
3
4
5
6
7
8

4中序遍历非递归

中序遍历非递归
思想：
1、沿着根的左孩子，依次入栈，直到左孩子为空
2、栈顶元素出栈并访问
3、右孩子为空继续执行第二部，否则执行第一步
void InOrder2(BiTree T){
InitStack(S);	//初始化栈S
BiTree P=T;	//p是遍历指针
	while(p||!IsEmpty(s)){	//p和s都非空
		if(p){
			pop(s,p);
			p=p->lchild;
		}
		else{
			pop(s,p);
			visit(p);
			p=p->rchild;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

后序遍历-递归

后序遍历-递归
void PostOrder1(BiTree T){
	if(T!=Null){
	InOrder(T->lchild);
	InOrder(T->rchild);
	visit(T);
	}
}
1
2
3
4
5
6
7
8

层次遍历

层次遍历
算法思想
根结点入队，出队访问根结点，若它有左子树将左子树入队，若有右子树，将右子树入队，然后出队，访问出队结点
void LevelOrder(BiTree T){
	InitQueue(Q);	//初始化辅助队列
	BiTree p;	//定义一个p指针
	EnQueue(Q,T);	//将根结点入队
	while(!InitQueue(Q)){
		DeQueue(Q,p);
		if(p->lchild!=Null){
			EnQueue(Q,p->lchild);
		}
		if(p->rchild!=Null){
			EnQueue(Q,p->rchild)
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

树的综合运用

求结点的双亲

求结点的孩子结点

求二叉树的深度

二叉树的叶子结点个数

判断两颗二叉树是否相等

05．假设二叉树采用二叉链表存储结构，设计一个非递归算法求二叉树的高度。
06、设一棵二叉树中各结点的值互不相同，其先序遍历序列和中序遍历序列分别存于两个一
维数组A [ 1…n]和B[ 1…n]中，试编写算法建立该二叉树的二叉链表。
07.二叉树按二叉链表形式存储，写一个判别给定二叉树是否是完全二叉树的算法。
08．假设二叉树采用二叉链表存储结构存储，试设计一个算法，计算一棵给定二叉树的所有双分支结点个数。
09.设树B是一棵采用链式结构存储的二叉树，编写一个把树B中所有结点的左、右子树进行交换的函数。
10.假设二叉树采用二叉链存储结构存储，设计一个算法，求先序遍历序列中第k ( 1 ≤k <二叉树中结点个数）个结点的值。
11.已知二叉树以二叉链表存储，编写算法完成:对于树中每个元素值为x的结点，删去以它为根的子树，并释放相应的空间。
12.在二叉树中查找值为×的结点，试编写算法（用C语言）打印值为×的结点的所有祖
先，假设值为×的结点不多于一个。
13.设一棵二叉树的结点结构为(LLINK,INFO,RLINK)，ROOT为指向该二叉树根结点的指针，p和q分别为指向该二叉树中任意两个结点的指针，试编写算法ANCESTOR(ROOT,p,q,r)，找到p和q的最近公共祖先结点r。
14．假设二叉树采用二叉链表存储结构，设计一个算法，求非空二叉树b的宽度（即具有结点数最多的那一层的结点个数)。
15．设有一棵满二叉树（所有结点值均不同)，已知其先序序列为pre，设计一个算法求其后序序列post。
16，设计一个算法将二叉树的叶结点按从左到右的顺序连成一个单链表，表头指针为head。
二叉树按二叉链表方式存储，链接时用叶结点的右指针域来存放单链表指针。
17．试设计判断两棵二叉树是否相似的算法。所谓二叉树T和T相似，指的是T和Tz都是
空的二叉树或都只有一个根结点;或T的左子树和T的左子树是相似的，且T的右子树和T的右子树是相似的。
18.写出在中序线索二叉树里查找指定结点在后序的前驱结点的算法。
19.【2014统考真题】二叉树的带权路径长度（WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T，采用二叉链表存储，结点结构为left weight right
其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针，请设计求T的WPL的算法，要求:
1)给出算法的基本设计思想。
2）使用C或C++语言，给出二叉树结点的数据类型定义。
3）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。