数据结构二叉树的程序设计
加我．我有～
//这个题目挺有意思的，很喜欢，你看看我这个咋样啊？
#include
#include
typedef char ElemType ;
typedef struct node
{
ElemType data ;
struct node *lchild ;
struct node *rchild ;
}BTree,*pBTree ;
//先序创建树
void CreateBTree(pBTree *T)
//此处参数应该用指针的指针，应给它要改变指向二叉树根的那个指针
{
char ch ;
ch=getchar();
getchar(); //得到回车按那个字符
if(ch ==' ') //输入空字符时要打空格
{
(*T) = NULL ;
return ;
}
else
{
if( !( (*T) = (pBTree) malloc(sizeof(BTree)) ) ) return ;
(*T)->data = ch ;
CreateBTree( &(*T)->lchild );
CreateBTree( &(*T)->rchild );
}
}
void BTreePrint(BTree *Tr,int n)
//逆时针旋转90°打印二叉树，n为缩进层数，初始值为0
{
int i;
if(Tr == NULL) return;
BTreePrint(Tr->rchild,n+1);
for(i = 0;i<n;i++)
printf(" ");
if(n >= 0)
{
printf("--");
printf("%c
",Tr->data);
}
BTreePrint(Tr->lchild,n+1);
}
void main()
{
pBTree bTree ;
CreateBTree(&bTree);
BTreePrint(bTree,0);
}
输入举例：建立以A为根B、C分别为左右子树的二叉树！输入格式为：
A 回车！
B 回车！
空格 回车！
空格 回车！
C 回车！
空格 回车！
空格 回车！
先说明我定的是C++程序
先实现二叉树的，把以下代码复制粘贴即可
#include <iostream>
using namespace std;
//****Lqueue.h
#define MAXQSIZE 100
typedef int Status;
template <class QElemType>
class Lqueue
{
public:
void InitQueue();
void DestroyQueue();
void ClearQueue();
Status QueueEmpty();
Status QueueLength();
void GetHead(QElemType & e);
void EnQueue(QElemType e);
void DeQueue(QElemType & e);
private:
struct SqQueue
{
QElemType * base;
int front;
int rear;
};
SqQueue Q;
};
//********Lqueue.cpp********
template <class QElemType>
void Lqueue<QElemType>::InitQueue()
{
Q.base = (QElemType *)malloc(MAXQSIZE * sizeof(QElemType));
if(!Q.base) exit(0);
Q.front = Q.rear = 0;
}
template <class QElemType>
void Lqueue<QElemType>::DestroyQueue()
{
free(Q.base);
}
template <class QElemType>
void Lqueue<QElemType>::ClearQueue()
{
Q.front = Q.rear = 0;
}
template <class QElemType>
Status Lqueue<QElemType>::QueueEmpty()
{
if(Q.front == Q.rear) return 1;
return 0;
}
template <class QElemType>
Status Lqueue<QElemType>::QueueLength()
{
return (Q.rear - Q.front + MAXQSIZE)%MAXQSIZE;
}
template <class QElemType>
void Lqueue<QElemType>::GetHead(QElemType & e)
{
if(Q.front == Q.rear) e = NULL;
else
{
e = Q.base[Q.front];
}
}
template <class QElemType>
void Lqueue<QElemType>::EnQueue(QElemType e)
{
if((Q.rear + 1)%MAXQSIZE == Q.front) cout << "ERROR" << endl;
else
{
Q.base[Q.rear] = e;
Q.rear = (Q.rear + 1)%MAXQSIZE;
}
}
template <class QElemType>
void Lqueue<QElemType>::DeQueue(QElemType & e)
{
if(Q.front == Q.rear) cout << "ERROR" << endl;
else
{
e = Q.base[Q.front];
Q.front = (Q.front + 1)%MAXQSIZE;
}
}
//******************Lqueue.cpp***************
//*****stack.h
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef int Status;
template<class QElemType>
class stack
{
public:
void InitStack();
void DestroyStack();
void ClearStack();
Status StackEmpty();
Status StackLength();
void GetTop(QElemType & e);
void Push(QElemType e);
void Pop(QElemType & e);
private:
struct SqStack{
QElemType *base;
QElemType *top;
int stacksize;
}S;
};
//******stack.cpp------
template<class QElemType>
void stack<QElemType>::InitStack()
{
S.base = (QElemType *)malloc(STACK_INIT_SIZE * sizeof(QElemType));
if(!S.base) exit(0);
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
}
template <class QElemType>
void stack<QElemType>::DestroyStack()
{
free(S.base);
}
template <class QElemType>
void stack<QElemType>::ClearStack()
{
S.top = S.base;
}
template <class QElemType>
Status stack<QElemType>::StackEmpty()
{
if(S.top == S.base) return 1;
else return 0;
}
template <class QElemType>
Status stack<QElemType>::StackLength()
{
return (S.top - S.base);
}
template <class QElemType>
void stack<QElemType>::GetTop(QElemType & e)
{
if(S.top != S.base)
e = *(S.top - 1);
else e = NULL;
}
template <class QElemType>
void stack<QElemType>::Push(QElemType e)
{
if(S.top - S.base >= S.stacksize)
{
S.base = (QElemType *)realloc(S.base,(S.stacksize + STACKINCREMENT) * sizeof(QElemType));
if(!S.base) exit(0);
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top++ = e;
}
template <class QElemType>
void stack<QElemType>::Pop(QElemType & e)
{
if(S.top == S.base) e = NULL;
else
e = * --S.top;
}
//**********stack.cpp
//****************BiTree.h
template <class TElemType>
struct BiTNode{
TElemType data;
BiTNode<TElemType> *lchild,*rchild;
};
template <class TElemType>
class BiTree
{
public:
void CreateBiTree(BiTNode<TElemType> *&T);
void CreateBiTree();
void PreOrderTraverse(BiTNode<TElemType> *T);
void PreOrderTraverse();
void InOrderTraverse(BiTNode<TElemType> *T);
void InOrderTraverse();
void PostOrderTraverse(BiTNode<TElemType> *T);
void PostOrderTraverse();
void LevelOrderTraverse();
private:
BiTNode<TElemType> *T;
};
template <class TElemType>
void BiTree<TElemType>::CreateBiTree(BiTNode<TElemType> *&T)
{
TElemType ch;
cin >> ch;
if(sizeof(ch) == 1 && ch == '0') T = NULL;
else if(ch == -1) T = NULL;
else
{
if(!(T = (BiTNode<TElemType> *)malloc(sizeof(BiTNode<TElemType>)))) exit(0);
T->data = ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
template <class TElemType>
void BiTree<TElemType>::CreateBiTree()
{
CreateBiTree(T);
}
template <class TElemType>
//递归先序遍历
void BiTree<TElemType>::PreOrderTraverse(BiTNode<TElemType> *T)
{
if(T)
{
cout << T->data << " ";
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
} //PreOrderTraverse
template <class TElemType>
void BiTree<TElemType>::PreOrderTraverse()
{
PreOrderTraverse(T);
}
//非递归先序遍历
/*void BiTree<TElemType>::PreOrderTraverse()
{
BiTNode<TElemType> * p = T;
stack<BiTNode<TElemType> *> S;
S.InitStack();
while(p || !S.StackEmpty())
{
if(p)
{
S.Push(p);
cout << p->data << " ";
p = p->lchild;
}
else
{
S.Pop(p);
p = p->rchild;
}
}
S.DestroyStack();
} */
//递归中序遍历
template <class TElemType>
void BiTree<TElemType>::InOrderTraverse(BiTNode<TElemType> *T)
{
if(T)
{
InOrderTraverse(T->lchild);
cout << T->data << " ";
InOrderTraverse(T->rchild);
}
}
template <class TElemType>
void BiTree<TElemType>::InOrderTraverse()
{
InOrderTraverse(T);
}
//非递归中序遍历
/*void BiTree<TElemType>::InOrderTraverse()
{
BiTNode<TElemType> * p = T;
stack<BiTNode<TElemType> *> S;
S.InitStack();
while(p || !S.StackEmpty())
{
if(p)
{
S.Push(p);
p = p->lchild;
}
else
{
S.Pop(p);
cout << p->data << " ";
p = p->rchild;
}
}
S.DestroyStack();
} */
//递归后序遍历
template <class TElemType>
void BiTree<TElemType>::PostOrderTraverse(BiTNode<TElemType> *T)
{
if(T)
{
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
cout << T->data << " ";
}
}
template <class TElemType>
void BiTree<TElemType>::PostOrderTraverse()
{
PostOrderTraverse(T);
}
//非递归后序遍历
/*void BiTree<TElemType>::PostOrderTraverse()
{
BiTNode<TElemType> * p = T;
BiTNode<TElemType> * q = NULL;
stack<BiTNode<TElemType> *> S;
S.InitStack();
S.Push(p);
p = p->lchild;
while(!S.StackEmpty())
{
if(p)
{S.Push(p);p = p->lchild;}
else
{
S.GetTop(p);
p = p->rchild;
if(!p)
{
S.Pop(p);
cout << p->data << " ";
S.GetTop(q);
while(q && p == q->rchild)
{
S.Pop(p);
cout << p->data << endl;
S.GetTop(q);
//if(q == NULL) break;
}
if(q)
{
S.GetTop(q);
p = q->rchild;
}
}
}
}
S.DestroyStack();
} */
//非递归层次遍历
template <class TElemType>
void BiTree<TElemType>::LevelOrderTraverse()
{
Lqueue<BiTNode<TElemType> *> que;
que.InitQueue();
if(T) que.EnQueue(T);
while(!que.QueueEmpty())
{
que.GetHead(T);
if(T->lchild) que.EnQueue(T->lchild);
if(T->rchild) que.EnQueue(T->rchild);
que.DeQueue(T);
cout << T->data << " ";
}
que.DestroyQueue();
}
//**************BiTree.h
int main()
{
BiTree<char> tree;
cout << "请按树的先序遍历输入数据(0表示空(字符型),-1表示空（实数型）):" << endl;
tree.CreateBiTree();
tree.InOrderTraverse();
tree.PreOrderTraverse();
tree.PostOrderTraverse();
tree.LevelOrderTraverse();
cout << endl;
return 0;
}
演示程序如图，结果中包含了各种遍历。此程序中输入的表示顶点的是字符。若要用一个数表示顶点，可在main()中把BiTree<char> tree;改成
BiTree<int> tree; 当然也可以改成float.
我实现的是模板类，可实例化各种类型。
再打开一个C++的窗口，把以下赫夫曼的代码粘贴进去即可。
#include <iostream>
#include <string.h>
#include <iomanip>
using namespace std;
struct Huffmantree
{
unsigned int weight;
unsigned int lchild,rchild,parent;
};
struct wch
{
char ch;
unsigned int weight;
};
void HuffmanCoding(Huffmantree *& HT,char **&htcode,wch *&w,int n);
void Select(Huffmantree * HT,int n,int &s1,int &s2);
void DestroyHuffman(Huffmantree *& HT,char **&htcode,wch *&w,int n);
int main()
{
Huffmantree *HT = NULL;
wch *w = NULL;
char **htcode = NULL;
int n;
cout << "输入字符个数:" << endl;
cin >> n;
HuffmanCoding(HT,htcode,w,n);
for(int i = 0;i < n;i ++)
cout << w[i].ch << " " << htcode[i] << endl;
DestroyHuffman(HT,htcode,w,n);
return 0;
}
void HuffmanCoding(Huffmantree *&HT,char **&htcode,wch *&w,int n)
{//n个结点的赫夫曼树有2n-1个结点
int i;
int start,p,q,s1,s2;
w = (wch *)malloc(n * sizeof(wch));
cout << "输入" << n << "个字符及其相应的权值" << endl;
for(i = 0;i < n;i ++)
cin >> w[i].ch >> w[i].weight;
//构造赫夫曼树
HT = (Huffmantree *)malloc((2*n-1) * sizeof(Huffmantree));
for(i = 0;i < n;i ++)
{
HT[i].weight = w[i].weight;
HT[i].lchild = 0,HT[i].rchild = 0;
HT[i].parent = 0;
}
for(;i < 2*n-1;i ++)
{
HT[i].weight = 0;
HT[i].lchild = 0,HT[i].rchild = 0;
HT[i].parent = 0;
}
for(i = n;i < 2*n-1;i ++)
{
Select(HT,i-1,s1,s2);
HT[i].lchild = s1,HT[i].rchild = s2;
HT[s1].parent = i,HT[s2].parent = i;
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
//构造完成
htcode = (char **)malloc(n * sizeof(char *));
char *cd = (char *)malloc(n * sizeof(char));
cd[n-1] = '\0';
for(i = 0;i < n;i ++)
{
start = n-1;
for(p = i;HT[p].parent != 0;p = HT[p].parent)
{
q = HT[p].parent;
if(p == HT[q].lchild) cd[--start] = '0';
else cd[--start] = '1';
}
htcode[i] = (char *)malloc((n-start)*sizeof(char));
strcpy(htcode[i],&cd[start]);
}
}
void Select(Huffmantree *HT,int n,int &s1,int &s2)
{
int i;
s1 = s2 = -1;
for(i = 0;i <= n;i ++)
{
if(HT[i].parent == 0 && s1 == -1)
s1 = i;
if(HT[i].parent == 0 && HT[i].weight < HT[s1].weight)
s1 = i;
}
for(i = 0;i <= n;i ++)
{
if(HT[i].parent == 0 && s2 == -1 && i != s1)
s2 = i;
if(HT[i].parent == 0 && HT[i].weight < HT[s2].weight && s1 != i) //此处易出错,漏掉s1 != i
s2 = i;
}
}
void DestroyHuffman(Huffmantree *&HT,char **&htcode,wch *&w,int n)
{
free(HT);
free(w);
for(int i = 0;i < n;i ++)
free(htcode[i]);
free(htcode);
}
数据结构问题:二叉树遍历
\/\/ 恢复二叉树 template< class T > void rebuildTree( string szInOrder, string szPostOrder, BinaryTreeNode< T > * curParent, int start, int end ){ \/\/szInOrder 为中序遍历，szPostOrder 为后序遍历 \/\/curParent 为当前父结点 \/\/start 为开始下标，end 为结束下标 if ( start > ...
二叉树是如何实现数据结构的?
今天我也遇到这道题了，经过我的研究，我觉得应该是如下的解答：首先画出该树 ：如下图左边所示。然后根据树的二叉链表表示法表示存储结构如图右边所示：注意这里的指针域为左边表示第一个孩子*firstchild，右边表示兄弟*nextsibling 紧接着就涉及到了树与二叉树的转换：核心思想：左子树放孩子，右子树放...
什么是二叉树,举一个二叉树的例子
详情请查看视频回答
数据结构中序和后序怎么画二叉树
右边是右子树的中序，知道这两子树的中序，就能从后序中，把左子序、右子树 找出来（据中序的左、右子树的结点数）。这样，根节点找出来了，左子数的后序、中序就分离出来了，右子数也分离出来了，这个问题，就化成两个新树的问题。同样的办法如此，就是递归成两个子树的新问题。如果用程序，...
二叉树的构造过程可以分为哪几个过程?
首先，根据给定的中序遍历序列和后序遍历序列，我们可以推断出这棵二叉树的结构。中序遍历序列是AEHCFBIGD，后序遍历序列是HEFCIGDBA。在后序遍历序列中，最后一个节点A是根节点，它的左子树包含在后序遍历序列的第一个元素H和最后一个元素D之间，右子树包含在后序遍历序列的第二个元素F和倒数第二...
二叉排序树的构造过程
二叉排序树 (Binary Sort Tree)，也称为二叉搜索树 (Binary Search Tree)，是一种重要的数据结构，它充分利用了二叉树的有序性质，可以实现快速的数据查找和操作。二叉排序树通过比较底层节点之间的关系建立，可以在平均情况下将查找的时间复杂度降到O(logN)，极大提高了查找效率。下面是二叉排序树的...
请教一下数据结构 二叉树的先序遍历 中序遍历 后序遍历 是怎么弄的
所谓先序、中序和后序的区别在于访问根的时机，分别是BLR、LBR和LRB，其中B、L、R分别表示根结点、根结点的左子树和根结点的右子树。以后序遍历为例进行讲解。后序遍历算法：(1) 后序遍历根结点的左子树；(2) 后序遍历根结点的右子树。(3) 访问二叉树的根结点；你的方法是将树分解为根、左...
C语言编写的数据结构
实验一:用二叉链表作为存储结构,建立二叉树,对二叉树进行前序、后序遍历,并对建立的二叉树进行中序线索,再中序线索遍历。实验二:根据给定的权值建立哈夫曼树,进行前序遍历。\/*建... 实验一:用二叉链表作为存储结构,建立二叉树,对二叉树进行前序、后序遍历,并对建立的二叉树进行中序线索,再中序线索遍历。实验...
最优二叉树算法构造算法
在哈夫曼树的构建过程中，算法的核心是通过不断合并森林（F）中的二叉树来形成最终的哈夫曼树。首先，我们设计一个结构数组HuffNode，用于存储哈夫曼树的节点信息，包括权值、左右子节点索引以及父节点索引。初始时，parent域的值设为-1，表示节点未加入树中。数组HuffNode的大小根据叶子节点个数n设置为...
基本的二叉树
在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2^...
堂友新百： BT.H文件 #include <stdio.h> #include <malloc.h> #include <conio.h> #define TRUE 1 #define FALSE 0 #define ERROR 0 #define OK 1 #define Stack_Size 50 #define NUM 50 #define MAXSIZE 50 //队列的最大长度 //定义二叉树 typedef char ...
峨眉山市19254184119： 数据结构上机实验编程:二叉树.要一套完整的代码程序!!!不要文字描述 - ？
堂友新百： 以下为程序代码,请楼主参考# include <stdio.h># include <stdlib.h># define OK 1# define ERROR -1# define overflow -1 typedef int ElemType; typedef int Status; typedef struct BiTNode { ElemType data;//此处Elem Type 根据数据类型实际情况而...
峨眉山市19254184119： 数据结构中用c语言建立二叉树的程序？
堂友新百： #include ＂stdio.h＂#include ＂stdlib.h＂#include ＂malloc.h＂typedef struct Bnode //二叉树节点类型{int m; struct Bnode *Lchild,*Rchild;}Btnode, *BTptr; typedef struct Dnode //队列节点类型{ Btnode *pr; struct Dnode *next;}Qnode,*Qlink;typedef ...
峨眉山市19254184119： 二叉树(C语言)怎么创建? - ？
堂友新百： C语言中二叉树的创建需要用到结构体来定义一个树的数据类型.树这个数据结构有一些数据域,和多个指针域.当然,对于二叉树而言,一般可以定义两个指针域,分别指向root节点的左右子节点.数据结构定义:struct tree{ int data; //这里数据域以此为例 tree*right,*left;}; 真正构建二叉树可以使用动态内存申请,这是一种比较常见的方法(如果不会动态内存申请,可以先看看),但是这样做在子树很多时会耗费较多时间.因此可以事先开辟好一段内存空间用于存储树.比如 tree T[2000];如果需要建立新的子树,那么只需将数组中某个左右子节点赋值即可.如有疑问,欢迎继续追问.
峨眉山市19254184119： 用c语言编程实现二叉树的建立和遍历二叉树? - ？
堂友新百： //这是我上数据结构写的 建议理解为主#include#include#define ERROR 0#define OK 1#define OVERFLOW -2#define FLASE 0#define TURE 1 typedef int Status; typedef char TElemType; typedef struct BiTNode{ TElemType data; struct BiTNode ...
峨眉山市19254184119： 数据结构代码(用C语言) 二叉树的操作 - ？
堂友新百： # include struct BTNode { int data; struct BTNode * pLchild;//p是指针,L是左,child是孩子 struct BTNode * pRchild; };//函数声明 struct BTNode * CreateBTree(void);//创建树 void PreTraverseBTree(struct BTNode * pT);//先序遍历 void ...
峨眉山市19254184119： 数据结构课程设计!算术表达式与二叉树!【问题描述】一个表达式和一棵二叉树之间,存在着自然的对应关系.写一个程序,实现基于二叉树表示的算术表达... - ？
堂友新百：[答案] 帮楼主顶个.
峨眉山市19254184119： c语言数据结构:怎么建立一个二叉树? - ？
堂友新百： 只要将一个二叉树用“括号表示法”表示出来,然后,用链式存储结构将其各个结点存储就可以了,也就是输入一个二叉树.最后,用中序遍历输出! typedef struct node{ ElemType data;struct node *lchild,*rchild;} BTNode; //创建一个二叉树...
峨眉山市19254184119： 请问C语言如何创建二叉树???? - ？
堂友新百： 创建二叉树的源程序如下: #include <cstdlib>#include <stdio.h>typedef struct node{ //树的结点int data;struct node* left;struct node* right;} Node;typedef struct{ //树根Node* root;} Tree;void insert(Tree* tree, int value)//创建树{Node* ...
峨眉山市19254184119： 数据结构课程设计(C版语言)二叉排序树算法 - ？
堂友新百： #include<stdio.h>#include<stdlib.h>#include<conio.h> typedef int DataType; //定义数据类型,以int为例 struct BSTNode //定义二叉排序树节点类型 { DataType data; struct BSTNode *lchild,*rchild; }; int insert(struct BSTNode **root,DataType data...
