树是n (n≥0)个节点的有限集。当n=0时，称为空树。在任意一棵非空树中应满足:
1）有且仅有一个特定的称为根的结点。
2)当n>1时，其余节点可分为m (m>0)个互不相交的有限集T,T2…,Tm，其中每个集合本身又是一棵树，并且称为根的子树。
显然，树的定义是递归的，即在树的定义中又用到了其自身，树是一种递归的数据结构。树作为一种逻辑结构，同时也是一种分层结构，具有以下两个特点:
1）树的根结点没有前驱，除根结点外的所有结点有且只有一个前驱。
2）树中所有结点可以有零个或多个后继。
树适合于表示具有层次结构的数据。树中的某个结点（除根结点外）最多只和上一层的一个结点(即其父结点)有直接关系，根结点没有直接上层结点，因此在n个结点的树中有n-1条边。而树中每个结点与其下一层的零个或多个结点（即其子女结点）有直接关系。
1）考虑结点K。根A到结点K的唯一路径上的任意结点，称为结点K的祖先。如结点B是结点K的祖先，而结点K是结点B的子孙。路径上最接近结点K的结点E称为K的双亲，而K为结点E的孩子。根A是树中唯一没有双亲的结点。有相同双亲的结点称为兄弟，如结点K和结点L有相同的双亲E,即K和L为兄弟。
2）树中一个结点的孩子个数称为该结点的度，树中结点的最大度数称为树的度。如结点B的度为2，结点D的度为3，树的度为3。
3）度大于0的结点称为分支结点(又称非终端结点);度为0(没有子女结点）的结点称为叶子结点(又称终端结点)。在分支结点中，每个结点的分支数就是该结点的度。
4)结点的深度、高度和层次。结点的层次从树根开始定义，根结点为第1层，它的子结点为第2层，以此类推。双亲在同一层的结点互为堂兄弟，图5.1中结点G与E,F,H,I,J互为堂兄弟。
结点的深度是从根结点开始自顶向下逐层累加的。
结点的高度是从叶结点开始自底向上逐层累加的。
树的高度或深度）是树中结点的最大层数。图5.1中树的高度为4。
5）有序树和无序树。树中结点的各子树从左到右是有次序的，不能互换，称该树为有序树，否则称为无序树。假设图5.1为有序树，若将子结点位置互换，则变成一棵不同的树。
6）路径和路径长度。树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的，而路径长度是路径上所经过的边的个数。
注意:由于树中的分支是有向的，即从双亲指向孩子，所以树中的路径是从上向下的，同一双亲的两个孩子之间不存在路径。
7）森林。森林是m(m≥0）棵互不相交的树的集合。森林的概念与树的概念十分相近因为只要把树的根结点删去就成了森林。反之，只要给m棵独立的树加上一个结点，并把这m棵树作为该结点的子树，则森林就变成了树。
二叉树与度为2的有序树的区别：
①度为2的树至少有3个结点，而二叉树可以为空。
②度为2的有序树的孩子的左右次序是相对于另一孩子而言的，若某个结点只有一个孩子，则这个孩子就无须区分其左右次序，而二叉树无论其孩子数是否为2.均需确定其左右次序，即二叉树的结点次序不是相对于另一结点而言，而是确定的。)
特殊的二叉树
//二叉树--顺序存储--适合完全二叉树 #include链式存储#define MAXSIZE 100 struct TreeNode{ //结点中的数据元素 int value; //判断结点是否为空 0为空 1不为空 int isEmpty; }; typedef struct TreeNode TreeNode; void initTree(TreeNode *tree){ int i=1; for(;i<=MAXSIZE-1;i++){ tree[i].isEmpty=0; } } void printfInitTree(TreeNode tree[]){ int i=1; for(;i<=MAXSIZE-1;i++){ printf("%d,",tree[i].isEmpty); } } int main(){ TreeNode tree[MAXSIZE]; initTree(tree); printfInitTree(tree); tree[1].value=1; tree[1].isEmpty=1; tree[2].value=2; tree[2].isEmpty=1; tree[3].value=3; tree[3].isEmpty=1; tree[4].value=4; tree[4].isEmpty=1; tree[5].value=5; tree[5].isEmpty=1; tree[6].value=6; tree[6].isEmpty=1; tree[7].value=7; tree[7].isEmpty=1; tree[8].value=8; tree[8].isEmpty=1; tree[9].value=9; tree[9].isEmpty=1; tree[10].value=10; tree[10].isEmpty=1; tree[11].value=11; tree[11].isEmpty=1; tree[12].value=12; tree[12].isEmpty=1; return 0; }
以下代码所用的二叉树如下图
//二叉树--链式存储 #include线索二叉树 线索二叉树的概念#include #define MAXSIZE 100 struct BiTNode{ //数据域 int value; //左孩子 struct BiTNode *lChild; //右孩子 struct BiTNode *rChild; }; typedef struct BiTNode BiTNode; typedef struct BiTNode* BiTree; struct linkNode{ BiTNode* data; struct linkNode *next; }; typedef struct linkNode linkNode; struct linkQueue{ linkNode *front; linkNode *rear; }; typedef struct linkQueue linkQueue; BiTNode* initTree(BiTree root){ root=NULL; return root; } BiTNode* constructTree(BiTree root){ BiTNode *p11=(BiTNode *)malloc(sizeof(BiTNode)); (*p11).value=11; (*p11).lChild=NULL; (*p11).rChild=NULL; BiTNode *p12=(BiTNode *)malloc(sizeof(BiTNode)); (*p12).value=12; (*p12).lChild=NULL; (*p12).rChild=NULL; BiTNode *p5=(BiTNode *)malloc(sizeof(BiTNode)); (*p5).value=5; (*p5).lChild=NULL; (*p5).rChild=p11; BiTNode *p6=(BiTNode *)malloc(sizeof(BiTNode)); (*p6).value=6; (*p6).lChild=p12; (*p6).rChild=NULL; BiTNode *p7=(BiTNode *)malloc(sizeof(BiTNode)); (*p7).value=7; (*p7).lChild=NULL; (*p7).rChild=NULL; BiTNode *p2=(BiTNode *)malloc(sizeof(BiTNode)); (*p2).value=2; (*p2).lChild=NULL; (*p2).rChild=p5; BiTNode *p3=(BiTNode *)malloc(sizeof(BiTNode)); (*p3).value=3; (*p3).lChild=p6; (*p3).rChild=p7; BiTNode *p1=(BiTNode *)malloc(sizeof(BiTNode)); (*p1).value=1; (*p1).lChild=p2; (*p1).rChild=p3; root=p1; return root; } void preOrder(BiTree biTree){ if(biTree!=NULL){ printf("%d ",(*biTree).value); preOrder((*biTree).lChild); preOrder((*biTree).rChild); } } void inOrder(BiTree biTree){ if(biTree!=NULL){ inOrder((*biTree).lChild); printf("%d ",(*biTree).value); inOrder((*biTree).rChild); } } void postOrder(BiTree biTree){ if(biTree!=NULL){ postOrder((*biTree).lChild); postOrder((*biTree).rChild); printf("%d ",(*biTree).value); } } int treeDepth(BiTree root){ if(root==NULL){ return 0; }else{ int l=treeDepth((*root).lChild); int r=treeDepth((*root).rChild); return l>r?l+1:r+1; } } int initQueue(linkQueue *queue){ linkNode *newNode=(linkNode *)malloc(sizeof(linkNode)); if(newNode==NULL){ return 0; } (*newNode).next=NULL; (*queue).front=newNode; (*queue).rear=newNode; } int enQueue(linkQueue *queue,BiTNode* data){ linkNode *newNode=(linkNode *)malloc(sizeof(linkNode)); if(newNode==NULL){ return 0; } (*newNode).data=data; (*newNode).next=NULL; (*queue).rear->next=newNode; (*queue).rear=newNode; return 1; } BiTNode* deQueue(linkQueue *queue){ linkNode *front=(*queue).front; linkNode *rear=(*queue).rear; //被出队的结点--头结点的下一个结点 linkNode *tmpNode=(*front).next; BiTNode* result=(*tmpNode).data; (*front).next=(*tmpNode).next; if((*tmpNode).next==NULL){ (*queue).rear=front; } free(tmpNode); return result; } int queueEmpty(linkQueue queue){ if(queue.front==queue.rear){ return 1; }else{ return 0; } } void levelOrder(BiTree root){ if(root==NULL){ return ; } linkQueue linkQueue; initQueue(&linkQueue); enQueue(&linkQueue,root); BiTNode* p; while(queueEmpty(linkQueue)==0){ p=deQueue(&linkQueue); printf("%d ",(*p).value); if((*p).lChild!=NULL){ enQueue(&linkQueue,(*p).lChild); } if((*p).rChild!=NULL){ enQueue(&linkQueue,(*p).rChild); } } } BiTNode *tmpResult=NULL; void preOrderTwo(BiTree biTree){ if(biTree!=NULL){ if((*biTree).value==5){ tmpResult=biTree; } preOrderTwo((*biTree).lChild); preOrderTwo((*biTree).rChild); } } void inPreBiTNode(BiTree biTree,BiTNode *q,BiTNode *target){ BiTNode *pre=NULL; if(biTree!=NULL){ inPreBiTNode((*biTree).lChild,q,target); pre=q; q=biTree; if(q==target){ tmpResult=pre; } inPreBiTNode((*biTree).rChild,q,target); } } void inNextBiTNode(BiTree biTree,BiTNode *q,BiTNode *target){ BiTNode *pre=NULL; if(biTree!=NULL){ inNextBiTNode((*biTree).lChild,q,target); pre=q; q=biTree; if(pre==target){ tmpResult=q; } inNextBiTNode((*biTree).rChild,q,target); } } void prePreBiTNode(BiTree biTree,BiTNode *q,BiTNode *target){ BiTNode *pre=NULL; if(biTree!=NULL){ pre=q; q=biTree; if(q==target){ tmpResult=pre; } prePreBiTNode((*biTree).lChild,q,target); prePreBiTNode((*biTree).rChild,q,target); } } void preNextBiTNode(BiTree biTree,BiTNode *q,BiTNode *target){ BiTNode *pre=NULL; if(biTree!=NULL){ pre=q; q=biTree; if(pre==target){ tmpResult=q; } preNextBiTNode((*biTree).lChild,q,target); preNextBiTNode((*biTree).rChild,q,target); } } void postPreBiTNode(BiTree biTree,BiTNode *q,BiTNode *target){ BiTNode *pre=NULL; if(biTree!=NULL){ postPreBiTNode((*biTree).lChild,q,target); postPreBiTNode((*biTree).rChild,q,target); pre=q; q=biTree; if(q==target){ tmpResult=pre; } } } void postNextBiTNode(BiTree biTree,BiTNode *q,BiTNode *target){ BiTNode *pre=NULL; if(biTree!=NULL){ postNextBiTNode((*biTree).lChild,q,target); postNextBiTNode((*biTree).rChild,q,target); pre=q; q=biTree; if(pre==target){ tmpResult=q; } } } int main(){ BiTNode *q=NULL; BiTree root; root=initTree(root); root=constructTree(root); preOrder(root); printf("n"); inOrder(root); printf("n"); postOrder(root); printf("n"); printf("%d",treeDepth(root)); printf("n"); levelOrder(root); printf("n"); preOrderTwo(root); printf("n"); inPreBiTNode(root,q,tmpResult); printf("结点5的中序前驱是：%d",(*tmpResult).value); printf("n"); preOrderTwo(root); printf("n"); inNextBiTNode(root,q,tmpResult); printf("结点5的中序后继是：%d",(*tmpResult).value); printf("n"); return 0; }
右指针存放的是后继，后继的确定是上一个结点pre确定，上一个结点早就遍历完了，所以不会出现循环现象
左指针存放的是前驱，先序的左是第二个遍历，如果左指针存放了根，接下来遍历左子树，就会造成循环；而中序和后序是先遍历左，所以不会造成循环
找前驱/后继
//二叉树--链式存储 #include先序线索二叉树#include #define MAXSIZE 100 struct ThreadNode{ //数据域 int value; //左孩子 struct ThreadNode *lChild; //右孩子 struct ThreadNode *rChild; //1--前驱结点 0--左孩子 int ltag; //1--后继结点 0--右孩子 int rtag; }; typedef struct ThreadNode ThreadNode; typedef struct ThreadNode* ThreadTree; ThreadTree* initTree(ThreadTree root){ root=NULL; return root; } ThreadTree* constructTree(ThreadTree root){ ThreadNode *p11=(ThreadNode *)malloc(sizeof(ThreadNode)); (*p11).ltag=0; (*p11).rtag=0; (*p11).value=11; (*p11).lChild=NULL; (*p11).rChild=NULL; ThreadNode *p12=(ThreadNode *)malloc(sizeof(ThreadNode)); (*p12).ltag=0; (*p12).rtag=0; (*p12).value=12; (*p12).lChild=NULL; (*p12).rChild=NULL; ThreadNode *p5=(ThreadNode *)malloc(sizeof(ThreadNode)); (*p5).ltag=0; (*p5).rtag=0; (*p5).value=5; (*p5).lChild=NULL; (*p5).rChild=p11; ThreadNode *p6=(ThreadNode *)malloc(sizeof(ThreadNode)); (*p6).ltag=0; (*p6).rtag=0; (*p6).value=6; (*p6).lChild=p12; (*p6).rChild=NULL; ThreadNode *p7=(ThreadNode *)malloc(sizeof(ThreadNode)); (*p7).ltag=0; (*p7).rtag=0; (*p7).value=7; (*p7).lChild=NULL; (*p7).rChild=NULL; ThreadNode *p2=(ThreadNode *)malloc(sizeof(ThreadNode)); (*p2).ltag=0; (*p2).rtag=0; (*p2).value=2; (*p2).lChild=NULL; (*p2).rChild=p5; ThreadNode *p3=(ThreadNode *)malloc(sizeof(ThreadNode)); (*p3).ltag=0; (*p3).rtag=0; (*p3).value=3; (*p3).lChild=p6; (*p3).rChild=p7; ThreadNode *p1=(ThreadNode *)malloc(sizeof(ThreadNode)); (*p1).ltag=0; (*p1).rtag=0; (*p1).value=1; (*p1).lChild=p2; (*p1).rChild=p3; root=p1; return root; } //指向当前被访问的结点 ThreadNode *q=NULL; void createInThread(ThreadTree root){ if(root!=NULL){ inThread(root); if((*q).rChild==NULL){ (*q).rtag=1; } } } void inThread(ThreadTree root){ ThreadNode *pre=NULL; if(root!=NULL){ inThread((*root).lChild); pre=q; q=root; if((*q).lChild==NULL){ (*q).lChild=pre; (*q).ltag=1; } if(pre!=NULL&&(*pre).rChild==NULL){ (*pre).rChild=q; (*pre).rtag=1; } inThread((*root).rChild); } } ThreadNode* inFirstNode(ThreadNode *p){ //循环找到最左下结点（不一定是叶子结点） while((*p).ltag==0){ p=(*p).lChild; } return p; } ThreadNode* inNextNode(ThreadNode *p){ //右子树中最左下结点 if((*p).rtag==0){ return inFirstNode((*p).rChild); }else{ return (*p).rChild; } } void inOrder(ThreadTree root){ ThreadNode *p=inFirstNode(root); for(;p!=NULL;p=inNextNode(p)){ printf("%d ",(*p).value); } } ThreadNode* inLastNode(ThreadNode *p){ //循环找到最右下结点（不一定是叶子结点） while((*p).rtag==0){ p=(*p).rChild; } return p; } ThreadNode* inPreNode(ThreadNode *p){ //左子树中最右下结点 if((*p).ltag==0){ return inLastNode((*p).lChild); }else{ return (*p).lChild; } } void revInOrder(ThreadTree root){ ThreadNode *p=inLastNode(root); for(;p!=NULL;p=inPreNode(p)){ printf("%d ",(*p).value); } } int main(){ ThreadTree root; root=initTree(root); root=constructTree(root); createInThread(root); inOrder(root); printf("n"); revInOrder(root); return 0; }
//二叉树--链式存储 #include后序线索二叉树#include #define MAXSIZE 100 struct ThreadNode{ //数据域 int value; //左孩子 struct ThreadNode *lChild; //右孩子 struct ThreadNode *rChild; //1--前驱结点 0--左孩子 int ltag; //1--后继结点 0--右孩子 int rtag; }; typedef struct ThreadNode ThreadNode; typedef struct ThreadNode* ThreadTree; ThreadTree* initTree(ThreadTree root){ root=NULL; return root; } ThreadTree* constructTree(ThreadTree root){ ThreadNode *p11=(ThreadNode *)malloc(sizeof(ThreadNode)); (*p11).ltag=0; (*p11).rtag=0; (*p11).value=11; (*p11).lChild=NULL; (*p11).rChild=NULL; ThreadNode *p12=(ThreadNode *)malloc(sizeof(ThreadNode)); (*p12).ltag=0; (*p12).rtag=0; (*p12).value=12; (*p12).lChild=NULL; (*p12).rChild=NULL; ThreadNode *p5=(ThreadNode *)malloc(sizeof(ThreadNode)); (*p5).ltag=0; (*p5).rtag=0; (*p5).value=5; (*p5).lChild=NULL; (*p5).rChild=p11; ThreadNode *p6=(ThreadNode *)malloc(sizeof(ThreadNode)); (*p6).ltag=0; (*p6).rtag=0; (*p6).value=6; (*p6).lChild=p12; (*p6).rChild=NULL; ThreadNode *p7=(ThreadNode *)malloc(sizeof(ThreadNode)); (*p7).ltag=0; (*p7).rtag=0; (*p7).value=7; (*p7).lChild=NULL; (*p7).rChild=NULL; ThreadNode *p2=(ThreadNode *)malloc(sizeof(ThreadNode)); (*p2).ltag=0; (*p2).rtag=0; (*p2).value=2; (*p2).lChild=NULL; (*p2).rChild=p5; ThreadNode *p3=(ThreadNode *)malloc(sizeof(ThreadNode)); (*p3).ltag=0; (*p3).rtag=0; (*p3).value=3; (*p3).lChild=p6; (*p3).rChild=p7; ThreadNode *p1=(ThreadNode *)malloc(sizeof(ThreadNode)); (*p1).ltag=0; (*p1).rtag=0; (*p1).value=1; (*p1).lChild=p2; (*p1).rChild=p3; root=p1; return root; } //指向当前被访问的结点 ThreadNode *q1=NULL; void createPreThread(ThreadTree root){ if(root!=NULL){ preThread(root); if((*q1).rChild==NULL){ (*q1).rtag=1; } } } void preThread(ThreadTree root){ ThreadNode *pre=NULL; if(root!=NULL){ pre=q1; q1=root; if((*q1).lChild==NULL){ (*q1).lChild=pre; (*q1).ltag=1; } if(pre!=NULL&&(*pre).rChild==NULL){ (*pre).rChild=q1; (*pre).rtag=1; } if((*root).ltag==0){ preThread((*root).lChild); } preThread((*root).rChild); } } ThreadNode* preFirstNode(ThreadNode *p){ if(p!=NULL){ return p; } return NULL; } ThreadNode* preNextNode(ThreadNode *p){ //右指针存放的是后继，直接返回 if((*p).rtag==1){ return (*p).rChild; }else{ //右指针存放的不是后继 //判断有没有左孩子，有直接返回，否则返回右孩子 if((*p).ltag==0){ return (*p).lChild; }else{ return (*p).rChild; } } } int main(){ return 0; }
//二叉树--链式存储 #include树的存储结构#include #define MAXSIZE 100 struct ThreadNode{ //数据域 int value; //左孩子 struct ThreadNode *lChild; //右孩子 struct ThreadNode *rChild; //1--前驱结点 0--左孩子 int ltag; //1--后继结点 0--右孩子 int rtag; }; typedef struct ThreadNode ThreadNode; typedef struct ThreadNode* ThreadTree; ThreadTree* initTree(ThreadTree root){ root=NULL; return root; } ThreadTree* constructTree(ThreadTree root){ ThreadNode *p11=(ThreadNode *)malloc(sizeof(ThreadNode)); (*p11).ltag=0; (*p11).rtag=0; (*p11).value=11; (*p11).lChild=NULL; (*p11).rChild=NULL; ThreadNode *p12=(ThreadNode *)malloc(sizeof(ThreadNode)); (*p12).ltag=0; (*p12).rtag=0; (*p12).value=12; (*p12).lChild=NULL; (*p12).rChild=NULL; ThreadNode *p5=(ThreadNode *)malloc(sizeof(ThreadNode)); (*p5).ltag=0; (*p5).rtag=0; (*p5).value=5; (*p5).lChild=NULL; (*p5).rChild=p11; ThreadNode *p6=(ThreadNode *)malloc(sizeof(ThreadNode)); (*p6).ltag=0; (*p6).rtag=0; (*p6).value=6; (*p6).lChild=p12; (*p6).rChild=NULL; ThreadNode *p7=(ThreadNode *)malloc(sizeof(ThreadNode)); (*p7).ltag=0; (*p7).rtag=0; (*p7).value=7; (*p7).lChild=NULL; (*p7).rChild=NULL; ThreadNode *p2=(ThreadNode *)malloc(sizeof(ThreadNode)); (*p2).ltag=0; (*p2).rtag=0; (*p2).value=2; (*p2).lChild=NULL; (*p2).rChild=p5; ThreadNode *p3=(ThreadNode *)malloc(sizeof(ThreadNode)); (*p3).ltag=0; (*p3).rtag=0; (*p3).value=3; (*p3).lChild=p6; (*p3).rChild=p7; ThreadNode *p1=(ThreadNode *)malloc(sizeof(ThreadNode)); (*p1).ltag=0; (*p1).rtag=0; (*p1).value=1; (*p1).lChild=p2; (*p1).rChild=p3; root=p1; return root; } //指向当前被访问的结点 ThreadNode *q3=NULL; void createPostThread(ThreadTree root){ if(root!=NULL){ postThread(root); if((*q3).rChild==NULL){ (*q3).rtag=1; } } } void postThread(ThreadTree root){ ThreadNode *pre=NULL; if(root!=NULL){ postThread((*root).lChild); postThread((*root).rChild); pre=q3; q3=root; if((*q3).lChild==NULL){ (*q3).lChild=pre; (*q3).ltag=1; } if(pre!=NULL&&(*pre).rChild==NULL){ (*pre).rChild=q3; (*pre).rtag=1; } } } ThreadNode* postPreNode(ThreadNode *p){ //左指针存放的是前驱，直接返回 if((*p).ltag==1){ return (*p).ltag; }else{ //左指针存放的不是前驱 //判断有没有右孩子，有直接返回，否则返回左孩子 if((*p).rtag==0){ return (*p).rtag; }else{ return (*p).lChild; } } } int main(){ return 0; }
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）