@yanglt7
2018-10-21T15:50:02.000000Z
字数 6736
阅读 873
数据结构和算法
Tips：
如果想要知道某结点的孩子，需要遍历整个树结构。
代码实现
//树的双亲表示法结点结构定义#define MAX_TREE_SIZE 100typedef int ElemType;typedef struct PTNode{ElemType data; //结点数据int parent; //双亲位置}PTNode；typedef struct{PTNode nodes[MAX_TREE_SIZE];int r; //根的位置int n; //结点数目}PTree;
#define MAX_TREE_SIZE 100typedef char ElemType;//孩子结点typedef struct CTNode{int child; //孩子结点的下标struct CTNode *next; //指向下一个孩子结点的指针} *ChildPtr;//表头结构typedef struct{ElemType data; //存放在树中的结点的数据int parent; //存放双亲的下标ChildPtr firstchild; //指向第一个孩子的指针} CTBox;//树结构typedef struct{CTBox nodes[MAX_TREE_SIZE]; //结点数组int r,n;};
拥有三个结点的普通树只有两种情况：两层或者三层。但对于二叉树来说，由于要区分左右，所以就演变成五种形态。
斜树
满二叉树
| 元素 | A | B | C | D | E | F | ^ |
|---|---|---|---|---|---|---|---|
| 下标 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| lchild | data | rchild |
|---|
- 结构定义代码
typedef struct BiTNode{ElemType data;struct BiTNode *lchild, *rchild；} BiTNode, *BiTree;
若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。
遍历的顺序为：ABDHIEJCFKG
若二叉树为空，则空操作返回，否则先中序遍历左子树，然后访问根结点，再中序遍历右子树。
遍历的顺序为：HDIBEJAFKCG
若树为空，则空操作返回，否则先从左到右先叶子后结点的方式遍历左右子树，最后访问根结点。
遍历的顺序为：HIDJEBKFGCA
题目要求：建立二叉树并输出每个字符所在的层数。如右图要求输出
代码实现
//前序遍历#include <stdio.h>#include <stdlib.h>typedef char ElemType;typedef struct BiTNode{char data;struct BiTNode *lchild, *rchild;} BiTNode, *BiTree;//创建一棵二叉树，约定用户遵照前序遍历的方式输入数据CreateBiTree(BiTree *T){char c;scanf("%c", &c);if( ' ' == c ){*T = NULL;}else{*T = (BiTNode *)malloc(sizeof(BiTNode));(*T)->data = c;CreateBiTree(&(*T)->lchild);CreateBiTree(&(*T)->rchild);}}//访问二叉树结点的具体操作visit(char c, int level){printf("%c 位于第 %d 层\n", c, level);}//前序遍历二叉树PreOrderTraverse(BiTree T, int level){if( T ){visit(T->data, level);PreOrderTraverse(T->lchild, level+1);PreOrderTraverse(T->rchild, level+1);}}int main(){int level = 1;BiTree T = NULL;CreateBiTree(&T);PreOrderTraverse(T, level);return 0;}
| lchild | ltag | data | rtag | rchild |
|---|
- ltag为0时指向该结点的左孩子，为1时指向该结点的前驱
- rtag为0时指向该结点的右孩子，为1时指向该结点的后继
#include <stdio.h>#include <stdlib.h>typedef char ElemType;//线索存储标志位//Link(0):表示指向左右孩子的指针//Thread(1)：表示指向前驱后继的线索typedef enum {Link, Thread} PointerTag;typedef struct BiThrNode{char data;struct BiThrNode *lchild, *rchild;PointerTag ltag;PointerTag rtag;} BiThrNode, *BiThrTree;//全局变量，始终指向刚刚访问过的结点BiThrTree pre;//创建一棵二叉树，约定用户遵照前序遍历的方式输入数据void CreateBiThrTree(BiThrTree *T){char c;scanf("%c", &c);if( ' ' == c ){*T = NULL;}else{*T = (BiThrNode *)malloc(sizeof(BiThrNode));(*T)->data = c;(*T)->ltag = Link;(*T)->rtag = Link;CreateBiThrTree(&(*T)->lchild);CreateBiThrTree(&(*T)->rchild);}}//中序遍历线索化void InThreading(BiThrTree T){if( T ){InThreading( T->lchild ); //递归左孩子线索化//结点处理//如果该结点没有左孩子，设置ltag为Thread，并把lchild指向刚刚访问的结点if( !T->lchild ){T->ltag = Thread;T->lchild = pre;}if( !pre->rchild ){pre->rtag = Thread;pre->rchild = T;}pre = T;InThreading( T->rchild ); //递归右孩子线索化}}void InOrderThreading( BiThrTree *p, BiThrTree T ){*p = (BiThrTree)malloc(sizeof(BiThrNode));(*p)->ltag = Link;(*p)->rtag = Thread;(*p)->rchild = *p;if( !T ){(*p)->lchild = *p;}else{(*p)->lchild = T;pre = *p;InThreading( T );pre->rchild = *p;pre->rtag = Thread;(*p)->rchild = pre;}}void visit( char c ){printf("%c", c );}//中序遍历二叉树，非递归void InOrderTraverse( BiThrTree T ){BiThrTree p;p = T->lchild;while( p != T ){while( p->ltag == Link ){p = p->lchild;}visit( p->data );while( p->rtag == Thread && p->rchild != T ){p = p->rchild;visit(p->data);}p = p->rchild;}}int main(){BiThrTree P, T = NULL;CreateBiThrTree( &T );InOrderThreading( &P, T );printf("中序遍历输出结果为： \n");InOrderTraverse( P );return 0;}
后根遍历：先依次遍历每棵子树，然后再访问根结点
先根遍历结果：ABEFCGDHIJ
森林的遍历也分为前序遍历和后序遍历，其实就是按照树的先根遍历和后根遍历依次访问森林的每一棵树
树、森林的前根（序）遍历和二叉树的前序遍历结果相同
先把二叉树简化成叶子结点带权的二叉树（注：树结点间的连线相关的数叫做权，Weight）
结点的路径长度：
树的路径长度：
结点带权路径长度：
树的带权路径长度：
WPL的值越小，说明构造出来的二叉树性能越优