2013年宁夏回族自治区C++语言版要领_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
2013年宁夏回族自治区C++语言版要领
&&2013年宁夏回族自治区C++语言版要领
你可能喜欢基于C++类和指针实现二叉树
1、二叉树的定义
　　二叉树（Binary Tree）是一种特殊的树型结构，每个节点至多有两棵子树，且二叉树的子树有左右之分，次序不能颠倒。
　　由定义可知，二叉树中不存在度（结点拥有的子树数目）大于2的节点。二叉树形状如下下图所示：
2、二叉树的性质vc3Ryb25nPjwvcD4KPHA+o6gxo6nU2rb+subK99bQtcS12mmy48nP1sG24NPQMl4oaS0xKbj2veG146OoaT49MSmho7G416I6XrHtyr60y7e9PC9wPgo8cD6jqDKjqcnutsjOqmu1xLb+subK99bBtuDT0DJeay0xuPa92rXjo6hrPj0xKaGjPC9wPgo8cD6jqDOjqbbUyM66ztK7v8O2/rLmyvdUo6zI57n7xuTW1bbLveG148r9xL/Oqm4wo6y2yM6qMrXEvdq148r9xL/Oqm4yo6zU8m4wPW4yJiM0MzsxoaM8L3A+CjxwPjxzdHJvbmc+wvq2/rLmyvejusnutsjOqmvH0r7f09AyXmstMbj2veG147XEtv6y5sr3oaO8tML6tv6y5sr31tC1xMO/0ruy48nPtcS94bXjyv22vMrH1+6087XEveG148r9oaM8L3N0cm9uZz48L3A+CjxwPjxzdHJvbmc+zerIq7b+subK96O6ye62yM6qa77f09BuuPa94bXjtcS2/rLmyvejrLWxx9K99rWxw7/Su7j2veG149Prye62yM6qa7XEwvq2/rLmyvfW0LXEseC6xbTTMdbBbrXEveG149K70ru21NOmoaM8L3N0cm9uZz48L3A+CjxwPr/J0tS1w7W90ruw473hwtujusL6tv6y5sr3us3N6sirtv6y5sr3ysfBvdbWzNjK4tDOzKy1xLb+subK96Oswvq2/rLmyve/z7aoysfN6sirtv6y5sr3o6y1q83qyKu2/rLmyveyu7K70ru2qMrHwvq2/rLmyvehozwvcD4KPHA+vtnA/cjnz8LNvMrHy/nKvqO6PC9wPgo8cD48aW1nIHNyYz0="/Collfiles/01.png" alt="\">
（4）具有n个节点的完全二叉树的深度为log2n + 1。
3、二叉树的存储结构
　　可以采用顺序存储数组和链式存储二叉链表两种方法来存储二叉树。经常使用的二叉链表方法，因为其非常灵活，方便二叉树的操作。二叉树的二叉链表存储结构如下所示：
1 typedef struct binary_tree_node
struct binary_tree_node *
struct binary_tree_node *
6 }binary_tree_node,*binary_
举例说明二叉链表存储过程，如下图所示：
从图中可以看出：在还有n个结点的二叉链表中有n+1个空链域。
4、遍历二叉树
　　遍历二叉树是按照指定的路径方式访问书中每个结点一次，且仅访问一次。由二叉树的定义，我们知道二叉数是由根结点、左子树和右子树三部分构成的。通常遍历二叉树是从左向右进行，因此可以得到如下最基本的三种遍历方法：
（1）先根遍历（先序遍历）：如果二叉树为空，进行空操作；否则，先访问根节点，然后先根遍历左子树，最后先根遍历右子树。采用递归形式实现代码如下：
1 void preorder_traverse_recursive(binary_tree root)
if(NULL != root)
printf("%d\t",root->elem);
preorder_traverse_recursive(root->left);
preorder_traverse_recursive(root->right);
具体过程如下图所示：
（2）中根遍历（中序遍历）：如果二叉树为空，进行空操作；否则，先中根遍历左子树，然后访问根结点，最后中根遍历右子树。递归过程实现代码如下：
1 void inorder_traverse_recursive(binary_tree root)
if(NULL != root)
inorder_traverse_recursive(root->left);
printf("%d\t",root->elem);
inorder_traverse_recursive(root->right);
具体过程如下图所示：
（3）后根遍历（后序遍历）：如果二叉树为空，进行空操作；否则，先后根遍历左子树，然后后根遍历右子树，最后访问根结点。递归实现代码如下：
1 void postorder_traverse_recursive(binary_tree root)
if(NULL != root)
postorder_traverse_recursive(root->left);
postorder_traverse_recursive(root->right);
printf("%d\t",root->elem);
具体过程如下图所示：
用类和指针实现的二叉树：
struct tree
tree *left,*
class Btree
root=NULL;
void create_Btree(int);
void Preorder(tree *);
//先序遍历
void inorder(tree *);
//中序遍历
void Postorder(tree *);
//后序遍历
void display1() {Preorder(root); cout<<}
void display2() {inorder(root);cout<<}
void display3() {Postorder(root); cout<data=x;
newnode->right=newnode->left=NULL;
if(root==NULL)
tree *current=
while(current!=NULL)
if(current->data>x)
current=current->
current=current->
if(back->data>x)
back->left=
back->right=
int Btree::count(tree *p)
if(p==NULL)
return count(p->left)+count(p->right)+1;
//这是运用了函数嵌套即递归的方法。
void Btree::Preorder(tree *temp)
//这是先序遍历二叉树，采用了递归的方法。
if(temp!=NULL)
cout<data<left);
Preorder(temp->right);
void Btree::inorder(tree *temp)
//这是中序遍历二叉树，采用了递归的方法。
if(temp!=NULL)
inorder(temp->left);
cout<data<right);
void Btree::Postorder(tree *temp)
//这是后序遍历二叉树，采用了递归的方法。
if(temp!=NULL)
Postorder(temp->left);
Postorder(temp->right);
cout<data<left==NULL&&temp->right==NULL)return n+=1;
findleaf(temp->left);
findleaf(temp->right);
int Btree::findnode(tree *temp)
if(temp==NULL)return 0;
if(temp->left!=NULL&&temp->right!=NULL)
findnode(temp->left);
findnode(temp->right);
if(temp->left!=NULL&&temp->right==NULL)
findnode(temp->left);
if(temp->left==NULL&&temp->right!=NULL)
findnode(temp->right);
void main()
int array[]={100,4,2,3,15,35,6,45,55,20,1,14,56,57,58};
k=sizeof(array)/sizeof(array[0]);
cout<<"建立排序二叉树顺序: "<<
for(int i=0;i<k;i++)
cout<<array[i]<<" ";
A.create_Btree(array[i]);
cout<<"二叉树节点个数： "<<A.count(A.root)<<
cout<<"二叉树叶子个数："<<A.findleaf(A.root)<<
cout<<"二叉树中度数为1的结点的数量为："<<A.findnode(A.root)<<
cout<<endl<<"先序遍历序列: "<<
A.display1();
cout<<endl<<"中序遍历序列: "<<
A.display2();
cout<<endl<<"后序遍历序列: "<<
A.display3();用二叉链表实现二叉查找树(二)
二叉查找树的链表实现：
以及三种遍历方式,删除节点；
查找节点；
author:天下无双
Version:3.0
typedef int T;//树内节点的数据类型
class BiTree
struct BiNode{
BiNode *lchild,*
BiNode(T d){
//root=root->rchild=root->rchild=
~BiTree(){
//使用递归创建二叉树
//以二叉排序树的规则建立
//指针的引用写法（推荐使用）
bool addBiNode(BiNode *&nodeRoot,T d){
if(nodeRoot==nullptr){
BiNode *p=new BiNode(d);
nodeRoot=p;
cout<data<<"
insert success!"<<
}else if(nodeRoot!=nullptr&&ddata){
//往左子树递归
addBiNode(nodeRoot->lchild,d);
}else if(nodeRoot!=nullptr&&d>(nodeRoot)->data){
//往右子树递归
addBiNode(nodeRoot->rchild,d);
cout<<"树中已有该数据"<<
BiNode *&getRoot(){//返回根指针的引用
BiNode *getPtrToRoot()const{
bool Traverse(const BiNode *b,string type)const{
if(type=="PreOrderTraverse"){
cout<<"\n先序遍历的结果为:"<<
PreOrderTraverse(b);
}else if(type=="InOrderTraverse"){
cout<<"\n中序遍历的结果为:"<<
InOrderTraverse(b);
}else if(type=="PostOrderTraverse"){
cout<<"\n后序遍历的结果为:"<<
PostOrderTraverse(b);
cout<<"遍历类型无效!"<data==d){
}else if(nodeRoot->datarchild,d);
Search(nodeRoot->lchild,d);
//递归查找确定该节点所在位置
bool DeleteBST(BiNode *&nodeRoot,T d){
if(nullptr==nodeRoot)//当该节点为空
if(nodeRoot->data==d){//
return Delete(nodeRoot);
//Delete(nodeRoot);
}else if(nodeRoot->datarchild,d);
//DeleteBST(nodeRoot->rchild,d);
return DeleteBST(nodeRoot->lchild,d);
//DeleteBST(nodeRoot->lchild,d);
protected:
//删除操作
//删除相应节点
//如果该节点是叶子节点，即该节点左右孩子均为空，则只需将父节点指向该节点
//指针置空即可
//如果仅有左孩子或者仅有右孩子，则将对应节点上移
//nodeRoot为要删除的节点
//若既有左孩子，又有右孩子，看下面的注释
bool Delete(BiNode *&nodeRoot){
//如果要删除的节点右子树为空，则只需移动左子树
if(nullptr==nodeRoot->rchild){
BiNode *temp=nodeR
nodeRoot=nodeRoot->
}else if(nullptr==nodeRoot->lchild){//若左子树空则移动右子树
BiNode *temp=nodeR
nodeRoot=nodeRoot->
}else{//左右子树均非空
//将该节点的左子树的最右边的右节点数据和该节点互换
//或者是将该节点右子树最左端的左节点和该节点数据互换
//我这里是选择左子树的最右节点
BiNode *temp=nodeRoot->//temp为该节点左子树的根节点
BiNode *preTemp=nodeRoot->
while(nullptr!=temp->rchild){
preTemp=//令preTemp指向最右节点的前驱
temp=temp->//一直寻找最右的右节点
//temp指向待删除的节点
//这时候temp指向最右的一个节点
nodeRoot->data=temp->//交换数据，由于二叉查找树的特性，交换后依旧保持该特性。
倘若删除的是50，则preTemp=temp=&30
if(temp!=preTemp)
preTemp->rchild=temp->//令前驱节点的右孩子变成被删除节点的左孩子
nodeRoot->lchild=temp->
//删除右节点
//T如果是结构或者类类型，需重载<<运算符
void Visit(const BiNode *r)const{
cout<data<lchild!=nullptr)
PreOrderTraverse(nodeRoot->lchild);
if(nodeRoot->rchild!=nullptr)
PreOrderTraverse(nodeRoot->rchild);
//中根遍历
void InOrderTraverse(const BiNode *nodeRoot)const{
if(nodeRoot->lchild!=nullptr)
InOrderTraverse(nodeRoot->lchild);
if(nodeRoot!=nullptr)//当该点左子树空时
Visit(nodeRoot);
if(nodeRoot->rchild!=nullptr)
InOrderTraverse(nodeRoot->rchild);
//后序遍历
void PostOrderTraverse(const BiNode *nodeRoot)const{
if(nodeRoot->lchild!=nullptr)
PostOrderTraverse(nodeRoot->lchild);
if(nodeRoot->rchild!=nullptr)
PostOrderTraverse(nodeRoot->rchild);
if(nodeRoot!=nullptr)
Visit(nodeRoot);
感觉对于递归中的return还是有点不太清晰。什么时候该用，什么时候不该用也不太清晰。测试代码#include "bit4.cpp"
int main()
//b.addBiNode(&b.root,50);//设立根节点值//二级指针写法
b.addBiNode(b.getRoot(),50);//指针的引用写法
int arr[9]={30,40,35,27,100,90,110,95,-999};
for(int j=0;j<9;j++)
if(i==-999)
b.addBiNode(b.getRoot(),i);
b.Traverse(b.getPtrToRoot(),"PreOrderTraverse");
b.Traverse(b.getPtrToRoot(),"InOrderTraverse");
b.Traverse(b.getPtrToRoot(),"PostOrderTraverse");
while(true)
cout<<"\n输入要查找的值:"<>k;
if(b.Search(b.getRoot(),k))
cout<<"OK"<<
cout<<"NO"<<
cin.get();
system("pause");