![[数据结构(C语言版本)上机实验]二叉树实验](http://www.mshxw.com/aiimages/31/832564.png "[数据结构(C语言版本)上机实验]二叉树实验")
文章目录实现内容：
1、根据用户输入的扩展的先序遍历序列创建二叉树的二叉链表存储结构
2、编写二叉树的先序遍历、后序遍历、中序遍历算法
3、编写函数，求二叉树高度
4、编写函数，求二叉树中叶子节点的个数。
5、（选做）写一个函数LeftChild(T,e)或RightChild(T,e)，实现求二叉树T中某个非叶子结点e的左孩子或右孩子，若e无左孩子或右孩，则返回空；
6、（选做）写一个函数Parent(T,e)，实现求二叉树T中某个非根结点e的双亲，若e无双亲，则返回空
7、（选做）写一个函数LeftSibling(T,e)或RightSibling(T,e)，实现求二叉树T中某个结点e的左兄弟或右兄弟。
- 前言
- 一、实现效果（附：注意事项）
- 二、实验完整代码
- 1.简版（仅含二叉树的创建、先序遍历、中序遍历、后序遍历）
- 2.完整代码（深度+叶子节点个数+非线索找节点）
前言
提示：本实验环境为VS2019
二叉树的创建（先序遍历、中序遍历、后序遍历）+ 二叉树的高度 + 叶子节点的个数 + 选做
一、实现效果（附：注意事项）
创建二叉树：
！！！注意：输入的空格为某节点的左右子树为空（该节点为叶子节点）两个空格
（简单版）
该二叉树的高度和叶子节点的个数：
找某节点的关联节点【左（右）孩子、双亲、左（右）兄弟】
！！！scanf被跳过或不执行：缓冲区问题ヾ(≧▽≦*)o
引用：scanf被跳过或不执行
BiTree.h代码如下：
#include#include #include #define TElemType char typedef struct BiTNode { TElemType data; struct BiTNode* Lchild, * Rchild;//左右孩子指针 }BiTNode, * BiTree; void displayElem(BiTNode* elem) { printf("%c ", elem->data); } void CreateBiTree(BiTree& T) { char ch; scanf_s("%c", &ch); //getchar(); if (ch == ' ') T = NULL; else { if (!(T = (BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW); T->data = ch; CreateBiTree(T->Lchild);//构造左子树 CreateBiTree(T->Rchild);//构造右子树 } }//按照先序次序输入二叉树中结点的值,空格字符表示空树 //先序遍历 void PreOrderTraverse(BiTree T) { if (T) { displayElem(T); PreOrderTraverse(T->Lchild); PreOrderTraverse(T->Rchild); } } //中序遍历 void InOrderTraverse(BiTree T) { if (T) { InOrderTraverse(T->Lchild);//遍历左孩子 displayElem(T);//调用操作结点数据的函数方法 InOrderTraverse(T->Rchild);//遍历右孩子 } //如果结点为空，返回上一层 } //后序遍历 void PostOrderTraverse(BiTree T) { if (T) { PostOrderTraverse(T->Lchild);//遍历左孩子 PostOrderTraverse(T->Rchild);//遍历右孩子 displayElem(T);//调用操作结点数据的函数方法 } //如果结点为空，返回上一层 }
BinaryTree.cpp代码如下
#include"BiTree.h"
int main()
{
BiTree Tree;
printf("请按照先序输入，以创建二叉树: n");
CreateBiTree(Tree);
printf("先序遍历序列: n");
PreOrderTraverse(Tree);
printf("n");
printf("中序遍历序列: n");
InOrderTraverse(Tree);
printf("n");
printf("后序遍历序列: n");
PostOrderTraverse(Tree);
printf("n");
}
2.完整代码（深度+叶子节点个数+非线索找节点）
BiTree.h代码如下：
#pragma once #include#include #include #define TElemType char typedef struct BiTNode { TElemType data; struct BiTNode* Lchild, * Rchild;//左右孩子指针 }BiTNode, * BiTree; //显示输出元素 void displayElem(BiTNode* elem) { printf("%c", elem->data); } //按照先序遍历创建二叉树 void CreateBiTree(BiTree& T) { char ch; scanf_s("%c",&ch); //getchar(); if (ch == ' ') T = NULL; else { if (!(T = (BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW); T->data = ch; CreateBiTree(T->Lchild);//构造左子树 CreateBiTree(T->Rchild);//构造右子树 } }//按照先序次序输入二叉树中结点的值,空格字符表示空树 //先序遍历 void PreOrderTraverse(BiTree T) { if (T) { displayElem(T); PreOrderTraverse(T->Lchild); PreOrderTraverse(T->Rchild); } } //中序遍历 void InOrderTraverse(BiTree T) { if (T) { InOrderTraverse(T->Lchild);//遍历左孩子 displayElem(T);//调用操作结点数据的函数方法 InOrderTraverse(T->Rchild);//遍历右孩子 } //如果结点为空，返回上一层 } //后序遍历 void PostOrderTraverse(BiTree T) { if (T) { PostOrderTraverse(T->Lchild);//遍历左孩子 PostOrderTraverse(T->Rchild);//遍历右孩子 displayElem(T);//调用操作结点数据的函数方法 } //如果结点为空，返回上一层 } //叶子节点的个数 int CountLeaf(BiTree T) { if (!T) return 0; if ((!T->Lchild) && (!T->Rchild)) return 1; return(CountLeaf(T->Lchild) + CountLeaf(T->Rchild)); } //二叉树的高度 int Depth(BiTree T) { int depth, Left, Right; if (!T) depth = 0; else if ((!T->Lchild) && (!T->Rchild)) depth = 1; else { Left = Depth(T->Lchild); Right = Depth(T->Rchild); depth = 1 + (Left > Right ? Left : Right); } return depth; } //(选做)找[左]孩子 void LeftChild(BiTree T, TElemType e) { if (T) { if (T->data == e) { if (!T->Lchild) printf("%c 无左孩子n",e); if (T->Lchild) printf("%c 的左孩子为 %cn", e, T->Lchild->data); return; } LeftChild(T->Lchild, e); LeftChild(T->Rchild, e); } } //(选做)找双亲 void Parent(BiTree T, TElemType e) { if (T) { if ((T->Lchild && T->Lchild->data == e) || (T->Rchild && T->Rchild->data == e)) printf("%c 的双亲为 %cn", e, T->data); Parent(T->Lchild, e); Parent(T->Rchild, e); } } //(选做)找[左]兄弟 void LeftSibling(BiTree T, TElemType e) { if (T) { if (T->Rchild->data == e ) //当某结点的右孩子等于e时 { if (T->Lchild) //如果左孩子成立，则返回左孩子 printf("%c 的左兄弟为 %cn", e, T->Lchild->data); if (!T->Lchild) printf("%c 无左兄弟n", e); return; } LeftSibling(T->Lchild, e); LeftSibling(T->Rchild, e); } }
BinaryTree.cpp代码如下：
#include"BiTree.h"
void printInfo();
int main()
{
BiTree Tree;
printf("请按照先序输入，以创建二叉树: n");
CreateBiTree(Tree);//！！注意输入格式，如【AB C 】，空格表示无左右子树
int choice;
TElemType elem;
printInfo();
while (scanf_s("%d", &choice)) {
switch (choice) {
case 1:
printf("先序遍历序列: n");
PreOrderTraverse(Tree);
printf("n");
break;
case 2:
printf("中序遍历序列: n");
InOrderTraverse(Tree);
printf("n");
break;
case 3:
printf("后序遍历序列: n");
PostOrderTraverse(Tree);
printf("n");
break;
case 4:
printf("该二叉树的叶子节点的个数为：%dn", CountLeaf(Tree));
break;
case 5:
printf("该二叉树的高度为：%dn", Depth(Tree));
break;
case 6:
printf("请输入要查找的元素:");
getchar();//!!!注意此处的缓冲区，不加--之后的scanf会直接读入"n"
scanf_s("%c", &elem);
LeftChild(Tree, elem);
break;
case 7:
printf("请输入要查找的元素:");
getchar();
scanf_s("%c", &elem);
Parent(Tree, elem);
break;
case 8:
printf("请输入要查找的元素:");
getchar();
scanf_s("%c", &elem);
LeftSibling(Tree, elem);
break;
default:
exit(0);
}
printInfo();
}
}
void printInfo() {
printf("--1.输出先序遍历序列n");
printf("--2.输出中序遍历序列n");
printf("--3.输出后序遍历序列n");
printf("--4.输出二叉树的叶子节点的个数n");
printf("--5.输出二叉树的高度n");
printf("--6.查找某元素的左孩子n");
printf("--7.查找某元素的双亲n");
printf("--8.查找某元素的左兄弟n");
printf("--其他：退出程序n");
printf("**请输入接下来的操作:");
}
