-
编程语言
站-
热门城市 全国站>
-
其他省市
-
-
400-636-0069
小标
2018-07-20
来源 ：
阅读 1223
评论 0
摘要：本文主要向大家介绍了C++语言二叉树的各种操作，通过具体的内容向大家展示，希望对大家学习C++语言有所帮助。
本文主要向大家介绍了C++语言二叉树的各种操作，通过具体的内容向大家展示，希望对大家学习C++语言有所帮助。
头文件
#ifndef _BINARYTREE_H_
#define _BINARYTREE_H_
const int MaxSize = 100;
template<class t="">
struct BTNode
{
T data;
BTNode<t> *lchild;
BTNode<t> *rchild;
};
template<class t="">
class BinaryTree
{
public:
BinaryTree(); //构造函数
~BinaryTree(); //析构函数
void PreOrder(){PreOrder(r);} //递归前序遍历
void InOrder(){InOrder(r);} //递归中序遍历
void PostOrder(){PostOrder1(r);} //递归后序遍历
void PreOrder1(){PreOrder1(r);} //非递归前序遍历
void InOrder1(){InOrder1(r);} //非递归中序遍历
void PostOrder1(){PostOrder(r);} //非递归后序遍历
void LevelOrder(){LevelOrder(r);}//层序遍历
BTNode<t>* FindNode(T x){FindNode(r,x);}//查找结点
int BTNodeHeigth(){BTNodeHeigth(r);}//树的高度
int NodeCount1(){NodeCount1(r);} //基于前序遍历求结点个数
int NodeCount2(){NodeCount2(r);} //基于中序遍历求结点个数
int NodeCount3(){NodeCount3(r);} //基于后序遍历求结点个数
int NodeCount4(){NodeCount4(r);} //递归求结点个数
void DispLeaf(){DispLeaf(r);} //输出树的叶子结点
void printRouteLength(){printLeavesDepth(r, 0);}//输出树的叶子结点到根结点的路径长度
bool printAncestor(T x){printAncestor(r,x);} //输出值为x的结点的祖先结点
private:
BTNode<t> *r;
BTNode<t>* CreateTree(BTNode<t> *t);//构造函数调用
void DestroyTree(BTNode<t> *t); //析构函数调用
void PreOrder(BTNode<t> *t); //递归前序遍历调用
void InOrder(BTNode<t> *t); //递归中序遍历调用
void PostOrder(BTNode<t> *t); //递归后序遍历调用
void PreOrder1(BTNode<t> *t); //非递归前序遍历调用
void InOrder1(BTNode<t> *t); //非递归中序遍历调用
void PostOrder1(BTNode<t> *t); //非递归后序遍历调用
void LevelOrder(BTNode<t> *t); //层序遍历调用
BTNode<t>* FindNode(BTNode<t> *t, T x);
int BTNodeHeigth(BTNode<t> *t);
int NodeCount1(BTNode<t> *t); //前序遍历求结点个数调用
int NodeCount2(BTNode<t> *t); //中序遍历求结点个数调用
int NodeCount3(BTNode<t> *t); //后序遍历求结点个数调用
int NodeCount4(BTNode<t> *t); //递归求结点个数调用
void DispLeaf(BTNode<t> *t);
void printLeavesDepth(BTNode<t> *t,int depth);
bool printAncestor(BTNode<t> *t,T x);
};
//
template<class t="">
BinaryTree<t>::BinaryTree()
{
r = CreateTree(r);
}
//
template<class t="">
BinaryTree<t>::~BinaryTree()
{
DestroyTree(r);
}
//
template<class t="">
void BinaryTree<t>::DestroyTree(BTNode<t> *t)
{
if(t != NULL)
{
DestroyTree(t->lchild);
DestroyTree(t->rchild);
delete t;
}
}
//
template<class t="">
BTNode<t>* BinaryTree<t>::CreateTree(BTNode<t> *t)
{
T ch;
std::cin>>ch;
if(ch == '#')
{
t = NULL;
}
else
{
t = new BTNode<t>;
t->data = ch;
t->lchild = CreateTree(t->lchild);
t->rchild = CreateTree(t->rchild);
}
return t;
}
//
template<class t="">
void BinaryTree<t>::PreOrder(BTNode<t> *t)
{
if(t != NULL)
{
std::cout<<t->data<<" ";
PreOrder(t->lchild);
PreOrder(t->rchild);
}
}
//
template<class t="">
void BinaryTree<t>::InOrder(BTNode<t> *t)
{
if(t != NULL)
{
InOrder(t->lchild);
std::cout<<t->data<<" ";
InOrder(t->rchild);
}
}
//
template<class t="">
void BinaryTree<t>::PostOrder(BTNode<t> *t)
{
if(t != NULL)
{
PostOrder(t->lchild);
PostOrder(t->rchild);
std::cout<<t->data<<" ";
}
}
//
template<class t="">
BTNode<t>* BinaryTree<t>::FindNode(BTNode<t> *t,T x)
{
BTNode<t> *p;
if(t == NULL)
{
return NULL;
}
else if(t->data == x)
{
return t;
}
else
{
p = FindNode(t->lchild,x);
if(p != NULL)
{
return p;
}
return FindNode(t->rchild,x);
}
}
//
template<class t="">
int BinaryTree<t>::BTNodeHeigth(BTNode<t> *t)
{
int lchildh,rchildh;
if(t == NULL)
{
return 0;
}
else
{
lchildh = BTNodeHeigth(t->lchild);
rchildh = BTNodeHeigth(t->rchild);
return (lchildh > rchildh)?(lchildh + 1):(rchildh + 1);
}
}
//
template<class t="">
int BinaryTree<t>::NodeCount4(BTNode<t> *t)
{
if(t == NULL)
{
return 0;
}
else
{
return (NodeCount4(t->lchild) + NodeCount4(t->rchild) + 1);
}
}
//
template<class t="">
int BinaryTree<t>::NodeCount1(BTNode<t> *t)
{
int m,n,k;
if(t != NULL)
{
m = NodeCount1(t->lchild);
k = 1;
n = NodeCount1(t->rchild);
return m + n + k;
}
return 0;
}
//
template<class t="">
int BinaryTree<t>::NodeCount2(BTNode<t> *t)
{
int m,n,k;
if(t != NULL)
{
m = NodeCount2(t->lchild);
n = NodeCount2(t->rchild);
k = 1;
return m + n + k;
}
return 0;
}
//
template<class t="">
int BinaryTree<t>::NodeCount3(BTNode<t> *t)
{
int m,n,k;
if(t != NULL)
{
k = 1;
m = NodeCount3(t->lchild);
n = NodeCount3(t->rchild);
return m + n + k;
}
return 0;
}
//
template<class t="">
void BinaryTree<t>::DispLeaf(BTNode<t> *t)
{
if(t != NULL)
{
if((t->lchild == NULL)&&(t->rchild == NULL))
{
std::cout<<t->data<<" ";
}
DispLeaf(t->lchild);
DispLeaf(t->rchild);
}
}
//
template<class t="">
//输出路径长度
void BinaryTree<t>::printLeavesDepth(BTNode<t> *t, int depth)
{
if (t == NULL) return;
if (t->lchild == NULL && t->rchild == NULL)
{
std::cout<<t->data<<": "<<depth<<std::endl; else="" t-="">lchild, depth+1);
printLeavesDepth(t->rchild, depth+1);
}
}
//
template<class t="">
bool BinaryTree<t>::printAncestor(BTNode<t> *t, T x)
{
if(t == NULL)
{
return false;
}
if((t->lchild != NULL)&&(t->lchild->data == x))
{
std::cout<<t->data<<" ";
return true;
}
if((t->rchild != NULL)&&(t->rchild->data == x))
{
std::cout<<t->data<<" ";
return true;
}
if((printAncestor(t->lchild,x))||(printAncestor(t->rchild,x)))
{
std::cout<<t->data<<" ";
return true;
}
return false;
}
//
template<class t="">
void BinaryTree<t>::PreOrder1(BTNode<t> *t)
{
BTNode<t> *st[MaxSize];
int top = -1;
BTNode<t> *p;
top++;
st[top] = t; //将根结点入栈
while(top != -1) //栈非空
{
p = st[top];
top--;
std::cout<<p->data<<" ";
if(p->rchild != NULL) //右孩子先进栈
{
top++;
st[top] = p->rchild;
}
if(p->lchild != NULL) //左孩子再进栈
{
top++;
st[top] = p->lchild;
}
}
}
//中序遍历非递归算法
template<class t="">
void BinaryTree<t>::InOrder1(BTNode<t> *t)
{
BTNode<t> *st[MaxSize];
BTNode<t> *p;
int top = -1;
p = t;
while((top != -1)||(p!=NULL)) //栈不空或p不为空时
{
while(p != NULL) //扫描所有左结点并进栈
{
top++;
st[top] = p;
p = p->lchild;
}
if(top > -1) //若栈不为空
{
p = st[top];
top--;
std::cout<<p->data<<" ";
p = p->rchild; //转向处理右子树
}
}
}
//
template<class t="">
void BinaryTree<t>::PostOrder1(BTNode<t> *t)
{
BTNode<t> *st[MaxSize],*p,*q;
p = t;
int top = -1;
bool flag;
do
{
while(p != NULL) //将p结点及所有的左下结点进栈
{
top++;
st[top] = p;
p = p->lchild;
}
q = NULL; //q指向栈顶结点的前一个已经访问的结点
flag =true; //表示p结点的左子树已经遍历完
while((top != -1)&&(flag == true))//若p结点及其右子树已访问或为空
{
p = st[top];
if(p->rchild == q)
{
std::cout<<q->data<<" ";
top--;
q = p;
}
else
{
p = p->rchild;
flag = false;
}
}
}
while(top != -1);
}
//
template<class t="">
void BinaryTree<t>::LevelOrder(BTNode<t> *t)
{
BTNode<t> *qu[MaxSize],*p;
int front = 0, rear = 0;
rear++;
qu[rear] = t;
while(front != rear) //队列不为空
{
front = (front + 1) % MaxSize;
p = qu[front];
std::cout<<p->data<<" ";
if(p->lchild != NULL)
{
rear = (rear + 1) % MaxSize;
qu[rear] = p->lchild;
}
if(p->rchild != NULL)
{
rear = (rear + 1) % MaxSize;
qu[rear] = p->rchild;
}
}
}
#endif // _BINARYREE_H_
</p-></t></t></t></class></q-></t></t></t></class></p-></t></t></t></t></class></p-></t></t></t></t></class></t-></t-></t-></t></t></class></depth<<std::endl;></t-></t></t></class></t-></t></t></class></t></t></class></t></t></class></t></t></class></t></t></class></t></t></class></t></t></t></t></class></t-></t></t></class></t-></t></t></class></t-></t></t></class></t></t></t></t></class></t></t></class></t></class></t></class></t></t></t></t></t></t></t></t></t></t></t></t></t></t></t></t></t></t></t></t></t></t></class></t></t></class>
源文件
#include <iostream>
#include "BinaryTree.h"
using namespace std;
int main()
{
BinaryTree<char> a;
cout<<"前序遍历： ";
a.PreOrder();
cout<<endl; :="" pre="" return=""><p> </p>
</endl;></char></iostream>
以上就介绍了C/C+的相关知识，希望对C/C+有兴趣的朋友有所帮助。了解更多内容，请关注职坐标编程语言C/C+频道！
喜欢 | 1
不喜欢 | 0
您输入的评论内容中包含违禁敏感词
我知道了
请输入正确的手机号码
请输入正确的验证码
您今天的短信下发次数太多了，明天再试试吧！
我们会在第一时间安排职业规划师联系您！
您也可以联系我们的职业规划师咨询：
版权所有 职坐标-一站式IT培训就业服务领导者 沪ICP备13042190号-4
上海海同信息科技有限公司 Copyright ©2015 www.zhizuobiao.com，All Rights Reserved.
沪公网安备 31011502005948号
索取资料
答疑解惑
技术交流
职业测评
面试技巧
高薪秘笈
