#ifndef tree_H
#define tree_H
#include<iostream>
#include<string>
using namespace std;
template<class T>struct BiNode
{
T data;
BiNode<T>* lchild;
BiNode<T>* rchild;
};
template<class T>class BiTree
{
private:
void Create(BiNode<T>*& R);//创建二叉树
void Release(BiNode<T>* R);//释放二叉树
public:
BiNode<T>* root;//根节点
BiTree(BiNode<T>* R);//构造函数
void PreOrder(BiNode<T>* R);//前序遍历
void InOrder(BiNode<T>* R);//中序遍历
void PostOrder(BiNode<T>* R);//后序遍历
void LevelOrder(BiNode<T>* R);//层序遍历
int TreeDepth(BiNode<T>* R);//二叉树深度
bool Path(BiNode<T>* R, T S);//指定结点路径
~BiTree();//析构函数
};
template<class T>
void BiTree<T>::Create(BiNode<T>*& R)//顺序存储结构为输入创建二叉树,先建立根节点,再建立左右孩子的递归算法
{
char ch;
cin >> ch;
if (ch == '#')
R = NULL;
else
{
R = new BiNode<T>;
R->data = ch;
Create(R->lchild); //建立左孩子
Create(R->rchild);
}
}
template<class T>
void BiTree<T>::Release(BiNode<T>* R)//释放所有结点,左右子树释放完毕后再释放该结点
{
if (R != NULL)
{
Release(R->lchild);
Release(R->rchild);
delete R;
}
}
template<class T>
BiTree<T>::BiTree(BiNode<T>* R)
{
Create(root);
}
template<class T>
void BiTree<T>::PreOrder(BiNode<T>* R)//前序遍历,先访问根结点再访问左右结点
{
if (R != NULL)
{
cout << R->data;
PreOrder(R->lchild);
PreOrder(R->rchild);
}
}
template<class T>
void BiTree<T>::InOrder(BiNode<T>* R)//中序遍历,先访问左子树,再访问根结点,最后访问右子树
{
InOrder(R->lchild);
cout << R->data;
InOrder(R->rchild);
}
template<class T>
void BiTree<T>::PostOrder(BiNode<T>* R)//后序遍历,先访问左右结点,再访问根结点
{
PostOrder(R->lchild);
PostOrder(R->rchild);
cout << R->data;
}
template<class T>
void BiTree<T>::LevelOrder(BiNode<T>* R)//先访问一层的结点,再依次访问左右子树,利用队列来实现
{
BiNode<T>* queue[100];
int f = 0, r = 0;
if (R != NULL)
queue[++r] = R;//根结点入队
while(f!=r)
{
BiNode<T>* p = queue[++f];
cout << p->data;//队头元素出队打印
if (p->lchild != NULL)
queue[++r] = p->lchild;//左孩子入队
if (p->rchild != NULL)
queue[++r] = p->rchild;//右孩子入队
}
}
template<class T>
int BiTree<T>::TreeDepth(BiNode<T>* R)//二叉树深度为左右子树 中深度大的加1,利用递归方法
{
if (R == NULL)
return 0;
int ldepth = TreeDepth(R->lchild);//左子树深度
int rdepth = TreeDepth(R->rchild);//右子树深度
int depth;
depth = ldepth > rdepth ? (ldepth + 1) : (rdepth + 1);
return depth;
}
template<class T>
bool BiTree<T>::Path(BiNode<T>* R, T S)
{
if (R == NULL)
return false;
else
{
if (R->data == S)
{
cout << R->data;
return true;
}
else if (Path(R->lchild, S))
{
cout << R->data;
return true;
}
else if (Path(R->rchild, S))
{
cout << R->rchild;
return true;
}
else
return false;
}
}
template<class T>
BiTree<T>::~BiTree()
{
Release(root);
}
#endif // !tree_H
#include<iostream>
#include<string>
#include"Bitree.h"
using namespace std;
int main() {
BiNode<char>* R = NULL;
char m;
BiTree<char> Test(R);
cout << "输出想要路径的结点值:";
cin >> m;
cout << "该二叉树的前序遍历为:" << endl;
Test.PreOrder(Test.root);
cout << endl;
cout << "该二叉树的中序遍历为:" << endl;
Test.InOrder(Test.root);
cout << endl;
cout << "该二叉树的后续遍历为:" << endl;
Test.PostOrder(Test.root);
cout << endl;
cout << "该二叉树的层序遍历为:" << endl;
Test.LevelOrder(Test.root);
cout << endl;
cout << "该二叉树的深度为:"; cout << Test.TreeDepth(Test.root);
cout << endl;
cout << "从根结点到该结点的路径为:";
Test.Path(Test.root, m);
cout << endl;
Test.~BiTree();
return 0;
}
这个是可以输出的, 你可以改为c++版
#include<stdio.h>
#include<stdlib.h>
/*定义树的结点结构*/
typedef struct TreeNode {
char data;/*树中结点的数据是一个字符*/
struct TreeNode* lchild;
struct TreeNode* rchild;
}TREENODE;
int NodeNum = 0;/*统计数的结点数*/
int LeafNum = 0;/*统计数的叶子结点数*/
char ch[] = { 'a', 'b', 'c', ' ', ' ', 'd', ' ', ' ', 'e', 'f', ' ', ' ', 'g', ' ', ' ' };
int inc = 0;
/*建立一颗二叉树*/
int CreateBiTree(TREENODE** T)
/*按先序次序输入二叉树中结点的值,以空字符表示空树*/
{
if (ch[inc++] == ' ')
*T = NULL;
else
{
printf("%c\n", ch[inc - 1]);
if (!(*T = (TREENODE*)malloc(sizeof(TREENODE))))
return -1;
(*T)->data = ch[inc - 1];
printf("%c\n", (*T)->data);
CreateBiTree(&((*T)->lchild));
CreateBiTree(&((*T)->rchild));
}
return 1;
}
/*先序遍历二叉树*/
int PreOderTraverse(TREENODE* T)
{
if (T)
{
printf("%c ", T->data);
PreOderTraverse(T->lchild);
PreOderTraverse(T->rchild);
}
return 1;
}
/* 中序遍历二叉树*/
int InOderTraverse(TREENODE* T)
{
if (T)
{
InOderTraverse(T->lchild);
printf("%c ", T->data);
InOderTraverse(T->rchild);
}
return 1;
}
/* 后序遍历二叉树*/
int BackOderTraverse(TREENODE* T)
{
if (T)
{
BackOderTraverse(T->lchild);
BackOderTraverse(T->rchild);
printf("%c ", T->data);
}
return 1;
}
/*利用先序遍历来计算树中的结点数*/
void CountNodeNum(TREENODE* T)
{
if (T)
{
NodeNum++;
CountNodeNum(T->lchild);
CountNodeNum(T->rchild);
}
}
/*利用先序遍历计算叶子节点数*/
void CountLeafNum(TREENODE* T)
{
if (T)
{
if ((!(T->lchild)) && (!(T->rchild)))
LeafNum++;
CountLeafNum(T->lchild);
CountLeafNum(T->rchild);
}
}
int main()
{
TREENODE* T;
int i;
CreateBiTree(&T);
do
{
puts("**************************************************");
puts("* 你可以选择: *");
puts("* 1: 按预定顺序遍历二叉树 *");
puts("* 2: 按中序遍历二叉树 *");
puts("* 3: 通过回溯顺序遍历二叉树 *");
puts("* 4: 计算二叉树的节点数 *");
puts("* 5: 计算二叉树的叶子节点数 *");
puts("**************************************************");
puts("请输入您的选择:");
scanf_s("%d", &i);
switch (i)
{
case 1:
PreOderTraverse(T);
break;
case 2:
InOderTraverse(T);
break;
case 3:
BackOderTraverse(T);
break;
case 4:
CountNodeNum(T);
printf("节点数: %d", NodeNum);
break;
case 5:
CountLeafNum(T);
printf("叶子节点数: %d", LeafNum);
break;
}
} while ((i >= 1) && (i < 6));
return 0;
}