数据结构树2 [复制链接]

这篇推送将讲解，二叉树的存储结构以及二叉树基本操作：三种顺序遍历的实现。

二叉树的两种存储结构：

（1）顺序存储

//-------二叉树的顺序表示-----#defineMAX_TREE_SIZEtypedefTElemTypeSqBiTree[MAX_TREE_SIZE];SqBiTreebt;

（2）链式存储

//-------二叉树的链式存储表示---typedefstructBiTNode{TElemTypedata;BiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTNode;

基本操作思想与实现

操作：CreateBiTree(BiTreeT)

描述：按先序次序输入二叉树中结点的值（一个字符），空格表示空树

功能：构造二叉链表表示的二叉树

思想：函数的自身递归调用

BiTNode*CreateBiTree(){//此处情景：假设输入为单字符，遇到空格表示空树chartem;BiTNode*T;tem=getchar();if(tem==")T=NULL;else{T=(BiTNode*)malloc(sizeof(BiTNode));if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))returnNULL;T-data=tem;//生成根结点；T-lchild=CreateBiTree();T-rchild=CreateBiTree();}returnT;}

三种顺序遍历二叉树

先序遍历二叉树

如图所示，无论按照哪一种顺序进行遍历，主要核心思想都是：按照被?指中?→的顺序输出，先被指中的先输出，而指的顺序就如上图，上图应该输出-*abc

算法思想：函数递归调用，每一个结点都可以视作后面树的root

intPreOrderTraverse(BiTNode*T,int(*print)(TElemTypee)){//此处在定义时，用到了函数的指针传递//在函数中传递了函数的指针//print函数用于输出单个结点，具体问题应该具体编写以达到符合要求的输出if(T){if(print(T-data))if(PreOrderTraverse(T-lchild,print))if(PreOrderTraverse(T-rchild,print))return1;//成功遍历该结点以下树返回1return0;//失败返回0；}return1;//如果是NULL，返回1，回退}

中序遍历二叉树

按照中序，应该输出a*b-c

算法思想一：采用栈当不再有左孩子时弹出，其余时候压入，弹出后压入右孩子（如果有），压入后进入下一重循环，获得栈顶元素，继续判断。

算法思想二：继续采用递归算法，把每个结点视作后续结点的root，均遵循先左后右访问，在左右中间设置print操作输出/访问结点。

算法思想一：栈的代码实现

//实现1intInOrderTraverse(BiTNode*T,int(*print)(TElemTypee)){//stack实现initstack(S);push(*S,T);//栈的操作运用时应该重新调整BiTNode*p=T;//p指向当前结点while(!Stackempty(S)){while(gettop(S,p)p)push(S,p-lchild);//未满足输出条件，左孩子进栈pop(S,p);//走到尽头是循环出口，此处弹出的是最后压入的空指针if(!Stackempty(S)){pop(S,p);if(!print(p-data))return0;push(S,p-rchild);//右孩子即使是空指针也没关系，循环开始时会进行判断}}return1;//正常退出}//实现2intInOrderTraverse(BiTNode*T,int(*print)(TElemTypee)){initstack(S);BiTNode*p=T;while(p

!Stackempty(S))//p不为空或者栈不为空进入循环{//遍历左子树if(p){push(S,p);p=p-lchild;}//如果p不为空，压入栈else{//左子树遍历到终点，开始遍历右子树pop(S,p);//弹出空指针if(!print(p-data))return0;//纯粹鲁棒性考量p=p-rchild;//开始遍历右子树}}return1;//正常退出}

算法二：递归实现

intInOrderTraverse(BiTNode*T,int(*print)(TElemTypee)){//递归实现BiTNode*p=T;if(p){InOrderTraverse(p-lchild,print);//遍历左子树print(p-data);//左子树返回，访问dataInOrderTraverse(p-rchild,print);//遍历右子树}}

后序遍历二叉树

后序遍历二叉树中需要注意的点是：在单个结点内部的被指向是不能算作被指向的，只有访问下一个结点后再被“弹回”，或者说，被下一个结点指向时才能进行访问。

算法思想：也是递归思想，当访问完右孩子return后再访问数据。

intPostOrderTraverse(BiTNode*T,int(*print)(TElemTypee)){//递归实现if(T){InOrderTraverse(p-lchild,print);//遍历左子树InOrderTraverse(p-rchild,print);//遍历右子树print(p-data);//右子树返回后再进行数据输出}}

综上，其实对于三种顺序遍历二叉树的递归算法，语句其实完全相同，仅仅是Visit函数的位置发生改变，先序先Visit再左右，中序先左再Visit再右，后序先左右再Visit，代码是十分简单易懂的。