hao3100590
- 浏览: 128631 次
- 性别:
- 来自: 成都
-
最新评论
-
yi_chao_jiang：
你好，多谢分享，问个问题，在上传数据的时候判断文件是否有上传记 ...
断点续传和下载原理分析 -
a41606709：
为什么我的tabhost显示不出来？ 怎么设置在全部页面中让他 ...
TabActivity中的Tab标签详细设置 -
Zero颴：
大神篇,思路,配图都很清晰,perfect!
Android事件模型之interceptTouchEvnet ,onTouchEvent关系正解 -
QAZ503602501：
牛死人了！！！
B-树 -
mengsina：
很牛的文档。数学功底好啊
Android Matrix理论与应用详解
1.二叉树的基本操作
这里我有一个疑问：
在使用构造函数的时候，传参数的问题？
开始我是这么理解的------只使用指针（其实指针本身就是一个地址，相当于引用，也会改变root建立起二叉树），而2指针的引用，相当于就是对记录了指针的地址，采用了二次引用，其实是没有必要的，一次就够了。但是实际上用的时候并不是这样？根本不能建立二叉树，原因是因为开始指针指向的是一个不确定的位置？然后我又实验了，分配空间先，但是还是不行？所以不知道为什么一定要使用双重指针或指针引用？不知哪位高人能解答之，谢谢了
就是这样void creatTree(Node<T>* root);
//声明类BiTree及定义结构BiNode,文件名为bitree.h
#ifndef BITREE_H
#define BITREE_H
template <class T>
struct Node //二叉树的结点结构
{
T data;
Node<T> *lchild, *rchild;
};
//定义队列或栈空间大小
const int SIZE = 100;
template <class T>
class BiTree
{
public:
BiTree( ); //构造函数，初始化一棵二叉树，其前序序列由键盘输入(输入序列是前序遍历顺序)
BiTree(T* a, int n); //构造函数，输入序列是层序序列（非递归建立）
~BiTree(); //析构函数，释放二叉链表中各结点的存储空间
Node<T>* getRoot(); //获得指向根结点的指针
void preOrder(Node<T> *root); //前序遍历二叉树
void inOrder(Node<T> *root); //中序遍历二叉树
void postOrder(Node<T> *root); //后序遍历二叉树
void leverOrder(Node<T> *root); //层序遍历二叉树
void nrPreOrder(Node<T> *root); //前序遍历二叉树(非递归)
void nrInOrder(Node<T> *root); //中序遍历二叉树(非递归)
void nrPostOrder(Node<T> *root); //后序遍历二叉树(非递归)
//基本操作
Node<T>* searchNode(T x); //寻找值为x的节点
int biTreeDepth(Node<T>* root); //二叉树深度
Node<T>* getParent(Node<T>* root, T x); //如果存在值为data的节点，返回其父节点
Node<T>* getLeftSibling(Node<T>* root, T x); //获取左兄弟
Node<T>* getRightSibling(Node<T>* root, T x); //获取右兄弟
int leafCount(Node<T>* root); //叶子个数
int nodeCount(Node<T>* root); //节点个数
void deleteSibTree(Node<T>* root, T x); //删除节点x为根节点的子树
private:
Node<T> *root; //指向根结点的头指针
//1.使用双指针（指向指针的地址，这样就不在是拷贝，相当于一个引用）
//void creatTree(Node<T> **root); //有参构造函数调用(根地址的地址,也可指针的引用)
//2.使用引用（别名，可以直接对root操作）
void creatTree(Node<T>* &root);
//3.使用返回
//Node<T>* creatTree();
//4.只使用指针（其实指针本身就是一个地址，相当于引用，也会改变root建立起二叉树）
//而2指针的引用，相当于就是对记录了指针的地址，采用了二次引用，其实是没有必要的，一次就够了
//但是实际上用的时候并不是这样？根本不能建立二叉树，原因是因为开始指针指向的是一个不确定的位置？
//然后我又实验了，分配空间先，但是还是不行？所以不知道为什么一定要使用双重指针或指针引用？不知哪位高人能解答之，谢谢了
//void creatTree(Node<T>* root);
void createTree(Node<T>* &root, T* a, int n);//非递归建立二叉树
void search(Node<T>* root, T x, Node<T>* &p); //搜索
void releaseTree(Node<T> *root); //析构函数调用
};
#endif
2.基本操作实现
#include <iostream>
#include "bitree.h"
using namespace std;
//构造函数，初始化一棵二叉树，其前序序列由键盘输入
template <class T>
BiTree<T>::BiTree( ){
//creatTree(&root); //1.双指针（指向指针的地址，故而使用取地址操作符，取出指针root的地址）
creatTree(root); //2.root的引用
//root = creatTree(); //3.返回(实际上是this->root = createTree())
}
template <class T>
BiTree<T>::BiTree(T* a, int n){
createTree(root, a, n);
}
//析构函数，释放二叉链表中各结点的存储空间
template <class T>
BiTree<T>::~BiTree(){
releaseTree(root);
}
//获得指向根结点的指针
template <class T>
Node<T>* BiTree<T>::getRoot(){
return root;
}
//前序遍历二叉树
template <class T>
void BiTree<T>::preOrder(Node<T> *root){
if(root){
cout<<root->data<<" ";
preOrder(root->lchild);
preOrder(root->rchild);
}
}
//中序遍历二叉树
template <class T>
void BiTree<T>::inOrder(Node<T> *root){
if(root){
inOrder(root->lchild);
cout<<root->data<<" ";
inOrder(root->rchild);
}
}
//后序遍历二叉树
template <class T>
void BiTree<T>::postOrder(Node<T> *root){
if(root){
postOrder(root->lchild);
postOrder(root->rchild);
cout<<root->data<<" ";
}
}
//层序遍历二叉树
template <class T>
void BiTree<T>::leverOrder(Node<T> *root){
int front = 0;
int rear = 0; //采用顺序队列，并假定不会发生上溢
Node<T>* queue[SIZE];//存放结点指针的数组
Node<T>* t; //临时结点指针
if(root == NULL) return;
else{
queue[rear++] = root;
while(front != rear){
t = queue[front++];
if(t) cout<<t->data<<" ";
if(t->lchild) queue[rear++] = t->lchild;
if(t->rchild) queue[rear++] = t->rchild;
}
}
}
//层序遍历二叉树(利用循环队列)
/*
template <class T>
void BiTree<T>::leverOrder(Node<T> *root){
int front = 0;
int rear = 0; //采用顺序队列，并假定不会发生上溢
Node<T>* queue[SIZE];//存放结点指针的数组
Node<T>* t; //临时结点指针
if(root == NULL) return;
else{
queue[rear] = root;
rear = (rear+1)%SIZE;
while(front != rear){
t = queue[front];
front = (front+1)%SIZE;
if(t) cout<<t->data<<" ";
if(t->lchild){ queue[rear] = t->lchild; rear = (rear+1)%SIZE;}
if(t->rchild){ queue[rear] = t->rchild; rear = (rear+1)%SIZE;}
}
}
}*/
//-------------------------建立树的三种参数设置方法---------------------------------
//有参构造函数调用(前序递归建立树，输入顺序也必须是前序)
/*
template <class T>
void BiTree<T>::creatTree(Node<T> **root){
T ch;
cout<<"请输入创建一棵二叉树的结点数据"<<endl;
cin>>ch;
if(ch == "#") *root = NULL;
else{
*root = (Node<T>*)new Node<T>; //*root = new Node<T>;不过前面写法更好
(*root)->data = ch;
creatTree(&(*root)->lchild);
creatTree(&(*root)->rchild);
}
}
*/
/*
template <class T>
Node<T>* BiTree<T>::creatTree(){
Node<T>* root;
T ch;
cout<<"请输入创建一棵二叉树的结点数据"<<endl;
cin>>ch;
if(ch == "#") root = NULL;
else{
root = new Node<T>;
root->data = ch;
root->lchild = creatTree();
root->rchild = creatTree();
}
return root;
}
*/
template <class T>
void BiTree<T>::creatTree(Node<T>* &root){
T ch;
cout<<"请输入创建一棵二叉树的结点数据"<<endl;
cin>>ch;
if(ch == "#") root = NULL;
else{
root = new Node<T>;
root->data = ch;
creatTree(root->lchild);
creatTree(root->rchild);
}
}
template <class T>
void BiTree<T>::createTree(Node<T>* &root, T* s, int n){
Node<T>* queue[SIZE];
Node<T> *p, *m;
int rear = 0, front = 0;
if(s[0] == "#"){
root = NULL;
}else{
root = new Node<T>;
root->data = s[0];
queue[rear++] = root;
}
int i=1;//注意不管出不出栈，或者是空节点，i都要往前,出一次栈对应i前进2
while(front != rear && i<n)
{
p = queue[front++];
if(s[i] != "#"){
//出栈后遍历后面连续两个左右节点
m = new Node<T>;
m->data = s[i++];
p->lchild = m;
queue[rear++] = m;
if(s[i] != "#"){ //右
m = new Node<T>;
m->data = s[i++];
p->rchild = m;
queue[rear++] = m;
}else{
i++;
p->rchild = NULL;
}
}else{
i++;
p->lchild = NULL;
if(s[i] == "#"){
p->rchild = NULL;
i++;
}else{
m = new Node<T>;
m->data = s[i++];
p->rchild = m;
queue[rear++] = m;
}
}
//cout<<"----"<<i<<endl;
}
}
//析构函数调用
template <class T>
void BiTree<T>::releaseTree(Node<T> *root){
if(root){
//递归删除，先释放左右结点在根结点,不能是先根在左右
releaseTree(root->lchild);
releaseTree(root->rchild);
delete root;
}
}
//前序遍历二叉树(非递归)
//它是在进栈的时候输出
template <class T>
void BiTree<T>::nrPreOrder(Node<T> *root){
Node<T>* stack[SIZE];
int top = 0;
Node<T>* t = root;
while(t || top != 0){
//一直遍历左孩子，直到左孩子为空
while(t){
cout<<t->data<<" ";
stack[top++] = t;
t = t->lchild;
}
//如果左孩子为空了，然后出栈，遍历右结点
if(top != 0){
t = stack[--top];
t = t->rchild;
}
}
}
//中序遍历二叉树(非递归)
//它是在出栈的时候输出
template <class T>
void BiTree<T>::nrInOrder(Node<T> *root){
Node<T>* stack[SIZE];
int top = 0;
Node<T>* t = root;
while(t || top != 0){
//一直遍历左孩子，直到左孩子为空
while(t){
stack[top++] = t;
t = t->lchild;
}
//如果左孩子为空了，然后出栈，遍历右结点
if(top != 0){
t = stack[--top];
cout<<t->data<<" ";
t = t->rchild;
}
}
}
//后序遍历二叉树(非递归)
//需要设置标志位，
template <class T>
void BiTree<T>::nrPostOrder(Node<T> *root){
Node<T>* stack[SIZE];//存储树结点
int flag[SIZE]; //标记结点(0标记第一次出栈(未出)，1标记第二次出栈（可出）)
int top = 0;
Node<T>* t = root;
while(t || top != 0){
while(t){
stack[top] = t;
flag[top] = 0;
top++;
t = t->lchild;
}
//可以出栈
while(top != 0 && flag[top-1] == 1){
t = stack[--top];
cout<<t->data<<" ";
}
if(top != 0){//第一次出栈（实际上并未出栈，只是标志位变为0）
t = stack[top-1];
flag[top-1] = 1;
t = t->rchild;
}else{
t = NULL; //这是结束条件，当top==0,在置t为空才能结束整个循环
}
}
}
//搜索节点x
template <class T>
void BiTree<T>::search(Node<T>* root, T x, Node<T>* &p){
if(root){
if(root->data == x){ p = root; return; }
search(root->lchild, x, p);
search(root->rchild, x, p);
}
}
//寻找值为data的节点
template <class T>
Node<T>* BiTree<T>::searchNode(T x){
Node<T>* r = NULL;
if(root){
search(root, x, r);
}
return r;
}
//二叉树深度
template <class T>
int BiTree<T>::biTreeDepth(Node<T>* root){
int hl, hr;
if(root){
hl = biTreeDepth(root->lchild);
hr = biTreeDepth(root->rchild);
return (hl>hr?hl:hr)+1;
}
return 0;
}
//如果存在值为data的节点，返回其父节点
template <class T>
Node<T>* BiTree<T>::getParent(Node<T>* root, T x){
Node<T> *q;
if(!root) return NULL;
else{
//如果找到则返回
if((root->lchild && root->lchild->data==x) || (root->rchild && root->rchild->data==x)){
return root;
//如果递归左子树没找到，到右子树上找(把递归当成普通的操作一样)
}
//如果左子树找到了返回双亲
if(q = getParent(root->lchild, x)) return q;
//如果左子树没找到，则到右子树找
else if(q = getParent(root->rchild, x)) return q;
//如果左右都没找到则返回空
else return NULL;
}
}
//获取左兄弟
template <class T>
Node<T>* BiTree<T>::getLeftSibling(Node<T>* root, T x){
if(!root) return NULL;
else{
if(root->lchild && root->lchild->data==x){//如果左子树是x，则必然不存在左兄弟
return NULL;
}
if(root->rchild && root->rchild->data==x){//如果右子树是x，看是否存在左子树，存在则返回
return root->lchild;
}
return getLeftSibling(root->lchild, x);
return getLeftSibling(root->rchild, x);
}
}
//获取右兄弟
template <class T>
Node<T>* BiTree<T>::getRightSibling(Node<T>* root, T x){
if(!root) return NULL;
else{
if(root->rchild && root->rchild->data==x){
return NULL;
}
if(root->lchild && root->lchild->data==x){//获取右兄弟，则只需要关心左节点，如果左节点是x，在看左
return root->rchild;
}
return getRightSibling(root->lchild, x);
return getRightSibling(root->rchild, x);
}
}
//叶子个数
template <class T>
int BiTree<T>::leafCount(Node<T>* root){
if(!root) return 0;
else if(!root->lchild && !root->rchild){//如果是叶子节点，返回1
return 1;
}else{//如果左右子树不空，则递归遍历左右子树，结果就是左右子树叶子节点的和(递归加)
return leafCount(root->lchild) + leafCount(root->rchild);
}
}
//节点个数
template <class T>
int BiTree<T>::nodeCount(Node<T>* root){
if(!root) return 0;
else{//递归调用加
//节点个数=左子树节点个数+右子树节点个数+1
return nodeCount(root->lchild) + nodeCount(root->rchild) + 1;
}
}
template <class T>
void BiTree<T>::deleteSibTree(Node<T>* root, T x){
Node<T>* p;
if(root){
if(root->lchild && root->lchild->data==x){
p = root->lchild;
root->lchild = NULL;
//递归删除p的左右子树
releaseTree(p->lchild);
releaseTree(p->rchild);
delete p;
}else if(root->rchild && root->rchild->data==x){
p = root->rchild;
root->rchild = NULL;
//递归删除p的左右子树
releaseTree(p->lchild);
releaseTree(p->rchild);
delete p;
}else{//递归查找左右子树
deleteSibTree(root->lchild, x);
deleteSibTree(root->rchild, x);
}
}
}
3.测试程序
//二叉树的主函数，文件名为bitreemain.cpp
#include<iostream>
#include<string>
#include"bitree.cpp"
using namespace std;
int main()
{
//注：BiTree<string> bt在输入的时候，必须是按照前序遍历的顺序输入节点，因为递归建立树的过程就是前序遍历
//BiTree<string> bt;
//string a[] = {"a", "b", "c", "#", "d", "#", "#", "#", "#", "#", "#"};
//string a[] = {"a", "b", "c", "d", "#", "#", "#", "#", "#"};
string a[] = {"a", "b", "c", "#", "d", "e", "f", "g", "#", "#", "#", "#", "#", "#", "#"};
BiTree<string> bt(a, 15); //创建一棵树(按层序输入)
Node<string>* root = bt.getRoot( ); //获取指向根结点的指针
cout<<"------前序遍历------ "<<endl;
bt.preOrder(root);
cout<<endl;
cout<<"------中序遍历------ "<<endl;
bt.inOrder(root);
cout<<endl;
cout<<"------后序遍历------ "<<endl;
bt.postOrder(root);
cout<<endl;
cout<<"------层序遍历------ "<<endl;
bt.leverOrder(root);
cout<<endl;
cout<<"------非递归前序遍历------ "<<endl;
bt.nrPreOrder(root);
cout<<endl;
cout<<"------非递归中序遍历------ "<<endl;
bt.nrInOrder(root);
cout<<endl;
cout<<"------非递归后序遍历------ "<<endl;
bt.nrPostOrder(root);
cout<<"\n---------基本操作----------"<<endl;
Node<string>* t;
cout<<"搜索b:";
t = bt.searchNode("b");
if(t) cout<<t->data<<endl;
else cout<<"无"<<endl;
if(t->lchild) cout<<"L:"<<t->lchild->data<<endl;
if(t->rchild) cout<<"R:"<<t->rchild->data<<endl;
cout<<"a的双亲：";
t = bt.getParent(root, "a");
if(t) cout<<t->data<<endl;
else cout<<"无"<<endl;
cout<<"b的双亲：";
t = bt.getParent(root, "b");
if(t) cout<<t->data<<endl;
else cout<<"无"<<endl;
cout<<"b的左兄弟：";
t = bt.getLeftSibling(root, "b");
if(t) cout<<t->data<<endl;
else cout<<"无"<<endl;
cout<<"b的右兄弟：";
t = bt.getRightSibling(root, "b");
if(t) cout<<t->data<<endl;
else cout<<"无"<<endl;
cout<<"c的左兄弟：";
t = bt.getLeftSibling(root, "c");
if(t) cout<<t->data<<endl;
else cout<<"无"<<endl;
cout<<"c的右兄弟：";
t = bt.getRightSibling(root, "c");
if(t) cout<<t->data<<endl;
else cout<<"无"<<endl;
cout<<"二叉树深度："<<bt.biTreeDepth(root)<<endl;
cout<<"叶子个数："<<bt.leafCount(root)<<endl;
cout<<"节点个数："<<bt.nodeCount(root)<<endl;
cout<<"删除节点为d的子树"<<endl;
bt.deleteSibTree(root, "d");
cout<<"------前序遍历------ "<<endl;
bt.preOrder(root);
cout<<endl;
cout<<"------中序遍历------ "<<endl;
bt.inOrder(root);
cout<<endl;
return 0;
}
4.总结
每个操作的一些注意事项都在代码中进行了说明，主要注意一下，建立二叉树的时候，如何输入节点？见下图：
- 大小: 12.9 KB
分享到：
评论
2 楼
hao3100590
2012-10-03
wentfar 写道
void creatTree(Node<T>* root);
这个函数是有问题的。
二叉树本质上是用地址（Node<T>* root）来表示的。
根据形参的值传递规则，要改变原二叉树，必须传递地址的地址，即为（Node<T>** root）。
这个函数是有问题的。
二叉树本质上是用地址（Node<T>* root）来表示的。
根据形参的值传递规则，要改变原二叉树，必须传递地址的地址，即为（Node<T>** root）。
好的，谢谢，这个函数的确有问题，参数使用指针引用或者双指针即可
1 楼
wentfar
2012-09-29
void creatTree(Node<T>* root);
这个函数是有问题的。
二叉树本质上是用地址（Node<T>* root）来表示的。
根据形参的值传递规则，要改变原二叉树，必须传递地址的地址，即为（Node<T>** root）。
这个函数是有问题的。
二叉树本质上是用地址（Node<T>* root）来表示的。
根据形参的值传递规则，要改变原二叉树，必须传递地址的地址，即为（Node<T>** root）。
发表评论
-
排序方法总结
2012-08-12 11:34 1131这里面包含了所有常见的排序操作 1.性能等比较分析 2 ... -
常见字符串操作大全
2012-08-12 11:34 14161.常见的字符串操作 如计算长度，求子串等都是考验基本功的， ... -
KMP算法解析
2012-08-12 11:35 2773一.理论基础 1.什么 ... -
二叉堆的实现
2012-08-12 11:35 11711.堆的概念 这里只需要注意两点： a.堆的存储方式：就是 ... -
set和map的简单实现
2012-08-10 11:35 12741.Set的简单实现 set是利用二叉查找树来实现的,而且为 ... -
红黑树的插入总结
2012-08-10 11:25 9051.红黑树 这个在july的博客中有详尽的说明，我就不在赘述 ... -
B-树实现
2012-08-10 11:03 15861.什么是B-树？ 这个在我的前一篇博客中已经详细的阐释过： ... -
平衡二叉树
2012-08-10 10:39 27931.问题描述 什么是平衡 ... -
二叉排序树
2012-08-10 10:25 14151.基本概念 二叉排 ... -
B-树
2012-07-04 22:48 56071.B-树的概念 是一种多 ... -
构造哈夫曼树
2012-07-04 10:40 11871.算法说明 就是建造哈夫曼树树，从而使得构造出的树带权路径 ... -
线索二叉树
2012-07-04 09:20 12361.算法描述 就是简单的线索二叉树的建立，遍历，查找等基本操 ... -
多种队列的实现
2012-06-29 10:09 14911.算法描述 a.数据结构与算法（Mark Allen We ... -
栈的各种实现
2012-06-28 16:34 10731.算法描述 a.实现二个栈，在一个数组里面，除非没有任何空 ... -
中缀表达式转换为后缀
2012-06-28 11:10 17501.算法描述 例如a+b*c这是常见的中缀表达式，但是 ... -
后缀表达式的值
2012-06-27 16:33 12881.算法描述 计算后缀表达式的值 2.事例 如：（ ... -
Josephus问题
2012-06-21 15:30 9531.算法描述 简单的游戏：有N个人坐成一圈，编号1-N、从编 ... -
关于最长递增子序列的实际应用--动态规划
2012-06-07 11:35 1788参考链接： a.http://www.programfan. ... -
线性查找二维数组
2012-06-05 17:23 9971.算法描述 有序（行有序，列有序，且每行从左至右递增 ... -
整数的随机置换
2012-06-05 15:10 2228算法描述:生成前N个整 ...
相关推荐
二叉树基本操作的程序实现，可以完成基本的操作
C++二叉树基本操作
运用二叉链表实现二叉树的基本操作，包括：创建二叉树的存储结构、复制已有的二叉树、计算已有的二叉树的深度、先根序序列、中根序序列、后根序序列等。 输入格式：AB#C##D## 二、实验目的 掌握二叉链表及二叉树的...
创建，输出左右结点，求深度，宽度，求叶子结点及总结点的个数，查找结点，求某结点的子孙个数，输出二叉树
二叉树的基本操作的各种操作 先序 中序 后序 遍历二叉树 还有二叉树的节点数的求法
【实验课程名称】算法与数据结构 【实验项目名称】二叉树基本操作的实现
1． 熟悉二叉树结点的结构和对二叉树的基本操作。 2． 掌握对二叉树每一种操作的具体实现。...4． 在二叉树基本操作的基础上掌握对二叉树的一些其它操作的具体实现方法。 5． 掌握构造哈夫曼树以及哈夫曼编码的方法
二叉树基本操作 数据结构 实验报告
1、根据输入的数据建立一个二叉树； 2、分别采用前序、中序、后序的遍历方式显示输出二叉树的遍历结果 3、采用非递归的编程方法，分别统计二叉树的节点个数、度为1、度为2和叶子节点的个数，以及数据值的最大值和...
二叉树的基本操作，使用递归算法,先序遍历建造二叉树。
二叉树的基本操作java代码
南邮数据结构实验使用C++描述，二叉树的基本操作
数据结构实用教程之二叉树，其中包含了：二叉树的定义、二叉树的递归遍历、二叉树基本操作。 数据结构实用教程之二叉树，其中包含了：二叉树的定义、二叉树的递归遍历、二叉树基本操作。 数据结构实用教程之二叉树，...
实现了二叉树的前向生成以及前向遍历。属于二叉树的基本操作。
编写程序实现二叉树的如下操作： 1) 建立二叉链表 2) 二叉树的先序、中序、后序遍历 3) 求解二叉树的叶子结点个数 4) 将二叉树中所有结点的左、右子树相互交换 输入： 扩展二叉树先序序列：ab#d##ce###。其中#...
问题描述：采用二叉链表作为存储结构，完成图1的二叉树的建立和遍历操作。 基本要求： （1）基于先序遍历的构造算法。输入是二叉树的先序序列，但必须在其中加入虚结点以示空指针的位置。假设虚结点输入时用空格字符...
递归二叉树的基本操作，递归创建，递归先序遍历、中序遍历、后序遍历，求树的高度，求叶子结点的个数，交换树的左右孩子