二叉树，递归、非递归遍历，求深度，输出叶子节点

本文主要是介绍二叉树，递归、非递归遍历，求深度，输出叶子节点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <malloc.h>
#define ElemType char//元素类型#define STACK_INIT_SIZE 100
#define _br_ printf("\n")
typedef char TElemType;/*
* \param 二叉树
* \author Silent_Amour
*/typedef struct BiTNode {ElemType data;struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;typedef struct {BiTree *base;BiTree *top;int Size;
} Stack;int initStack(Stack &S)
{S.base = (BiTree *)malloc(STACK_INIT_SIZE*sizeof(BiTree));if (!S.base)exit(-1);S.top = S.base;S.Size = STACK_INIT_SIZE;return 1;
}int StackPop(Stack &S, BiTree &e)
{if (!S.top || S.top == S.base)return -1;e = *--S.top;// printf("出栈%d，%d\n", S.top, e);return 1;
}int StackPush(Stack &S, BiTree e)
{if (S.top-S.base>= S.Size)exit(-1);*S.top++ = e;
// printf("进栈%d，地址：%d\n", S.top, e);return 1;
}int DisplayElem(TElemType e)
{printf("%c ", e);return 1;
}int creatBiTree(BiTree &T)
{char ch;ch=getchar();if (ch == '.')T = NULL;else{if (!(T = (BiTNode *)malloc(sizeof(BiTNode))))exit(-1);T->data = ch;creatBiTree(T->lchild);creatBiTree(T->rchild);}return 1;
}int PreOrderTraverse(BiTree T, int(*DisplayElem)(TElemType e))
{if (T) {if (DisplayElem(T->data))if (PreOrderTraverse(T->lchild, DisplayElem))if (PreOrderTraverse(T->rchild, DisplayElem))return 1;return -1;} elsereturn 1;}int InOrderTraverse(BiTree T, int(*DisplayElem)(TElemType e))
{if (T) {if (InOrderTraverse(T->lchild, DisplayElem))if (DisplayElem(T->data))if (InOrderTraverse(T->rchild, DisplayElem))return 1;return -1;} else return 1;
}int PostOrderTraverse(BiTree T, int(*DisplayElem)(TElemType e))
{if (T) {if (PostOrderTraverse(T->lchild, DisplayElem))if (PostOrderTraverse(T->rchild, DisplayElem))if (DisplayElem(T->data))return 1;return -1;} else return 1;
}int InOrderTraverse_Stack(BiTree T, int(*DisplayElem)(TElemType e))
{BiTree p = T;BiTree s[100];int top=-1;while (p||top!=-1) {while (p) {s[++top]=p;p = p->lchild;}if(top!=-1) {p=s[top--];if (!DisplayElem(p->data))return -1;p = p->rchild;}}return 1;
}void InOrderUnrec(BiTree t)
{Stack s;initStack(s);BiTree p=t;while (p!=NULL || s.top!=s.base) {while (p!=NULL) {StackPush(s,p);p=p->lchild;}if (s.top!=s.base) {StackPop(s,p);DisplayElem(p->data);p=p->rchild;}}
}void PreOrderUnrec(BiTree t)
{Stack s;initStack(s);BiTree p=t;while (p!=NULL || s.top!=s.base) {while (p!=NULL) {DisplayElem(p->data);StackPush(s,p);p=p->lchild;}if (s.top!=s.base) {//访问根结点StackPop(s,p);p=p->rchild;}}
}int Depth(BiTree t)
{int ld=0,rd=0;BiTree s=t;if(!t)return 0;if(t) {ld=Depth(s->lchild);rd=Depth(s->rchild);}if(ld>=rd)return ld+1;return rd+1;
}void disp_leaf(BiTree t)
{BiTNode *p=t;if(p){if(p->lchild==NULL&&p->rchild==NULL)printf("%c ",p->data);disp_leaf(p->lchild);disp_leaf(p->rchild);}
}int main()
{BiTree S;creatBiTree(S);printf("递归先序遍历：\n");PreOrderTraverse(S, DisplayElem);_br_;printf("递归中序遍历：\n");InOrderTraverse(S, DisplayElem);_br_;printf("递归后序遍历：\n");PostOrderTraverse(S, DisplayElem);_br_;printf("非递归中序遍历(小堆栈)：\n");InOrderTraverse_Stack(S, DisplayElem);_br_;printf("非递归中序遍历(标准堆栈)：\n");InOrderUnrec(S);_br_;printf("非递归先序遍历(标准堆栈)：\n");PreOrderUnrec(S);_br_;printf("深度：%d",Depth(S));_br_;printf("所有的叶子节点为：\n");disp_leaf(S);free(S);return 0;
}

这篇关于二叉树，递归、非递归遍历，求深度，输出叶子节点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---