尼采般地抒情

公告栏

此网站主题为本人手写主题, 主题待开源···

站点信息

文章总数目: 305
已运行时间: 1063
目录
  1. 实验报告
  2. 实验代码
  3. DFS 遍历算法
    1. 手写例子
    2. 前序遍历
    3. 中序遍历
    4. 后序遍历

尼采般地抒情

尼采般地抒情

公告栏

此网站主题为本人手写主题, 主题待开源···

站点信息

文章总数目: 305
已运行时间: 1063

实验报告

编写一个程序,实现二叉树的各种运算,并在此基础上设计一个程序完成如下功能:


(1)创建一棵二叉树(用键盘按照先序遍历序列输入一个字符串生成二叉树);

(2)输出前序、中序、后序遍历的遍历序列;  

(3)统计并输出二叉树的的结点个数;

(4)输出二叉树的叶子结点的个数;(选做)


实验要求:  


用键盘输入一个字符串,按照满二叉树的特点生成一棵二叉树。


测试用例要求:


如下二叉树的输入字符串为:ABD###C#E##

书写方法:碰到#说明该二叉树是一棵空树,注意分配(下面缺两个左右补两个#,缺一个左/右子树,补一个#)

二叉链表的结点类型(C++):


Typedef structure  tnode{

    int   data;
    structure  tnode   *lchild, *rchild;

}bitree,\*bitlink ;

实验代码

用上面的二叉树作为例子:

#include<bits/stdc++.h>
using namespace std;
typedef int Status;
typedef char TElemType;
#define OVERFLOW -1
#define ERROR 0
#define OK 1
char ch;

/\*\*

- 采用二叉链表的存储形式
  */
  typedef struct BiTNode
  {
  TElemType data;
  struct BiTNode *lchild, *rchild;
  }BiTNode, *BiTree;

/\*\*

- 创建一棵二叉树
  \*/
  void CreateBiTree(BiTree &T) {
  //按先序次序输入二叉树中结点的值,创建二叉链表表示的二叉树 T
  TElemType ch;
  cin>>ch;
  if(ch == '#'){//递归结束,建空树
  T = NULL;
  } else {
  T = new BiTNode;
  T->data = ch;
  CreateBiTree(T->lchild);
  CreateBiTree(T->rchild);
  }  


}

/\*\*

- 先序遍历
  \*/
  void PreOrderTraverse(BiTree &T)
  {//先序遍历二叉树 T 的递归算法
  if(T) //若二叉树非空
  {
  cout << T->data << " "; //访问根结点
  PreOrderTraverse(T->lchild); //中序遍历左子树
  PreOrderTraverse(T->rchild); //中序遍历右子树
  }
  }

/\*\*

- 中序遍历
  \*/
  void InOrderTraverse(BiTree &T) {
  if (T) {
  InOrderTraverse(T->lchild);
  cout << T->data << " ";
  InOrderTraverse(T->rchild);
  }
  }

/\*\*

- 后序遍历
  \*/
  void PostOrderTraverse(BiTree &T)
  {//后序遍历二叉树 T 的递归算法
  if(T) //若二叉树非空
  {
  PostOrderTraverse(T->lchild); //中序遍历左子树
  PostOrderTraverse(T->rchild); //中序遍历右子树
  cout << T->data << " "; //访问根结点
  }
  }

/\*\*

- 统计二叉树中节点个数
  \*/
  int NodeCount (BiTree &T) {
  if (T == NULL) {
  return 0;
  } else {
  return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
  }
  }

/\*\*

- 二叉树中叶结点个数
  \*/
  int LeavesCount (BiTree &T) {
  if (T == NULL) {
  return 0;
  } else if (T->lchild == NULL && T->rchild == NULL) {
  return LeavesCount(T->lchild) + LeavesCount(T->rchild) + 1;
  }
  else {
  return LeavesCount(T->lchild) + LeavesCount(T->rchild);
  }
  }

int main() {
BiTree test = new BiTNode;
cout << "请输入一个字符串以生成二叉树:";
CreateBiTree(test);
cout <<"\n"<< "先序遍历结果:";
PreOrderTraverse(test);
cout <<"\n"<< "中序遍历结果:";
InOrderTraverse(test);
cout <<"\n"<< "后序遍历结果:";
PostOrderTraverse(test);
cout <<"\n"<< "二叉树结点个数:"<<NodeCount(test);
cout <<"\n"<< "二叉树叶结点个数:"<<LeavesCount(test);
}

DFS 遍历算法

DFS 遍历分三种情况:先序、中序、后序

把一颗树遍历完,有下面三种方法:

  • 波兰表达式 -> 先序遍历二叉树
  • 中缀表达式 -> 中序遍历二叉树
  • 逆波兰表达式 -> 后序遍历二叉树


手写例子


各种遍历结果

  • 先序:-+a*b-cd/ef
  • 中序:a+b*c-d-e/f
  • 后序:abcd-\*+ef/-


前序遍历

/\*\*

- Definition for a binary tree node.
- function TreeNode(val, left, right) {
-     this.val = (val===undefined ? 0 : val)
-     this.left = (left===undefined ? null : left)
-     this.right = (right===undefined ? null : right)
- }
  \*/
  /\*\*
- @param {TreeNode} root
- @return {number[]}
  \*/
  var preorderTraversal = function(root) {
  let result = []
  let preorder = data => {
  if (data) {
  result.push(data.val)
  preorder(data.left)
  preorder(data.right)
  }
  }
  preorder(root)
  return result
  };

中序遍历

/\*\*
- Definition for a binary tree node.
- function TreeNode(val, left, right) {
-     this.val = (val===undefined ? 0 : val)
-     this.left = (left===undefined ? null : left)
-     this.right = (right===undefined ? null : right)
- }
  \*/
  /\*\*
- @param {TreeNode} root
- @return {number[]}
  \*/
  var inorderTraversal = function(root) {
  let result = []
  let inorder = data => {
  if (data) {
  inorder(data.left)
  result.push(data.val)
  inorder(data.right)
  }
  }
  inorder(root)
  return result
  };

后序遍历

/\*\*
- Definition for a binary tree node.
- function TreeNode(val, left, right) {
-     this.val = (val===undefined ? 0 : val)
-     this.left = (left===undefined ? null : left)
-     this.right = (right===undefined ? null : right)
- }
  \*/
  /\*\*
- @param {TreeNode} root
- @return {number[]}
  \*/
  var postorderTraversal = function(root) {
  let result = []
  let postorder = data => {
  if (data) {
  postorder(data.left)
  postorder(data.right)
  result.push(data.val)
  }
  }
  postorder(root)
  return result
  };

评论区

Twikoo giscus