数据结构二叉树/树一、遍历二叉树非递归算法前面给出的二叉树先序、中序和后序遍历算法都是递归算法。递归程序虽然简洁，但可读
性一般不好，执行效率也不高。因此，就存在如何把一个递归算法转化为非递归算法的问题。解决这个问题的方法可通过对三种遍历方法实质过程的
分析得到
具体做法:从根结点
开始沿左子树深入下去，当深入到最左端，无法再深入下去时，则返回，再逐一进入刚才深入时遇到结点的右子树，再进行如此深入和返回，直到最
后从根结点的右子树返回到根结点为止。先序遍历是在深入时遇到结点就访问;中序遍历是在从左子树返回时遇到结点访问;后序遍历是在从
右子树返回时遇到结点访问。StatusInorderTraverse(BiTreeT,Status(visit)(
TElemTypee)){if(T){InorderTraverse(T->lchild,visit);
visit(T->data);//访问结点InorderTraverse(T->
rchild,visit);}returnOK;}-ca+^^^^T-a+c
bdb^^d^^T以中序遍历为例编制非递归遍历算法StatusInorderTraverse(B
iTreeT,Status(visit)(TelemTypee)){
InitStack(S);p=T;while(p||！StackEmpty(S)){if
(p){Push(S,p);p=p->lchild;}else{P
op(S,p);if(!Visit(p->data))returnERROR;
p=p->rchild;}}//whilereturnOK;}//In
orderTraverse
6.4
树和森林一、树的三种存储结构1.双亲表示法:2.孩子链表表示法3.树的二叉链表(孩子-兄弟）存储表示法AB
CDEFG0A-11B02C03D0
4E25F26G5r=0n=6dataparent1
.双亲表示法:typedefstructPTNode{Elemdata;int
parent;//双亲位置域}PTNode;dataparent#defineMAX_
TREE_SIZE100结点结构:C语言的类型描述:树结构:typedefstruct{PTNode
nodes[MAX_TREE_SIZE];intr,n;//根结点的位置和结点个数}
PTree;ABCDEFG0A1B2C3D4E
5F6Gr=0n=6datafirstchild1234
562.孩子链表表示法:-1000224typedefstructCTNode{int
child;structCTNodenext;}ChildPtr;孩子结点结构:chi
ldnextC语言的类型描述:双亲结点结构:datafirstchildtypedefstruct{El
emTypedata;ChildPtrfirstchild;//孩子链的头指针
}CTBox;树结构:typedefstruct{CTBoxnodes[MAX_TREE_SIZE];
intn,r;//结点数和根结点的位置}CTree;ABCDEFGro
otABCED
FGABCED
FG3.树的二叉链表(孩子-兄弟）存储表示法（重点掌握)typedefstruc
tCSNode{ElemTypedata;structCSNodefirstchild,
nextsibling;}CSNode,CSTree;C语言的类型描述:结点结构:firstchilddat
anextsibling二、森林和二叉树的对应关系设森林F=(T1,T2,…,Tn);
T1=(root，t11,t12,…,t1m);二叉树B=(LBT,Node(root),R
BT);二叉树和树都可用二叉链表作为存储结构，则以二叉链表作为媒介可导出树与二叉树之间的一个对应关系。这种对应关系可
使森林或树与二叉树之间相互转换由森林转换成二叉树的转换规则为:若F=Φ，则B=Φ；否则，由ROOT(T1)
对应得到Node(root)；由(t11,t12,…,t1m)对应得到LBT；由(
T2,T3,…,Tn)对应得到RBT。由二叉树转换为森林的转换规则为：若B=Φ，则F=Φ；否则，由
Node(root)对应得到ROOT(T1)；由LBT对应得到(t11,t12,…，t1m)；
由RBT对应得到(T2,T3,…,Tn)。由此，树的各种操作均可对应二叉树的操作来完成。应当注意的是，和树对应的二叉树，其左、右子树的概念已改变为：左是孩子，右是兄弟。三、树和森林的遍历树的遍历可有三条搜索路径:１.先根(次序)遍历:若树不空，则先访问根结点，然后依次先根遍历各棵子树。2.后根(次序)遍历:若树不空，则先依次后根遍历各棵子树，然后访问根结点。3.按层次遍历:若树不空，则自上而下自左至右访问树中每个结点。 |
|
