当前位置:首页 » 《随便一记》 » 正文

使用C++创建二叉树和其基本操作

23 人参与  2023年04月05日 09:24  分类 : 《随便一记》  评论

点击全文阅读


目录

1.创建二叉树节点

2.使用前序遍历创建二叉树

3.遍历二叉树 

3.1 前序遍历二叉树

3.2 中序遍历二叉树

3.3 后序遍历二叉树

4. 二叉树是否为空

5. 求二叉树的节点数

6.求二叉树的深度

完整代码

运行测试用例及截图


1.创建二叉树节点

typedef struct TreeNode {char data;//数据域TreeNode* Lchild;//左孩子TreeNode* Rchild;//右孩子}*Tree, TreeNode;

2.使用前序遍历创建二叉树

void CreateTree(Tree& T) {char x;cin >> x;if (x =='*') {T = NULL; return;}else {T = new TreeNode;T->data = x;CreateTree(T->Lchild);CreateTree(T->Rchild);}}

3.遍历二叉树 

3.1 前序遍历二叉树

void Pre_Traversal(const Tree& T) {if (T) {cout << T->data<<" ";Pre_Traversal(T->Lchild);Pre_Traversal(T->Rchild);}}

3.2 中序遍历二叉树

void Ino_Traversal(const Tree& T) {if (T) {Ino_Traversal(T->Lchild);cout << T->data<<" ";Ino_Traversal(T->Rchild);}}

3.3 后序遍历二叉树

void Pos_Traversal(const Tree& T) {if (T) {Pos_Traversal(T->Lchild);Pos_Traversal(T->Rchild);cout << T->data << " ";}}

4. 二叉树是否为空

bool TreeEmpty(const Tree& T) {if (T == NULL){cout << "该二叉树为空!"<<endl; return true;}else{cout << "该二叉树为不为空!"<<endl;return false;}}

5. 求二叉树的节点数

int TreeNodeCount(const Tree& T) {if (T == NULL)return 0;else if (T->Lchild == NULL && T->Rchild == NULL)return 1;elsereturn TreeNodeCount(T->Lchild) + TreeNodeCount(T->Rchild)+1;}

6.求二叉树的深度

int TreeDepth(const Tree& T) {if (T == NULL) return 0;else {int i = TreeDepth(T->Lchild);int j = TreeDepth(T->Rchild);return i > j ? i + 1 : j + 1;}}

完整代码

#include<iostream>using namespace std;typedef struct TreeNode {char data;//数据域TreeNode* Lchild;//左孩子TreeNode* Rchild;//右孩子}*Tree, TreeNode;//前序创建二叉树void CreateTree(Tree& T) {char x;cin >> x;if (x =='*') {T = NULL; return;}else {T = new TreeNode;T->data = x;CreateTree(T->Lchild);CreateTree(T->Rchild);}}//先序遍历void Pre_Traversal(const Tree& T) {if (T) {cout << T->data<<" ";Pre_Traversal(T->Lchild);Pre_Traversal(T->Rchild);}}//中序遍历void Ino_Traversal(const Tree& T) {if (T) {Ino_Traversal(T->Lchild);cout << T->data<<" ";Ino_Traversal(T->Rchild);}}//后序遍历void Pos_Traversal(const Tree& T) {if (T) {Pos_Traversal(T->Lchild);Pos_Traversal(T->Rchild);cout << T->data << " ";}}//二叉树是否为空bool TreeEmpty(const Tree& T) {if (T == NULL){cout << "该二叉树为空!"<<endl; return true;}else{cout << "该二叉树为不为空!"<<endl;return false;}}//求二叉树的节点数int TreeNodeCount(const Tree& T) {if (T == NULL)return 0;else if (T->Lchild == NULL && T->Rchild == NULL)return 1;elsereturn TreeNodeCount(T->Lchild) + TreeNodeCount(T->Rchild)+1;}//求二叉树的深度int TreeDepth(const Tree& T) {if (T == NULL) return 0;else {int i = TreeDepth(T->Lchild);int j = TreeDepth(T->Rchild);return i > j ? i + 1 : j + 1;}}int main(){Tree T;cout << "请按先序遍历的顺序创建二叉树,若其节点的左孩子或右孩子不存在则使用*代替!如:(ABD**E**CF**G**)" << endl;CreateTree(T);TreeEmpty(T);cout << "先序遍历的结果为:";Pre_Traversal(T) ;cout<< endl;cout << "中序遍历的结果为:";Ino_Traversal(T);cout << endl;cout << "后序遍历的结果为:";Pos_Traversal(T);cout << endl;cout << "该树的深度为:"<< TreeDepth(T)<< endl;cout << "该树的节点数为:" << TreeNodeCount(T) << endl;system("pause");}

运行测试用例及截图

下图为测试用例: (ABD**E**CF**G**)

                        ​​​​​​​

前序遍历:A B D E C F G

中序遍历:D B E A F C G

后序遍历:D E B F G C A

总节点数 :7

树的深度:3 

运行截图如下:


点击全文阅读


本文链接:http://zhangshiyu.com/post/58378.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 此后锦书休寄周窈音全文最新章节(周窈音)全文免费阅读无弹窗大结局_周窈音免费阅读
  • 弹幕说我是捞女?反手收购男主公司养鸡(林朝曦沈墨川)_弹幕说我是捞女?反手收购男主公司养鸡
  • 没给寡嫂抢到La******,老公把我和儿子做成蜡像(顾云州沈云烟)_没给寡嫂抢到La******,老公把我和儿子做成蜡像顾云州沈云烟
  • 出狱后,假千金靠玄术杀疯了(顾九音霍霆修)_出狱后,假千金靠玄术杀疯了
  • 养妹偷我认亲玉佩当上千金,男友当场分手超长版_玉佩陈雨柔养父母一口气看完_小说后续在线阅读_无删减免费完结_
  • 抽卡后,气运之子怎么都缠上来了小说(夏挽棠)(抽卡后,气运之子怎么都缠上来了)全书+后续+结局在线阅读
  • 前传爱意随风消逝续集:全文+番外乔清浅宋轻舟:结局+番外新上热文
  • 宋昭黎陆铭绪(假如从没拥抱你)前文+全本完整阅读预售作品抢先看
  • 终章小说搬空海港!我携军舰嫁军官躺赢了完结篇(温婉历战)已更新+延伸(搬空海港!我携军舰嫁军官躺赢了)清爽版
  • 贵妻在上:废材老公来护航完结篇(贵妻在上:废材老公来护航)章节目录+章节前文(宋锦瑶霍少霆)全章无套路在线
  • 离婚后,前夫一家给我跪下了隐藏剧情_明白双宿双飞江城必读文_小说后续在线阅读_无删减免费完结_
  • 乔芊芊顾宴夜小说(乔芊芊顾宴夜)(踹了渣男后,禁欲大佬为我失控)前传+阅读全新作品预订

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1