C 语言源码:二叉树求宽度与深度

2023-04-2908:34:32数据结构与算法Comments1,374 views字数 1509阅读模式

C 语言 二叉树 求宽度与深度文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/37703.html

C 语言源码:二叉树求宽度与深度文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/37703.html

源码如下:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/37703.html

#include <stdio.h>#include <stdlib.h>
typedef struct Tree {    char ch;    struct Tree *left;    struct Tree *right;} Tree;
typedef struct queNode {    Tree *p;    int lno; //层号信息} queNode;
//求宽度void GetMaxHW(Tree *root){    queNode Q[100];    Tree *q = NULL;    int frontQ = 0, rearQ = 0;    int Lno;    if (!root) return;
    Q[++rearQ].p = root;    Q[rearQ].lno = 1;
    while(frontQ != rearQ) {        q = Q[++frontQ].p;        Lno = Q[frontQ].lno;        if (q->left != NULL) {            Q[++rearQ].p = q->left;            Q[rearQ].lno = Lno + 1;        }        if (q->right != NULL) {            Q[++rearQ].p = q->right;            Q[rearQ].lno = Lno + 1;        }    }// Lno 为深度
    int width = 0;    for (int i = 1; i <= Lno; i++) {        int num = 0;        for (int j = 1; j <= rearQ; j++) {            if(Q[j].lno == i) {                num++;            }        }        if (num > width) {            width = num;        }    }
    printf("height = %d, width = %d\n", Lno, width);}
Tree *newNode(char ch){    Tree *t = (Tree *)malloc(sizeof(Tree));    t->ch = ch;    t->left = t->right = NULL;    return t;}
Tree *create(){    char ch;    ch = getchar();    Tree *node = NULL;    if (ch == '#') {        node = NULL;    } else {        node = newNode(ch);        node->left = create();        node->right = create();    }    return node;}
void preOrder(Tree *root){    if (root) {        printf("%c ", root->ch);        preOrder(root->left);        preOrder(root->right);    }}
void inOrder(Tree *root){    if (root) {        inOrder(root->left);        printf("%c ", root->ch);        inOrder(root->right);    }}
void postOrder(Tree *root){    if (root) {        postOrder(root->left);        postOrder(root->right);        printf("%c ", root->ch);    }}

int main(){    Tree *root = create();    printf("preOrder: "); preOrder(root);    printf("\n");    printf("inOrder: "); inOrder(root);    printf("\n");    printf("postOrder: "); postOrder(root);    printf("\n");    GetMaxHW(root);    printf("\n");    return 0;}

编译,运行:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/37703.html

[root@localhost tree]# ./TreeHW ABC##D##E#F##preOrder: A B C D E F inOrder: C B D A E F postOrder: C D B F E A height = 3, width = 3
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/37703.html
  • 本站内容整理自互联网,仅提供信息存储空间服务,以方便学习之用。如对文章、图片、字体等版权有疑问,请在下方留言,管理员看到后,将第一时间进行处理。
  • 转载请务必保留本文链接:https://www.cainiaoxueyuan.com/suanfa/37703.html

Comment

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定