动画制作设计_b2c跨境电商_谷歌排名算法_网络营销的作用

二叉树的遍历

二叉树的遍历是二叉树的一种重要的操作，指按照某种顺序访问树中的每个节点，并且每个节点仅被访问一次。常见的遍历方式有四种：前序遍历、中序遍历、后序遍历和层次遍历（或称为广度优先遍历）。

二叉树的定义类型：

typedef struct
{ElemType data;struct BiNode *lchild,*rchild;
}BiNode,*BiTree;

1. 前序遍历（Preorder Traversal）：

首先访问根节点，然后递归地进行前序遍历左子树，最后递归地进行前序遍历右子树。

//pre
void preorder(BiTree T){if(T!=NULL){visit(T);preorder(T->lchild);preorder(T->rchild);}
}

非递归算法：

void preorder2(BiTree T){InitStack(S);BiTree p=t;if(p||isEmpty(S)){if (p){visit(p);push(S,p);p=p->lchild;}else{pop(S,p);p=p->rchild;}}
}

1. 中序遍历（Inorder Traversal）：

首先递归地进行中序遍历左子树，然后访问根节点，最后递归地进行中序遍历右子树。

void inorder(BiTree T){if(T!=NULL){inorder(T->lchild);visit(T);inorder(T->rchild)}
}

非递归算法：

void inprder2(BiTree T){InitStack(S);BiTree P=T;if(p||isEmpty(S)){if(P){push(S,P);P=P->lchild;}else{pop(S,P);visit(P);P=P->rchild;}}
}

 

1. 后序遍历（Postorder Traversal）：

首先递归地进行后序遍历左子树，然后递归地进行后序遍历右子树，最后访问根节点。

void postorder(BiTree T){if(T!=NULL){postorder(T->lchild);postorder(T->rchild);visit(T);}
}

1. 层次遍历（Level-order Traversal）：

从上到下、从左到右依次访问树的每个节点。这通常需要使用队列来实现。

void levelorder(BiTree T){InitQueue(Q);BiTree p;EnQueue(Q,T);while(isEmpty(Q)){DeQueue(Q,p);visit(p);if(p->lchild)EnQueue(Q,p->lchild);else if(p->rchild)EnQueue(p->rchild);}
}

线索二叉树（存储结构）

线索二叉树是二叉树的一种变种，主要用于解决二叉树在遍历过程中“指针空域”的浪费问题。在普通二叉树中，每个节点有两个指针域，分别指向左右子节点，但在很多情况下，这两个指针域可能为空，这些空指针域就称为“空域”。线索二叉树就是将这些空域利用起来，存储指向该节点在某种遍历次序下的前驱和后继节点的指针（或线索）。

线索二叉树的实现

1. 线索化：将二叉树中的空指针域改为线索的过程称为线索化。根据遍历方式的不同，可以构造出前序线索二叉树、中序线索二叉树和后序线索二叉树。

//线索二叉树定义的类型
typedef struct{`ElemType data;struct TreadNode * lchild,*rchild;int ltag,rtag;
}ThreadNode,*ThreadTree;//中序遍历线索化二叉树
void inthread(ThreadTree &p,ThreadTree &pre){if(p!=NULL){inthread(p->lchild,pre);if(p->lchild==NULL){p->lchild=pre;p->ltag=1;}if(pre!=NULL&&pre->rchild==NULL){pre->rchild=p;pre->rtag=1;}pre=p;inthread(p->rchild,pre);}
}//中序遍历构造线索二叉树
void createinorder(ThreadTree T){ThreadTree pre=NULL;if(T!=NULL){inthread(T,pre);pre->rchild=NULL;pre->rtag=1;}}//求线索二叉树的第一个结点
ThreadNode *FirstNode(ThreadNode *T){while(T->ltag!=1){T=T->lchild;}return T;
}//求线索二叉树的结点的下一个结点
ThreadNode *NextNode(ThreadNode *T){if(T->rtag==0)return FirstNode(T->rchild);elsereturn T->rchild;
}//中序遍历线索二叉树
void inorder(ThreadNode *T){for(ThreadNode *p=FirstNode(T);p!=NULL;p=NextNode(p)){visit(p);}
}

1. 线索的表示：

   • 引入两个布尔标志，ltag 和 rtag，分别表示左指针域和右指针域是否为线索。若 ltag=1，则 lchild 指向前驱；若 ltag=0，则 lchild 指向左子树。同理，若 rtag=1，则 rchild 指向后继；若 rtag=0，则 rchild 指向右子树。

2. 遍历：在中序线索二叉树中，从根节点开始，若 ltag=1，则直接通过 lchild 访问前驱节点；否则，递归遍历左子树。遍历完左子树后，访问根节点，然后根据 rtag 决定是否直接通过 rchild 访问后继节点或递归遍历右子树。

线索二叉树的优点

• 节省空间：不需要额外的空间来存储遍历的结果。
• 简化遍历：通过线索，可以快速找到前驱和后继节点，无需回溯。
• 引入线索二叉树的目的是加快查找结点前驱和后继的速度。

线索二叉树的缺点

• 空间利用率：虽然节省了指针空域，但增加了 ltag 和 rtag 的存储开销。
• 灵活性：线索二叉树只能适应一种遍历方式，如果需要其他遍历方式，需要重新线索化。

注意：

后续线索二叉树上找后继时需要知道双亲结点，即需采用带标志域的三叉链表作为存储结构。

线索二叉树是数据结构中一种高效利用空间并简化遍历操作的方法，特别适用于需要频繁遍历但不修改树结构的场景。