| 失效链接处理 |
|
算法设计题_树 PDF 下载
本站整理下载：
提取码：menh
相关截图：
 主要内容：
二叉树的链式存储结构
typedef struct BiTNode{
ElemType data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
2. 二叉树的遍历 （1）递归先序遍历：
void PreOrder(BiTree T){
if (T != NULL){
visit(T);
PreOrder(T ->lchild);
PreOrder(T ->rchild);
} } （2）非递归先序遍历
void preOrder(BiTree b){
BiTree *stack[20], *p;
int top;
if (b != NULL){
top = 1;
stack[top] = b; // 根结点入栈
while (top > 0){
p = stack[top]; // 出栈访问
top--;
visit(p);
if (p ->rchild != NULL) // 右孩子入栈
stack[++top] = p ->rchild;
if (p ->lchild != NULL) // 左孩子入栈
stack[++top] = p ->lchild;
}
} } （3）非递归中序遍历
void InOrder(Bitree T){
InitStack(S); // 初始化栈
BiTree p = T; // p 是遍历指针
while (p || !IsEmpty(S)){
if (p){ // 根指针入栈，遍历左子树
Push(S, p);
p = p ->lchild;
} else { // 根指针出栈，访问根结点，遍历右子树
Pop(S, p);
visit(p);
p = p ->rchild;
1
}
}//while
}（4）非递归后续遍历（应用访问很广，极其重要）
void PostOrder(BiTree T){
InitStack(S);
BiTree p = T, r = NULL;
while (p || !IsEmpty(S)){
if (p){ // 走到最左边
push(S, p);
p = p ->lchild;
} else {
GetTop(S, p);
// 右子树存在，且未被访问
if (p ->rchild && p ->rchild != r){
p = p ->rchild; // 转向右子树
push(S, p);
p = p ->lchild; // 再走向最左
} else {
pop(S, p);
visit(p); // 访问该结点
r = p; // 记录最近访问过的结点
p = NULL; // 结点访问完后，重置 p 指针
}
}// else
}// while
}（5）层次遍历(很重要)
void LevelOrder(BiTree T){
InitQueue(Q); // 初始化队列
Bitree p; // p 为遍历结点
EnQueue(Q, T); // 根结点入队
while (!IsEmpty(Q)){
DeQueue(Q, p);
visit(p);
if (p ->lchild != NULL) // 左孩子入队
EnQueue(Q, p ->lchild);
if (p ->rchild != NULL) // 右孩子入队
EnQueue(Q, p ->rchild);
} }
层次遍历的应用： （1） 求某一层的叶子数 / 分支结点。 （2） 求树的宽度。 （3） 非递归求高度。
（4） 判断是否是完全二叉树。
|
| Java1234官方群25： | 
|
| Java1234官方群25： | 838462530 |
苏公网安备 32061202001004号
