首页 > 代码库 > 树的概念与实现
树的概念与实现
树是n（n>=0）个节点的有限集。n=0时称为空树。在非空树中，只有一个根节点，子树的个数没有限制，但是一定不相交。
结点拥有的子树数成为结点的度。度为0的结点称为叶结点。树的度是树内各结点的度的最大值。
树中节点的最大层次称为树的深度或高度。
如果将树中结点的各子树看成从左到右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。
森林是m（m>=0）棵互不相交的树的集合。
树的存储结构：
双亲表示法：每个结点存储数据和双亲的位置
孩子表示法：数据+孩子位置+孩子位置……
孩子兄弟表示法：数据+第一个孩子位置+第一个右兄弟位置
二叉树：空树或是由一个根节点和两棵不相交的子树。每个结点最多只有两棵树，左子树和右子树是有序的，一棵子树也得分左右。
在一棵二叉树中，所有分支结点都存在左子树和右子树，并且所有的叶子结点都在同一层，即为满二叉树。
对一棵具有n个结点的二叉树编号，如果编号i的结点与同样深度的满二叉树中编号为i的节点在二叉树中的位置完全相同，则成为完全二叉树。满二叉树必是完全二叉树，完全二叉树不一定是满二叉树。
二叉树遍历：前序遍历：根左右；中序遍历：左根右；后续遍历：左右根；层序遍历：一层二层三层….
1 /*树的实现*/ 2 #include <stdio.h> 3 #include <stdlib.h> 4 #include <time.h> 5 6 typedef char ElemType; 7 #define OK 1 8 #define ERROR 0 9 typedef int Status; 10 11 //二叉树 12 typedef struct BiTNode 13 { 14 ElemType data; 15 struct BiTNode *lchild, *rchild; 16 }BiTNode,*BiTree; 17 18 void CreateBiTree(BiTree *T) //二叉树创建，每次输入一个字符 19 { 20 ElemType ch; 21 ElemType cx; 22 printf("Input data:"); 23 scanf_s("%c", &ch); 24 cx = getchar(); 25 if (ch == ‘#‘) 26 { 27 *T = NULL; 28 } 29 else 30 { 31 *T = (BiTree)malloc(sizeof(BiTNode)); 32 if (!(*T)) 33 exit(0); 34 (*T)->data =http://www.mamicode.com/ ch; 35 CreateBiTree(&(*T)->lchild); 36 CreateBiTree(&(*T)->rchild); 37 } 38 } 39 void PreOrderTraverse(BiTree T) //前序遍历 40 { 41 if (T == NULL) 42 return; 43 printf("%d ", T->data); 44 PreOrderTraverse(T->lchild); 45 PreOrderTraverse(T->rchild); 46 } 47 void PostOrderTraverse(BiTree T) //后序遍历 48 { 49 if (T == NULL) 50 return; 51 PreOrderTraverse(T->lchild); 52 PreOrderTraverse(T->rchild); 53 printf("%d ", T->data); 54 } 55 void InOrderTraverse(BiTree T) //后序遍历 56 { 57 if (T == NULL) 58 return; 59 PreOrderTraverse(T->lchild); 60 printf("%d ", T->data); 61 PreOrderTraverse(T->rchild); 62 } 63 64 /*线索二叉树*/ 65 typedef enum{Link,Thread} PointerTag; 66 typedef struct BiThrNode 67 { 68 ElemType data; 69 struct BiThrNode *lchild, *rchild; 70 PointerTag LTag; 71 PointerTag RTag; 72 }BiThrNode, *BiThrTree; 73 BiThrTree pre; 74 void CreateBiThrTree(BiThrTree *T) //线索二叉树的创建,一次输入中序遍历格式，例如：ab##c## 75 { 76 char ch; 77 ElemType cx; 78 ch = getchar(); 79 if (ch == ‘#‘) 80 { 81 *T = NULL; 82 } 83 else 84 { 85 *T = (BiThrTree)malloc(sizeof(BiThrNode)); 86 if (!(*T)) 87 exit(0); 88 (*T)->data =http://www.mamicode.com/ ch; 89 (*T)->LTag = Link; 90 (*T)->RTag = Link; 91 CreateBiThrTree(&(*T)->lchild); 92 CreateBiThrTree(&(*T)->rchild); 93 } 94 } 95 void InThreading(BiThrTree p) //二叉树线索化 96 { 97 if (p) 98 { 99 InThreading(p->lchild);100 if (!p->lchild)101 {102 p->LTag = Thread;103 p->lchild = pre;104 }105 if (!pre->rchild)106 {107 pre->RTag = Thread;108 pre->rchild = p;109 }110 pre = p;111 InThreading(p->rchild);112 }113 }114 BiThrTree M; //保存线索二叉树的头节点地址115 void InOrderThreading(BiThrTree *p, BiThrTree T) //线索二叉树初始化116 {117 *p = (BiThrTree)malloc(sizeof(BiThrNode));118 (*p)->LTag = Link;119 (*p)->RTag = Thread;120 (*p)->rchild = *p;121 M = (*p);122 if (!T)123 (*p)->lchild = *p;124 else125 {126 (*p)->lchild = T;127 pre = *p;128 InThreading(T);129 pre->rchild = *p;130 pre->RTag = Thread;131 (*p)->rchild = pre;132 }133 }134 Status InOrderTraverse_Thr(BiThrTree T) //中序遍历二叉线索树链表表示的二叉树135 {136 BiThrTree p;137 p = T->lchild;138 while (p != T)139 {140 while (p->LTag == Link)141 p = p->lchild;142 printf("%c ", p->data);143 while (p->RTag == Thread && p->rchild != T)144 {145 p = p->rchild;146 printf("%c", p->data);147 }148 p = p->rchild;149 }150 return OK;151 }152 153 int main()154 {155 BiTree T=NULL;156 BiThrTree S,P = NULL;157 char cx;158 char opp = ‘-1‘;159 char tmp;160 161 printf("\n1.创建二叉树 \n2.前序遍历 \n3.后序遍历 \n4.中序遍历 \n5 创建线索二叉树 \n6 线索二叉树的中序遍历0.退出 \n请选择你的操作：\n");162 163 while (opp != ‘0‘) {164 opp = getchar();165 switch (opp) {166 case ‘1‘:167 tmp = getchar();168 CreateBiTree(&T);169 printf("create finish!\n");170 break;171 case ‘2‘:172 PreOrderTraverse(T);173 printf("\n");174 break;175 case ‘3‘:176 PostOrderTraverse(T);177 printf("\n");178 break;179 case ‘4‘:180 InOrderTraverse(T);181 printf("\n");182 break;183 case ‘5‘:184 tmp = getchar(); //读出回车符185 CreateBiThrTree(&P);186 printf("create finish!\n");187 InOrderThreading(&S,P);188 printf("\n");189 break;190 case ‘6‘:191 InOrderTraverse_Thr(M);192 printf("\n");193 break;194 case ‘0‘:195 exit(0);196 }197 }198 }
树的概念与实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。