#include#include typedef struct Node { DataType data; struct Node *LChild; struct Node *RChild; }BiTNode, *BiTree; //若一个二叉树有n个结点，则它的二叉链表中必含有2n个指针域，其中必有n+1个空的链域 //二叉树的遍历（默认先左后右） //先序遍历DLR；中序遍历LDR；后序遍历LRD //遍历问题的提出：计算机中的表达式求值-后缀表达式即为逆波兰表达式 //先序遍历二叉树 void PreOrder(BiTree root) { if(root!=NULL) { Visit(root->data); PreOrder(root->LChild); PreOrder(root->RChild);s } } //中序遍历 void InOrder(BiTree root) { if(root!=NULL) { InOrder(root->LChild); Visit(root->data); InOrder(root->RChild); } } //后序遍历二叉树 void PostOrder(BiTree root){ if(root!=NULL) { PostOrder(root->LChild); PostOrder(root->RChild); Visit(root->data); } } //遍历算法应用 //分治算法统计叶子结点的数目 int leaf(BiTree root) { int LeafCount; if(root==NULL) LeafCount=0; else if((root->LChild==NULL)&&(root->RChild==NULL)) LeafCount=1; else//叶子数为左右子数的叶子数目之和 LeafCount=leaf(root->LChild)+leaf(root->RChild); return LeafCount; } //继续遍历算法的应用 //比如说先序序列AB.DF..G..C.E.H..;其中用小圆点表示空子树 void CreateBiTree(BiTree *bt) { char ch; ch=getchar(); if(ch=='.') *bt=NULL; else { *bt=(BiTree)malloc(sizeof(BiTNode)); (*bt)->data=ch; CreateBiTree(&((*bt)->LChild)); CreateBiTree(&((*bt)->RChild)); } } //5-求二叉树的高度（若bt为空，则高度为0；若bt非空，其高度应为其左右子树高度的最大值加1） //后续遍历求高度 int PostTreeDepth(BiTree bt) { int hl, hr, max; if(bt!=NULL){ hl=PostTreeDepth(bt->LChild); //求左子树的深度 hr=PostTreeDepth(bt->RChild);//求右子树深度 max=hl>hr?hl:hr;s return (max+1); } else return 0;//代表是空树 } //先序遍历求二叉树高度 void PreTreeDepth(BiTree bt, int h) { //h为bt指向结点所在层次，初值为1 if(bt!=NULL) { if(h>depth) depth=h;//时刻更新depth为最大 PreTreeDepth(bt->LChild, h+1); PreTreeDepth(bt->RChild, h+1); } } //应用6-按树状打印二叉树（书P181) //基于栈的递归消除：这里还不太懂，需要进一步看书 //线索二叉树 //二叉树的线索化实质是将二叉链表的空指针域填上相应结点的遍历前去或后继结点的地址； //线索化的过程即为在遍历过程中修改空指针域的过程 //建立中序线索树（不同的遍历方法得到不同的线索二叉树） BiTNode* pre=NULL; void Inthread(BiTree root) //pre始终指向刚访问过的结点，初值为NULL { if(root!=NULL) { Inthread(root->LChild);//线索化左子树 //root和pre互相置 if(root->LChild==NULL) { root->Ltag=1; root->LChild=pre; //置前驱线索 } if(pre!=NULL && pre->RChild=NULL)//置后继线索 { pre->RChild=root; pre->Rtag=1; } pre=root; Inthread(root->RChild);//线索化右子树 } } //在中序线索中找结点前驱 BiTNode* InPre(BiTNode *p) { if(p->Ltag==1) pre=p->LChild; //直接利用线索 else{ //在p的左子树中找最右下端结点 for(q=p->LChild; q->Rtag==0;q=q->RChild); pre=q; } return pre; } //在中序线索树中找结点后继 BiTNode* InNext(BiTNode *p) { if(p->Rtag==1) Next=p->RChild; else{ //p的右子树中最左下端 for(q=p->RChild; q->Ltag==0; q=q->LChild); Next=q; } return (NEXT); } //在先序中查找结点的后继比较容易，在后续中查找结点的前驱比较容易 //具体方法：求出中序线索树上中序遍历的第一个结点；连续求出刚访问结点的后继结点来遍历中序二叉线索树 //找中序遍历的第一个结点 BiTNode *InFirst(BiTree Bt) { BiTNode *p=Bt; if(!p) return NULL; //找到左子树的最左结点 while(p->LTag==0) p=p->LChild; return p; } void TInOrder(BiTree Bt) { BiTNode *p; p=InFirst(BiTree Bt); while(p) { visit(p); p=InNext(p); } } //由给定的序列确定二叉树：先序或后序+中序可以唯一的确定二叉树 int main() { return 0; }
#include//树的遍历：先根遍历（ 转换后的前序遍历）；后根遍历（转换后的中序遍历） int main() { return 0; }
终于来到了非线性数据结构的领域，知识点都在以上代码段中用注释的形式给出了。有的具体内容没有写完整，详细参考耿国华老师和严蔚敏老师分别写的《数据结构》。
总结一下：了解数据结构树家族，首先要了解一些有关树的基本概念，一些名词概念和性质，了解树的ADT是什么样子的。然后了解二叉树的代码实现，重点关注其遍历方式（前序、中序、后序），知道什么。之后，由二叉树，推广了解一般的树，对应的代码实现。由一般的树，进一步了解森林，学习树、森林、二叉树之间的关系和转换。霍夫曼树的代码我还没写，到时候写完了粘上来。
其他想到了再补充。最近在学写CPU，想看的可以留言我有时间出个帖子。看关注我的好多都是因为JAVA那篇关注我的，下一篇文章预计写一下JAVA有关知识，把UML图一起梳理了。先立个flag有时间回来填坑。
