二叉树递归与非递归遍历算法

㈠ c语言实现二叉树的先序,中序,后序的递归和非递归算法和层次遍历算法

#include<malloc.h> // malloc()等
#include<stdio.h> // 标准输入输出头文件，包括EOF(=^Z或F6)，NULL等
#include<stdlib.h> // atoi()，exit()
#include<math.h> // 数学函数头文件，包括floor()，ceil()，abs()等

#define ClearBiTree DestroyBiTree // 清空二叉树和销毁二叉树的操作一样

typedef struct BiTNode
{
int data; // 结点的值
BiTNode *lchild,*rchild; // 左右孩子指针
}BiTNode,*BiTree;

int Nil=0; // 设整型以0为空
void visit(int e)
{ printf("%d ",e); // 以整型格式输出
}
void InitBiTree(BiTree &T)
{ // 操作结果：构造空二叉树T
T=NULL;
}

void CreateBiTree(BiTree &T)
{ // 算法6.4：按先序次序输入二叉树中结点的值(可为字符型或整型，在主程中定义)，
// 构造二叉链表表示的二叉树T。变量Nil表示空(子)树。修改
int number;
scanf("%d",&number); // 输入结点的值
if(number==Nil) // 结点的值为空
T=NULL;
else // 结点的值不为空
{ T=(BiTree)malloc(sizeof(BiTNode)); // 生成根结点
if(!T)
exit(OVERFLOW);
T->data=number; // 将值赋给T所指结点
CreateBiTree(T->lchild); // 递归构造左子树
CreateBiTree(T->rchild); // 递归构造右子树
}
}

void DestroyBiTree(BiTree &T)
{ // 初始条件：二叉树T存在。操作结果：销毁二叉树T
if(T) // 非空树
{ DestroyBiTree(T->lchild); // 递归销毁左子树，如无左子树，则不执行任何操作
DestroyBiTree(T->rchild); // 递归销毁右子树，如无右子树，则不执行任何操作
free(T); // 释放根结点
T=NULL; // 空指针赋0
}
}

void PreOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数。修改算法6.1
// 操作结果：先序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T) // T不空
{ Visit(T->data); // 先访问根结点
PreOrderTraverse(T->lchild,Visit); // 再先序遍历左子树
PreOrderTraverse(T->rchild,Visit); // 最后先序遍历右子树
}
}

void InOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数
// 操作结果：中序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T)
{ InOrderTraverse(T->lchild,Visit); // 先中序遍历左子树
Visit(T->data); // 再访问根结点
InOrderTraverse(T->rchild,Visit); // 最后中序遍历右子树
}
}

void PostOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数
// 操作结果：后序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T) // T不空
{ PostOrderTraverse(T->lchild,Visit); // 先后序遍历左子树
PostOrderTraverse(T->rchild,Visit); // 再后序遍历右子树
Visit(T->data); // 最后访问根结点
}
}

void main()
{
BiTree T;
InitBiTree(T); // 初始化二叉树T
printf("按先序次序输入二叉树中结点的值,输入0表示节点为空，输入范例：1 2 0 0 3 0 0\n");
CreateBiTree(T); // 建立二叉树T
printf("先序递归遍历二叉树：\n");
PreOrderTraverse(T,visit); // 先序递归遍历二叉树T
printf("\n中序递归遍历二叉树：\n");
InOrderTraverse(T,visit); // 中序递归遍历二叉树T
printf("\n后序递归遍历二叉树：\n");
PostOrderTraverse(T,visit); // 后序递归遍历二叉树T
}

㈡ 二叉树先序遍历递归算法和非递归算法本质区别

在前面一文，说过二叉树的递归遍历算法（二叉树先根（先序）遍历的改进），此文主要讲二叉树的非递归算法，采用栈结构
总结先根遍历得到的非递归算法思想如下：
1）入栈，主要是先头结点入栈，然后visit此结点
2）while，循环遍历当前结点，直至左孩子没有结点
3）if结点的右孩子为真，转入1）继续遍历，否则退出当前结点转入父母结点遍历转入1）
先看符合此思想的算法：

[cpp] view plain print?
int (const BiTree &T, int (*VisitNode)(TElemType data))
{
if (T == NULL)
{
return -1;
}

BiTNode *pBiNode = T;
SqStack S;
InitStack(&S);
Push(&S, (SElemType)T);

while (!IsStackEmpty(S))
{
while (pBiNode)
{
VisitNode(pBiNode->data);
if (pBiNode != T)
{
Push(&S, (SElemType)pBiNode);
}
pBiNode = pBiNode->lchild;
}
if(pBiNode == NULL)
{
Pop(&S, (SElemType*)&pBiNode);
}
if ( pBiNode->rchild == NULL)
{
Pop(&S, (SElemType*)&pBiNode); //如果此时栈已空，就有问题
}
pBiNode = pBiNode->rchild;
}

return 0;
}

㈢ 二叉树的深度算法怎么算啊

二叉树的深度算法：
一、递归实现基本思想：
为了求得树的深度，可以先求左右子树的深度，取二者较大者加1即是树的深度，递归返回的条件是若节点为空，返回0
算法：
1
int
FindTreeDeep(BinTree
BT){
2
int
deep=0;
3
if(BT){
4
int
lchilddeep=FindTreeDeep(BT->lchild);
5
int
rchilddeep=FindTreeDeep(BT->rchild);
6
deep=lchilddeep>=rchilddeep?lchilddeep+1:rchilddeep+1;
7
}
8
return
deep;
9
}
二、非递归实现基本思想：
受后续遍历二叉树思想的启发，想到可以利用后续遍历的方法来求二叉树的深度，在每一次输出的地方替换成算栈S的大小，遍历结束后最大的栈S长度即是栈的深度。
算法的执行步骤如下：
（1）当树非空时，将指针p指向根节点，p为当前节点指针。
（2）将p压入栈S中，0压入栈tag中，并令p执行其左孩子。
（3）重复步骤（2），直到p为空。
（4）如果tag栈中的栈顶元素为1，跳至步骤（6）。从右子树返回
（5）如果tag栈中的栈顶元素为0，跳至步骤（7）。从左子树返回
（6）比较treedeep与栈的深度，取较大的赋给treedeep，对栈S和栈tag出栈操作，p指向NULL，并跳至步骤（8）。
（7）将p指向栈S栈顶元素的右孩子，弹出栈tag，并把1压入栈tag。（另外一种方法，直接修改栈tag栈顶的值为1也可以）
（8）循环（2）~（7），直到栈为空并且p为空
（9）返回treedeep，结束遍历
1
int
TreeDeep(BinTree
BT
){
2
int
treedeep=0;
3
stack
S;
4
stack
tag;
5
BinTree
p=BT;
6
while(p!=NULL||!isEmpty(S)){
7
while(p!=NULL){
8
push(S,p);
9
push(tag,0);
10
p=p->lchild;
11
}
12
if(Top(tag)==1){
13
deeptree=deeptree>S.length?deeptree:S.length;
14
pop(S);
15
pop(tag);
16
p=NULL;
17
}else{
18
p=Top(S);
19
p=p->rchild;
20
pop(tag);
21
push(tag,1);
22
}
23
}
24
return
deeptree;
25
}

㈣ 浜屽弶镙戠殑涓搴忋佸墠搴忋佸悗搴忕殑阃掑綊銆侀潪阃掑綊阆嶅巻绠楁硶锛屽眰娆″簭镄勯潪阃掑綊阆嶅巻绠楁硶镄勫疄鐜帮纴搴斿寘钖寤烘爲镄勫疄鐜般

浜屽弶镙戠殑阆嶅巻鏄鎸囨寜镦т竴瀹氭″簭璁块梾浜屽弶镙戜腑镄勬墍链夎妭镣癸纴涓旀疮涓鑺傜偣浠呰璁块梾涓娆＄殑杩囩▼銆傛槸链锘烘湰镄勮繍绠楋纴鏄鍏朵粬杩愮畻镄勫熀纭銆
浜屽弶镙戞湁涓ょ嶅瓨鍌ㄧ粨鏋勶细椤哄簭瀛桦偍鍜岄摼寮忓瓨鍌
椤哄簭瀛桦偍锛 锛埚瑰畬鍏ㄤ簩鍙夋爲𨱒ヨ达纴鍙浠ュ厖鍒嗗埄鐢ㄥ瓨鍌ㄧ┖闂达纴浣嗗逛簬涓鑸镄勪簩鍙夋爲锛屽彧链夊皯鏁扮殑瀛桦偍鍗曞厓琚鍒╃敤锛
[cpp] view plain
typedef struct
{
ElemType data[MaxSize];
int n;
}SqBTree;
阈惧纺瀛桦偍锛
[csharp] view plain
typedef struct node
{
ElemType data;
struct node *lchild;
struct node *rchild;
} BTNode;

浜屽弶镙戜笁绉嶉掑綊镄勯亶铡嗘柟娉曪细
鍏埚簭阆嶅巻 璁块梾镙硅妭镣光啋鍏埚簭阆嶅巻宸﹀瓙镙戋啋鍏埚簭阆嶅巻鍙冲瓙镙
涓搴忛亶铡 涓搴忛亶铡嗗乏瀛愭爲鈫掕块梾镙硅妭镣光啋涓搴忛亶铡嗗彸瀛愭爲
钖庡簭阆嶅巻 钖庡簭阆嶅巻宸﹀瓙镙戋啋钖庡簭阆嶅巻鍙冲瓙镙戋啋璁块梾镙硅妭镣
浜屽弶镙戦亶铡嗙殑阃掑綊绠楁硶锛
[cpp] view plain
void preOrder(BTNode *b) //鍏埚簭阆嶅巻阃掑綊绠楁硶
{
if (b!=NULL)
{
visit(b);
preOrder(b->lchild);
preOrder(b->rchild);
}
}
void InOrder(BTNode *b) //涓搴忛亶铡嗛掑綊绠楁硶
{
if(b!=NULL)
{
InOrder(b->lchild);
visit(b);
InOrder(b->rchild);
}
}
void PostOrder(BTNode *b) //钖庡簭阆嶅巻阃掑綊绠楁硶
{
if(b!=NULL){
PostOrder(b->lchild);
PostOrder(b->rchild);
visit(b);
}
}
浜屽弶镙戦潪阃掑綊阆嶅巻绠楁硶锛
链変袱绉嶆柟娉曪细鈶犵敤镙埚瓨鍌ㄤ俊鎭镄勬柟娉 鈶″炲姞鎸囧悜鐖惰妭镣圭殑鎸囬拡镄勬柟娉 𨱌傛椂鍙浠嬬粛涓嬫爤镄勬柟娉
鍏埚簭阆嶅巻锛
[cpp] view plain
void PreOrder(BTNode *b)
{
Stack s;
while(b!=NULL||!s.empty())
{
if(b!=NULL){
visit(b);
s.push(b);
b=b->left;
}
else{
b=s.pop();
b=b->right;
}
}
}
涓搴忛亶铡嗭细
[cpp] view plain
void InOrder(BTNode *b){
Stack s;
while(b!=NULL||!s.empty()){
if (b!=NULL)
{
s.push(b);
s=s->left
}
if(!s.empty()){
b=s.pop();
visit(b);
b=b->right;
}
}
}
钖庡簭阆嶅巻锛
[cpp] view plain
void PostOrder(BTNode *b){
Stack s;
while(b!=NULL){
s.push(b);
}
while(!s.empty()){
BTNode* node=s.pop();
if(node->bPushed){
visit(node);
}
else{
s.push(node);
if(node->right!=NULL){
node->right->bPushed=false;
s.push(node->right);
}
if(node->left!=NULL){
node->left->bpushed=false;
s.push(node->left);
}
node->bPushed=true; //濡傛灉镙囱瘑浣崭负true,鍒栾〃绀哄叆镙
}
}
}
灞傛￠亶铡嗙畻娉曪细锛堢敤阒熷垪镄勬柟娉曪级
[cpp] view plain
void levelOrder(BTNode *b){
Queue Q;
Q.push(b);
while(!Q.empty()){
node=Q.front();
visit(node);
if(NULL!=node->left){
Q.push(node->left);
}
if(NULL!=right){
Q.push(node->right);
}
}
}<span style=""></span>
宸茬煡鍏埚簭鍜屼腑搴忔眰钖庡簭镄勭畻娉曪细锛埚凡鐭ュ悗搴忓拰涓搴忔眰鍏埚簭镄勭畻娉旷被浼硷纴浣嗗凡鐭ュ厛搴忓拰钖庡簭镞犳硶姹傚嚭涓搴忥级
[cpp] view plain
int find(char c,char A[],int s,int e) /* 镓惧嚭涓搴忎腑镙圭殑浣岖疆銆 */
{
int i;
for(i=s;i<=e;i++)
if(A[i]==c) return i;
}
/* 鍏朵腑pre[]琛ㄧず鍏埚簭搴忥纴pre_s涓哄厛搴忕殑璧峰嬩綅缃锛宲re_e涓哄厛搴忕殑缁堟浣岖疆銆 */
/* 鍏朵腑in[]琛ㄧず涓搴忥纴in_s涓轰腑搴忕殑璧峰嬩綅缃锛宨n_e涓轰腑搴忕殑缁堟浣岖疆銆 */
/* pronum()姹傚嚭pre[pre_s锝瀙re_e]銆乮n[in_s锝瀒n_e]鏋勬垚镄勫悗搴忓簭鍒椼 */
void pronum(char pre[],int pre_s,int pre_e,char in[],int in_s,int in_e)
{
char c;
int k;
if(in_s>in_e) return ; /* 闱炴硶瀛愭爲锛屽畬鎴愩 */
if(in_s==in_e){printf("%c",in[in_s]); /* 瀛愭爲瀛愪粎涓轰竴涓鑺傜偣镞剁洿鎺ヨ緭鍑哄苟瀹屾垚銆 */
return ;
}
c=pre[pre_s]; /* c鍌ㄥ瓨镙硅妭镣广 */
k=find(c,in,in_s,in_e); /* 鍦ㄤ腑搴忎腑镓惧嚭镙硅妭镣圭殑浣岖疆銆 */
pronum(pre,pre_s+1,pre_s+k-in_s,in,in_s,k-1); /* 阃掑綊姹傝В鍒嗗壊镄勫乏瀛愭爲銆 */
pronum(pre,pre_s+k-in_s+1,pre_e,in,k+1,in_e); /* 阃掑綊姹傝В鍒嗗壊镄勫彸瀛愭爲銆 */
printf("%c",c); /* 镙硅妭镣硅緭鍑恒 */
}
main()
{
char pre[]="abdc";
char in[]="bdac";
printf("The result:");
pronum(pre,0,strlen(in)-1,in,0,strlen(pre)-1);
getch();
}