二叉链表(C语言实现)——递归和非递归遍历_Mr
- #include<stdio.h>
- #include<stdlib.h>
- #include<stdbool.h>
- #define QueueSize 100 // 借助队列实现层序遍历
- #define StackSize 100 // 借助栈实现非递归遍历
- typedef char DataType;
- typedef struct BiTNode
- {
- DataType data;
- struct BiTNode * lchild;
- struct BiTNode * rchild;
-
- }BiTNode,*BiTree;
-
- // 栈元素类型
- typedef struct SNode
- {
- BiTNode * bt; // 结点域
- int flag; // 标志域
-
- }ElemType;
-
- void Creat_BiTree(BiTree* T); // 建立树
- int Depth_BiTree(BiTree T); // 树深度
- int Count_BiTree(BiTree T); // 树结点个数
- int LeafCount_BiTree(BiTree T); // 树叶子结点个数
- bool Destroy_BiTree(BiTree T); // 销毁树
- void PreOrder_Traverse(BiTree T); // 前序遍历递归算法
- void InOrder_Traverse(BiTree T); // 中序遍历递归算法
- void PostOrder_Traverse(BiTree T); // 后序遍历递归算法
- void Level_Traverse(BiTree T); // 层序遍历
- void Pre_Traverse(BiTree T); // 前序遍历非递归算法
- void In_Traverse(BiTree T); // 中序遍历非递归算法
- void Post_Traverse(BiTree T); // 后序遍历非递归算法
-
- int main()
- {
- BiTree T;
- printf("请输入根结点:");
- Creat_BiTree(&T);
-
- printf("
");
- printf("树深度:%%d
",Depth_BiTree(T)) ;
- printf("树结点个数:%%d
",Count_BiTree(T));
- printf("树叶子结点个数:%%d
",LeafCount_BiTree(T));
-
- printf("
————————层序遍历算法————————
");
- printf("层序遍历:");
- Level_Traverse(T);
- printf("
");
-
- printf("
————————递归遍历算法————————
");
- printf("递归前序遍历:");
- PreOrder_Traverse(T);
- printf("
");
-
- printf("递归中序遍历:");
- InOrder_Traverse(T);
- printf("
");
-
- printf("递归后序遍历:");
- PostOrder_Traverse(T);
- printf("
");
-
- printf("
————————非递归遍历算法————————
");
- printf("非递归前序遍历:");
- Pre_Traverse(T);
- printf("
");
-
- printf("非递归中序遍历:");
- In_Traverse(T);
- printf("
");
-
- printf("非递归后序遍历:");
- Post_Traverse(T);
- printf("
");
-
- return 0;
-
- }
-
- // 注意产生空指针
- void Creat_BiTree(BiTree* T)
- {
- char ch;
- fflush(stdin);
- scanf("%%c",&ch);
- if(ch == '#')
- {
- *T = NULL;
- return;
- }
- else
- {
- *T = (BiTree)malloc(sizeof(BiTNode));
- (*T)->data = ch;
- printf("请输入%%c的左子树结点:", ch);
- Creat_BiTree(&(*T)->lchild);
- printf("请输入%%c的右子树结点:", ch);
- Creat_BiTree(&(*T)->rchild);
- }
- }
-
- int Depth_BiTree(BiTree T)
- {
- if(!T)
- return;
- // 递归求树深度
- return Depth_BiTree(T->lchild) > Depth_BiTree(T->rchild) ? Depth_BiTree(T->lchild)+1 : Depth_BiTree(T->rchild)+1;// 深度=最大层数+1
- }
-
- int Count_BiTree(BiTree T)
- {
- if(!T)
- return;
- // 递归求树结点数
- return Count_BiTree(T->lchild) + Count_BiTree(T->rchild) + 1; // 树结点:左子树结点+右子树结点+根结点
-
- }
-
- int LeafCount_BiTree(BiTree T)
- {
- if(!T)
- return;
-
- if(T->lchild==NULL && T->rchild==NULL) // 左、右孩子指针域均为空时为叶子结点
- return 1;
- else
- return LeafCount_BiTree(T->lchild) + LeafCount_BiTree(T->rchild);
- }
-
- bool Destroy_BiTree(BiTree T)
- {
- if(!T)
- return false;
-
- Destroy_BiTree(T->lchild);
- Destroy_BiTree(T->rchild);
- free(T);
- T = NULL; // 防止产生野指针
- return true;
- }
-
- void PreOrder_Traverse(BiTree T)
- {
- if(!T)
- return;
-
- printf("%%3c",T->data);
- PreOrder_Traverse(T->lchild);
- PreOrder_Traverse(T->rchild);
- }
-
- void InOrder_Traverse(BiTree T)
- {
- if(!T)
- return;
-
- InOrder_Traverse(T->lchild);
- printf("%%3c",T->data);
- InOrder_Traverse(T->rchild);
- }
-
- void PostOrder_Traverse(BiTree T)
- {
- if(!T)
- return;
-
- PostOrder_Traverse(T->lchild);
- PostOrder_Traverse(T->rchild);
- printf("%%3c",T->data);
- }
-
- void Level_Traverse(BiTree T)
- {
- // 初始化队列
- BiTree Q[QueueSize];
- int front = 0;
- int rear = 0;
-
- if(!T)
- return;
- Q[rear++] = T;
- while(front != rear)
- {
- BiTree p = Q[front++];
- printf("%%3c",p->data);
-
- if(p->lchild!=NULL)
- Q[rear++] = p->lchild;
- if(p->rchild!=NULL)
- Q[rear++] = p->rchild;
- }
- return;
- }
-
- void Pre_Traverse(BiTree T)
- {
- BiTree p = T; // 初始化工作指针
-
- // 将栈初始化
- BiTree Stack[StackSize];
- int top = -1;
-
- while(p!=NULL || top!=-1) // 两个条件都不成立时,才能退出循环
- {
- if(p!=NULL)
- {
- printf("%%3c",p->data); // 访问输出结点后,将其入栈
- Stack[++top] = p;
- p = p->lchild;
- }
- else
- {
- p = Stack[top--];
- p = p->rchild;
- }
- }
-
- }
-
- void In_Traverse(BiTree T)
- {
- BiTree p = T; // 初始化工作指针
-
- // 栈初始化
- BiTree Stack[StackSize];
- int top = -1;
-
- while(p!=NULL || top!=-1)
- {
- if(p!=NULL)
- {
- Stack[++top] = p;
- p = p->lchild;
- }
- else
- {
- p = Stack[top--];
- printf("%%3c",p->data); // 出栈后,访问输出结点
- p = p->rchild;
- }
- }
- }
-
- void Post_Traverse(BiTree T)
- {
- BiTree p = T;
- ElemType Stack[StackSize];
- int top = -1;
-
- while(p!=NULL || top!=-1 )
- {
- if(p!=NULL)
- {
- ++top;
- Stack[top].bt = p;
- Stack[top].flag = 1;
- p = p->lchild;
- }
- else
- {
- if(Stack[top].flag==1)// 左子树遍历完,访问栈顶元素但不出栈,随后将标志域设为2,并遍历右子树
- {
- p = Stack[top].bt;
- Stack[top].flag = 2;
- p = p->rchild;
- }
- else
- {
- p = Stack[top--].bt;
- printf("%%3c",p->data);
- p = NULL; // p置空,以便继续退栈
- }
- }
- }
- }
①前序遍历
②中序遍历
③后序遍历
④层序遍历
推荐阅读