【数据结构】二叉树先序遍历递归实现

wander

二叉树的先序遍历采用的是递归的思想，因此图1所示的二叉树可以递归实现，其 C 语言实现代码为：

                图 1 二叉树

• #include <stdio.h>
• #include <string.h>
• #define TElemType int
• //构造结点的结构体
• typedef struct BiTNode{
•     TElemType data;//数据域
•     struct BiTNode *lchild,*rchild;//左右孩子指针
• }BiTNode,*BiTree;
• //初始化树的函数
• void CreateBiTree(BiTree *T){
•     *T=(BiTNode*)malloc(sizeof(BiTNode));
•     (*T)->data=1;
•     (*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode));
•     (*T)->rchild=(BiTNode*)malloc(sizeof(BiTNode));
•     (*T)->lchild->data=2;
•     (*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
•     (*T)->lchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));
•     (*T)->lchild->rchild->data=5;
•     (*T)->lchild->rchild->lchild=NULL;
•     (*T)->lchild->rchild->rchild=NULL;
•     (*T)->rchild->data=3;
•     (*T)->rchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
•     (*T)->rchild->lchild->data=6;
•     (*T)->rchild->lchild->lchild=NULL;
•     (*T)->rchild->lchild->rchild=NULL;
•     (*T)->rchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));
•     (*T)->rchild->rchild->data=7;
•     (*T)->rchild->rchild->lchild=NULL;
•     (*T)->rchild->rchild->rchild=NULL;
•     (*T)->lchild->lchild->data=4;
•     (*T)->lchild->lchild->lchild=NULL;
•     (*T)->lchild->lchild->rchild=NULL;
• }
• //模拟操作结点元素的函数，输出结点本身的数值
• void displayElem(BiTNode* elem){
•     printf("%d ",elem->data);
• }
• //先序遍历
• void PreOrderTraverse(BiTree T){
•     if (T) {
•         displayElem(T);//调用操作结点数据的函数方法
•         PreOrderTraverse(T->lchild);//访问该结点的左孩子
•         PreOrderTraverse(T->rchild);//访问该结点的右孩子
•     }
•     //如果结点为空，返回上一层
•     return;
• }
• int main() {
•     BiTree Tree;
•     CreateBiTree(&Tree);
•     printf("先序遍历: \n");
•     PreOrderTraverse(Tree);
• }
  

运行结果：先序遍历:
1 2 4 5 3 6 7