数据结构（4）二叉树的基本操作 |
您所在的位置：网站首页 › 二叉树的创建代码百度网盘 › 数据结构（4）二叉树的基本操作 |
数据结构（4）二叉树的基本操作
|
作为一个数据结构学习的新手，这篇文章也算是笔记了，请根据目录食用 目录 单链表的操作（C语言） 一、存储结构 二、前序递归建立二叉树 三、前序递归遍历二叉树 四、前序非递归遍历二叉树 五、中序非递归遍历二叉树 六、后序非递归遍历二叉树 七、层序遍历 八、层序遍历Pro（按层输出）（舍去，采用Pro++） 九、层序遍历Pro++（按层输出） 层序遍历Pro和层序遍历Pro++的对比反思 十、树的深度——递归实现 十一、结点数统计——递归实现 十二、度为0的结点的个数——递归实现 十三、度为1的结点的个数——递归实现 十四、度为2的结点的个数——递归实现 实现的总代码 单链表的操作（C语言） 一、存储结构 typedef struct Bitnode { Elemtype data; Bitnode *lchild, *rchild; } Bitnode, *Bitree; 二、前序递归建立二叉树 void Creat(Bitree &T) { Elemtype n; scanf("%c", &n); if (n == '#') T = NULL; else { T = (Bitnode *)malloc(sizeof(Bitnode)); T->data = n; T->lchild = NULL; T->rchild = NULL; Creat(T->lchild); Creat(T->rchild); } } 三、前序递归遍历二叉树 void Inorder(Bitree T) { if (T) { printf("%c", T->data);//根 Inorder(T->lchild);//左 Inorder(T->rchild);//右 } }中序递归和后序递归只需要调整语句的顺序即可，中序左根右，后序左右根 四、前序非递归遍历二叉树 void Fir_Inorder(Bitree T) { Bitree stack[100], p = T; //用栈来实现 int top = 0; while (p || top) { while (p) { stack[top] = p; top++; printf("%c", p->data); p = p->lchild; } top--; p = stack[top]; p = p->rchild; } }【思路】由于前序的输出顺序为根左右，当遇到根的时候，将根压到栈里，并输出根的data，再检查它的左孩子，当没有左孩子的时候（p==NULL），指向栈顶，然后检查它的右孩子；当有左孩子的时候（p ! = NULL），左孩子成为现在的根节点，重复上述步骤，直至所有结点都输出（栈空）。 五、中序非递归遍历二叉树 void Mid_Inorder(Bitree T) { Bitree stack[100], p = T; int top = 0; while (p || top) { while (p) { stack[top] = p; top++; p = p->lchild; } top--; p = stack[top]; printf("%c", p->data); p = p->rchild; } }【思路】和前序非递归遍历的思路基本一致，只是输出顺序发生改变 六、后序非递归遍历二叉树 void Las_Inorder(Bitree T) { Bitree stack[100], p = T; int tag[100]; int top = 0; while (p || top) { while (p) { top++; stack[top] = p; p = p->lchild; tag[top] = 1; } if (tag[top] == 1) { p = stack[top]; tag[top] = 2; p = p->rchild; } else { p = stack[top]; printf("%c", p->data); top--; p = NULL; } } }【思路】由于后序遍历的输出顺序为左右根，也就是说，需要检查并分别输出根节点的左右孩子后，才能输出根节点，也就是说在第三次访问根节点时才输出该根节点。 第一次访问，入栈，并设置标志（tag[top] = 1），访问该结点的左孩子； 第二次访问（该结点的左孩子为空），指针指向栈顶元素，并设置标志（tag[top] = 2），访问该结点的右孩子； 第三次访问（该结点的右孩子为空），指针指向栈顶元素，输出栈顶元素，栈顶指针减一。 关键的是这个p = NULL，现在这个位置已经输出了（相当于左孩子或者右孩子为空了），需要让程序去处理前一个结点（前一个结点必然是被访问过一次或两次的），所以指针p指空，这样才可以进行第二次或第三次的访问。 七、层序遍历 void Level(Bitree T) { Bitree Q[100], p = T; //用队列来实现 int rear, front; rear = front = 0; rear++; Q[rear] = p; while (rear != front) { front++; p = Q[front]; printf("%c", p->data); //每输出一个队头的结点，就要将它的左右孩子入队 if (p->lchild) { rear++; Q[rear] = p->lchild; } if (p->rchild) { rear++; Q[rear] = p->rchild; } } }【思路】每输出一个队头的结点，就要将它的左右孩子入队，实现层序遍历 当一层的结点全被访问过后，下一层的结点也全部入队了（对于实现按层输出有用的一个点） 【进一步思考】这样的输出结果，并不能让人直观地看出，哪个数据是属于哪一层的，于是有了下面的代码 八、层序遍历Pro（按层输出）（舍去，采用Pro++） void Lever_pro(Bitree T) { Bitree Q[100], p = T; int rear, front, tag[10], i = 1, j = 0, k = 0, num = 0; //i标志层数，j执行循环，k标志每层的结点数，由于k每次需要归零， //故还需要设置变量num记录每层的结点数并参与执行循环 rear = front = 0; rear++; Q[rear] = p; num = 1; while (rear != front) { printf("第%d层的数据为：", i); for (j = 0; j < num; j++) { front++; p = Q[front]; printf("%c", p->data); if (p->lchild) { rear++; Q[rear] = p->lchild; k++; } if (p->rchild) { rear++; Q[rear] = p->rchild; k++; } } num = k; k = 0; printf("\n"); i++; } }【思路】记录每一层元素的个数，进而控制输出次数。 【进一步思考】循环的时间复杂度就要比较高了，那么可以不使用循环吗？可以。只要每次输出之后，将现在所在层的结点个数减一不就完事了嘛。 当然，还需要进行一个判断，判断结点数是否为0，当当前层结点数为零的时候，开始输出下一层，需要先将下一层结点数赋值给当前层结点数。代码如下： 九、层序遍历Pro++（按层输出） void Lever_pro_pro(Bitree T) { Bitree Q[100], p = T; int rear, front, nowcount = 0, nextcount = 0, i = 1, tag = 0; rear = front = 0; rear++; Q[rear] = p; nowcount = 1; while (rear != front) { if (tag == 0) printf("第%d层的元素为：", i); front++; p = Q[front]; printf("%c", p->data); nowcount--; if (p->lchild) { rear++; Q[rear] = p->lchild; nextcount++; } if (p->rchild) { rear++; Q[rear] = p->rchild; nextcount++; } tag = 1; if (nowcount == 0) { nowcount = nextcount; nextcount = 0; i++; printf("\n"); tag = 0; } } }【分析】只需在输出的时候设置一个标志（nowcount）控制输出即可，其余代码与“层序遍历”基本相同 层序遍历Pro和层序遍历Pro++的对比反思设置的标志该怎么巧妙地使用？ 根据“当一层的结点全被访问过后，下一层的结点也全部入队了”这一个特点进行考虑 十、树的深度——递归实现 int Depth(Bitree T) { int m, n; if (T == NULL) return 0; else { m = Depth(T->lchild); n = Depth(T->rchild); if (m > n) return m + 1; else return n + 1; } } 十一、结点数统计——递归实现 int NodeCount(Bitree T) { if (T) return NodeCount(T->lchild) + NodeCount(T->rchild) + 1; else return 0; }【思路】结点数 = 根节点 + 左子树结点数 + 右子树结点数 十二、度为0的结点的个数——递归实现 int Node0Count(Bitree T) { if (T) { if (T->lchild == NULL && T->rchild == NULL) return Node0Count(T->lchild) + Node0Count(T->rchild) + 1; else return Node0Count(T->lchild) + Node0Count(T->rchild); } else return 0; } 十三、度为1的结点的个数——递归实现 int Node1Count(Bitree T) { if (T) { if (T->lchild != NULL && T->rchild == NULL || T->lchild == NULL && T->rchild != NULL) return Node1Count(T->lchild) + Node1Count(T->rchild) + 1; else return Node1Count(T->lchild) + Node1Count(T->rchild); } else return 0; } 十四、度为2的结点的个数——递归实现 int Node2Count(Bitree T) { if (T) { if (T->lchild != NULL && T->rchild != NULL) return Node2Count(T->lchild) + Node2Count(T->rchild) + 1; else return Node2Count(T->lchild) + Node2Count(T->rchild); } return 0; } 实现的总代码 #include #include //二叉树的基本操作 typedef char Elemtype; typedef struct Bitnode { Elemtype data; Bitnode *lchild, *rchild; } Bitnode, *Bitree; //前序递归建立二叉树 void Creat(Bitree &T) { Elemtype n; scanf("%c", &n); if (n == '#') T = NULL; else { T = (Bitnode *)malloc(sizeof(Bitnode)); T->data = n; T->lchild = NULL; T->rchild = NULL; Creat(T->lchild); Creat(T->rchild); } } //前序递归遍历二叉树 void Inorder(Bitree T) { if (T) { printf("%c", T->data); Inorder(T->lchild); Inorder(T->rchild); } } //前序非递归遍历二叉树 void Fir_Inorder(Bitree T) { Bitree stack[100], p = T; int top = 0; while (p || top) { while (p) { stack[top] = p; top++; printf("%c", p->data); p = p->lchild; } top--; p = stack[top]; p = p->rchild; } } //中序非递归遍历 void Mid_Inorder(Bitree T) { Bitree stack[100], p = T; int top = 0; while (p || top) { while (p) { stack[top] = p; top++; p = p->lchild; } top--; p = stack[top]; printf("%c", p->data); p = p->rchild; } } //后序非递归遍历 void Las_Inorder(Bitree T) { Bitree stack[100], p = T; int tag[100]; int top = 0; while (p || top) { while (p) { top++; stack[top] = p; p = p->lchild; tag[top] = 1; } if (tag[top] == 1) { p = stack[top]; tag[top] = 2; p = p->rchild; } else { p = stack[top]; printf("%c", p->data); top--; p = NULL; } } } //层序遍历 void Level(Bitree T) { Bitree Q[100], p = T; int rear, front; rear = front = 0; rear++; Q[rear] = p; while (rear != front) { front++; p = Q[front]; printf("%c", p->data); if (p->lchild) { rear++; Q[rear] = p->lchild; } if (p->rchild) { rear++; Q[rear] = p->rchild; } } } //按层输出 void Lever_pro(Bitree T) { Bitree Q[100], p = T; int rear, front, tag[10], i = 1, j = 0, k = 0, num = 0; //i标志层数，j执行循环，k标志每层的结点数，由于k每次需要归零， //故还需要设置变量num记录每层的结点数并参与执行循环 rear = front = 0; rear++; Q[rear] = p; num = 1; while (rear != front) { printf("第%d层的数据为：", i); for (j = 0; j < num; j++) { front++; p = Q[front]; printf("%c", p->data); if (p->lchild) { rear++; Q[rear] = p->lchild; k++; } if (p->rchild) { rear++; Q[rear] = p->rchild; k++; } } num = k; k = 0; printf("\n"); i++; } } void Level_pro_pro(Bitree T) { Bitree Q[100], p = T; int rear, front, nowcount = 0, nextcount = 0, i = 1, tag = 0; rear = front = 0; rear++; Q[rear] = p; nowcount = 1; while (rear != front) { if (tag == 0) printf("第%d层的元素为：", i); front++; p = Q[front]; printf("%c", p->data); nowcount--; if (p->lchild) { rear++; Q[rear] = p->lchild; nextcount++; } if (p->rchild) { rear++; Q[rear] = p->rchild; nextcount++; } tag = 1; if (nowcount == 0) { nowcount = nextcount; nextcount = 0; i++; printf("\n"); tag = 0; } } } //树的深度 int Depth(Bitree T) { int m, n; if (T == NULL) return 0; else { m = Depth(T->lchild); n = Depth(T->rchild); if (m > n) return m + 1; else return n + 1; } } //树的结点数 int NodeCount(Bitree T) { if (T) return NodeCount(T->lchild) + NodeCount(T->rchild) + 1; else return 0; } //统计二叉树中度为0的结点的个数 int Node0Count(Bitree T) { if (T) { if (T->lchild == NULL && T->rchild == NULL) return Node0Count(T->lchild) + Node0Count(T->rchild) + 1; else return Node0Count(T->lchild) + Node0Count(T->rchild); } else return 0; } //统计二叉树中度为1的结点的个数 int Node1Count(Bitree T) { if (T) { if (T->lchild != NULL && T->rchild == NULL || T->lchild == NULL && T->rchild != NULL) return Node1Count(T->lchild) + Node1Count(T->rchild) + 1; else return Node1Count(T->lchild) + Node1Count(T->rchild); } else return 0; } //统计二叉树中度为2的结点的个数 int Node2Count(Bitree T) { if (T) { if (T->lchild != NULL && T->rchild != NULL) return Node2Count(T->lchild) + Node2Count(T->rchild) + 1; else return Node2Count(T->lchild) + Node2Count(T->rchild); } return 0; } int main() { Bitree T; int depth; Creat(T); printf("前序非递归的结果："); Fir_Inorder(T); printf("\n"); printf("中序非递归的结果："); Mid_Inorder(T); printf("\n"); printf("后序非递归的结果："); Las_Inorder(T); printf("\n"); printf("层序递归的结果："); Level(T); printf("\n"); Lever_pro(T); depth = Depth(T); printf("树的深度为:%d\n", depth); printf("树的结点的个数:"); printf("%d\n", NodeCount(T)); printf("度为0的结点的个数:"); printf("%d\n", Node0Count(T)); printf("度为1的结点的个数:"); printf("%d\n", Node1Count(T)); printf("度为2的结点的个数:"); printf("%d\n", Node2Count(T)); return 0; }【输出结果 】
|
【本文地址】