ㅤcoderitl

V1

2022/02/07阅读:54主题:萌绿

二叉树先序创建

【问题描述】二叉树可以采用两种方式存储,其中经常使用的是二叉链表存储方式。利用扩展先序序列创建以二叉链表存储的二叉树按树状打印此二叉树,求此二叉树的高度以及叶子结点的个数,并输出。

【输入形式】 输入某二叉树的扩展先序序列。(二叉树中元素为 char 类型) 注意:输入的扩展先序序列必须是某二叉树的扩展序列,不能随意输入。

【输出形式】 逆时针旋转90度的二叉树,根节点层次号为 1,每进一层,显示3个空格;输出的二叉树的叶子结点个数和高度,各占一行。

程序实现


  /**********************************************
  Author: coder-itl
  date: 2021-11-07
  **********************************************/


  #include <stdio.h>
  #include <stdlib.h>
  #include <string.h>

  #define NAME_SIZE 1024

  typedef char ElementType;
  /* 统计节点数 */
  int count = 0;

  /* 二叉树数据结构定义 **/
  typedef struct BiTreeNode {
      ElementType data;
      struct BiTreeNode *leftChild;
      struct BiTreeNode *rightChild;
  } BiTreeNode, *BiTree;

  /**
   * 先序创建二叉树
   * @param tree
   */

  void CreateBiTree(BiTree *tree) {
      char ch;
      ch = getchar();
      /* . 代表为空 */
      if (ch == '.') {
          *tree = NULL;
          return;
      } else {
          *tree = (BiTree) malloc(sizeof(BiTreeNode));
          (*tree)->data = ch;
          CreateBiTree(&((*tree)->leftChild));
          CreateBiTree(&((*tree)->rightChild));
      }
  }

  /**
   * 后序遍历求二叉树 tree 高度的递归算法
   * @param tree
   * @return
   */

  int PostTreeDepth(BiTree tree) {
      int hl, hr, max;
      if (tree != NULL) {
          /* 求左子树的深度 */
          hl = PostTreeDepth(tree->leftChild);
          /* 求右子树的深度 */
          hr = PostTreeDepth(tree->rightChild);
          /* 得到左右子树深度较大者 */
          max = hl > hr ? hl : hr;
          /* 返回树的深度 */
          return max + 1;
      } else {
          /* 如果是空树返回 0 */
          return 0;
      }

  }

  /**
   * 按逆中序输出节点,用层深决定的左右位置
   * @param bt
   * @param nLayer
   */

  void PrintTree(BiTree bt, int nLayer) {
      int i;
      if (bt == NULL) {
          return;
      }
      PrintTree(bt->rightChild, nLayer + 1);
      for (i = 0; i < nLayer; i++) {
          printf("%-3s""");
      }
      /* 按逆中序输出节点,用层深决定的左右位置 */
      printf("%c\n", bt->data);
      PrintTree(bt->leftChild, nLayer + 1);
  }


  int leaf(BiTree root) {
      /* 先序遍历输出二叉树中的叶子节点,root为指向二叉树根节点的指针 */
      if (root != NULL) {
          leaf(root->leftChild);
          leaf(root->rightChild);
          if (root->leftChild == NULL && root->rightChild == NULL) {
              count++;
          }
      }
      return count;
  }

  int main() {
      int treeHeight;
      BiTree tree;
      /* 以先序创建树 */
      CreateBiTree(&tree);
      /* 按照树状打印树 */
      printf("The BinaryTree is:\n");
      PrintTree(tree, 1);
      /* 高度 */
      treeHeight = PostTreeDepth(tree);
      printf("The Height of BinaryTree:%d", treeHeight);
      /* 叶子节点个数 */
      count = leaf(tree);
      printf("\nThe Number of Leaf:%d", count);
      return 0;
  }

  • 结果输出 先序创建树、并按逆中序输出

分类:

后端

标签:

C++

作者介绍

ㅤcoderitl
V1