第四章 树和二叉树
一、二叉树计算高度(二叉树创建的实例)
#include<iostream>
using namespace std;
typedef char ElemType;
typedef struct BiTNode // 二叉树的链式存储结构
{
ElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode, *BiTree;
bool InitBiTree(BiTree& T);
int treeDepth(BiTree T);
bool InitBiTree(BiTree& T) //初始化
{
ElemType ch;
cin>>ch;
if(ch=='#'){
T = NULL;
}else{
T = (BiTNode*)malloc(sizeof(BiTNode));
T->data = ch;
InitBiTree(T->lchild);
InitBiTree(T->rchild);
}
}
int treeDepth(BiTree T) //计算树的深度
{
if(T==NULL) return 0;
int l = treeDepth(T->lchild);
int r = treeDepth(T->rchild);
return l>r?l+1:r+1;
}
int main()
{
BiTree T;
InitBiTree(T);
cout << treeDepth(T);
return 0;
}
/*
输入样例:
ABD##E##C##
输出样例:
3
*/
二、递归实现二叉树 前 中 后 序遍历
#include<iostream>
using namespace std;
typedef char ElemType;
typedef struct BiTNode // 定义二叉树链式存储结构
{
ElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
bool InitBiTree(BiTree& T); //初始化二叉树
void visit(BiTNode* p); //打印节点信息
void PreOrder(BiTree T); //先序遍历
void InOrder(BiTree T); //中序遍历
void PostOrder(BiTree T); //后序遍历
bool InitBiTree(BiTree& T) //初始化二叉树
{
ElemType ch;
cin>>ch;
if(ch=='#'){
T = NULL;
}else{
T = (BiTNode*)malloc(sizeof(BiTNode));
T->data = ch;
InitBiTree(T->lchild);
InitBiTree(T->rchild);
}
}
void visit(BiTNode* p) //打印节点信息
{
cout << p->data << " ";
}
void PreOrder(BiTree T) //先序遍历
{
if(T == NULL) return ;
visit(T);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
void InOrder(BiTree T) //中序遍历
{
if(T == NULL) return ;
InOrder(T->lchild);
visit(T);
InOrder(T->rchild);
}
void PostOrder(BiTree T) //后序遍历
{
if(T == NULL) return ;
PostOrder(T->lchild);
PostOrder(T->rchild);
visit(T);
}
void test()
{
BiTree T;
InitBiTree(T);
cout << "先序遍历" << endl;
PreOrder(T);
cout << endl;
cout << "中序遍历" << endl;
InOrder(T);
cout << endl;
cout << "后序遍历" << endl;
PostOrder(T);
cout << endl;
}
int main()
{
test();
return 0;
}
/*
输入样例:
ABD##E##C##
输出样例:
先序遍历
A B D E C
中序序遍历
D B E A C
后序遍历
D E B C A
*/
四、非递归实现二叉树 前 中 后 序遍历
#include<iostream>
using namespace std;
typedef struct BiTNode
{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
typedef struct LinkNode
{
BiTNode *data;
struct LinkNode* next;
}*LiStack,LinkNode;
// 定义栈的相关操作,用来实现非递归
bool InitStack(LiStack& S);
bool StackEmpty(LiStack S);
bool Push(LiStack& S, BiTNode* x);
bool Pop(LiStack& S, BiTNode*& x);
bool GetTop(LiStack S, BiTNode*& x);
bool DestoryStack(LiStack& S);
bool InitBiTree(BiTree& T); //初始化
void visit(BiTNode* p); //打印节点信息
void PostOrder(BiTree T); //后序遍历
void InOrder(BiTree T); //先序遍历
void PreOrder(BiTree T); //前序遍历
bool InitStack(LiStack& S)
{
S = (LiStack)malloc(sizeof(LinkNode));
if (S == NULL) return false;
S->next = NULL;
return true;
}
bool StackEmpty(LiStack S)
{
if (S->next == NULL) return true;
return false;
}
bool Push(LiStack& S, BiTNode* x)
{
LinkNode* p;
p = (LinkNode*)malloc(sizeof(LinkNode));
if (p == NULL) return false;
p->data = x;
p->next = S->next;
S->next = p;
return true;
}
bool Pop(LiStack& S, BiTNode*& x) {
if (StackEmpty(S)) return false;
LinkNode* p = S->next;
S->next = p->next;
x = p->data;
free(p);
return true;
}
bool GetTop(LiStack S, BiTNode*& x) {
if (StackEmpty(S)) return false;
x = S->next->data;
return true;
}
bool InitBiTree(BiTree& T){
char ch;
cin>>ch;
if(ch=='#'){
T = NULL;
}else{
T = (BiTNode*)malloc(sizeof(BiTNode));
T->data = ch;
InitBiTree(T->lchild);
InitBiTree(T->rchild);
}
}
void visit(BiTNode* p)
{
cout << p->data << " ";
}
void InOrder(BiTree T) // 中序遍历
{
LiStack S;
InitStack(S);
BiTree p = T; // p是遍历指针
while(p || !StackEmpty(S))
{
if(p) //一路向左
{
Push(S,p); //当前节点入栈
p = p->lchild; //左孩子不为空一直向左走
}
else //出栈,并转向该节点的右孩子
{
Pop(S,p); //栈顶结点出栈,访问
visit(p);
p = p->rchild; //向右子树走,
}
}
}
void PreOrder(BiTree T) // 先序遍历
{
LiStack S;
InitStack(S);
BiTree p = T; // 遍历指针
while(p || !StackEmpty(S))
{
if(p) // 一路向左
{
visit(p);
Push(S,p); // 当前节点入栈
p = p->lchild; // 左孩子不为空一直向左走
}
else // 出栈,并转向该节点的右孩子
{
Pop(S,p); // 栈顶结点出栈
p = p->rchild; // 向右子树走
}
}
}
void PostOrder(BiTree T) // 后序遍历
{
LiStack S;
InitStack(S);
BiTree p = T;
BiTNode *r = NULL; //辅助指针,指向最近访问的节点
while(p || !StackEmpty(S))
{
if(p) //走到最左边
{
Push(S,p);
p = p->lchild;
}
else //走到最右边
{
GetTop(S,p); //读栈顶元素(非出栈)
if(p->rchild && p->rchild != r) //若右子树存在且未被访问过
{
p = p->rchild; //转向右
Push(S,p); //压入栈
p = p->lchild; //再走到最左
}
else //否则弹出栈顶元素并访问
{
Pop(S,p);
visit(p);
r = p; //记录最近访问过的节点
p = NULL; //节点访问完后重置p指针
}
}
}
}
void test(){
BiTree T;
InitBiTree(T);
cout<<"----------后序遍历----------"<<endl;
PostOrder(T);
cout<<endl;
cout<<"----------中序遍历----------"<<endl;
InOrder(T);
cout<<endl;
cout<<"----------先序遍历----------"<<endl;
PreOrder(T);
cout<<endl;
}
int main(){
test();
return 0;
}
/*
输入样例:
ABD##E##C##
输出样例:
----------后序遍历----------
D E B C A
----------中序遍历----------
D B E A C
----------先序遍历----------
A B D E C
*/
四、 二叉树层次遍历
—— 通过队列实现
#include<iostream>
using namespace std;
typedef char ElemType;
typedef struct BiTNode{
ElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
typedef struct LinkNode {
BiTNode* data;
struct LinkNode* next;
}LinkNode;
typedef struct {
LinkNode* front, * rear;
}LinkQueue;
bool InitBiTree(BiTree& T); //初始化树
void LevelOrder(BiTree T); //层序遍历
// 定义栈的一系列操作
void InitQueue(LinkQueue& Q);
bool QueueEmpty(LinkQueue Q);
bool EnQueue(LinkQueue& Q, BiTNode* x);
bool DeQueue(LinkQueue& Q, BiTNode*& x);
void visit(BiTNode* p);
void InitQueue(LinkQueue& Q) {
Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
Q.front->next = NULL;
}
bool QueueEmpty(LinkQueue Q) {
if (Q.front == Q.rear) return true;
return false;
}
bool EnQueue(LinkQueue& Q, BiTNode* x) {
LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
s->data = x;
s->next = Q.rear->next;
Q.rear->next = s;
Q.rear = s;
return true;
}
bool DeQueue(LinkQueue& Q, BiTNode*& x) {
if (QueueEmpty(Q)) return false;
LinkNode* q = Q.front->next;
x = q->data;
Q.front->next = q->next;
if (Q.rear == q) {
Q.rear = Q.front;
}
free(q);
return true;
}
bool InitBiTree(BiTree& T){
ElemType ch;
cin>>ch;
if(ch=='#'){
T = NULL;
}else{
T = (BiTNode*)malloc(sizeof(BiTNode));
T->data = ch;
InitBiTree(T->lchild);
InitBiTree(T->rchild);
}
}
void LevelOrder(BiTree T) // 层次遍历
{
LinkQueue Q;
InitQueue(Q); // 初始化队列
BiTree p; // 定义指针
EnQueue(Q,T); // 将根节点入队
while(!QueueEmpty(Q)) // 队列不空则循环
{
DeQueue(Q,p); // 队头结点出队
visit(p); // 访问出队结点
if(p->lchild != NULL) // 如果其有左孩子
EnQueue(Q,p->lchild); // 就将其入队
if(p->rchild!=NULL) // 如果其有有孩子
EnQueue(Q,p->rchild); // 也将其入队
}
}
void visit(BiTNode* p){
cout<<p->data<<" ";
}
void test(){
BiTree T;
InitBiTree(T);
LevelOrder(T);
}
int main(){
test();
return 0;
}
/*
输入数据:
ABD##E##C##
输出数据:
A B C D E
*/
五、中序线索化二叉树
—— 王道只有中序遍历的代码
#include<iostream>
using namespace std;
typedef char ElemType;
typedef struct ThreadNode // 线索二叉树的存储结构
{
ElemType data; // 数据元素
struct ThreadNode *lchild, *rchild; // 左右孩子指针
int ltag, rtag; // 左右线索标志
}ThreadNode,*ThreadTree;
ThreadNode *pre; //指向当前访问节点的前驱
void InitTree(ThreadTree& T); //初始化树
void InThread(ThreadTree T); //中序遍历二叉树,
void CreatInThread(ThreadTree T); //建立中序线索化二叉树
/*中序线索二叉树中找中序后继*/
ThreadNode* Firstnode(ThreadNode* p); //找中序线索二叉树中中序序列下的第一个节点
ThreadNode* Nextnode(ThreadNode* p); //找中序线索二叉树中节点p在中序序列下的后继
void Inorder(ThreadTree T); //遍历线索二叉树
/*中序线索二叉树中找中序前驱*/
ThreadNode* Lastnode(ThreadNode* p); //找到以p为根的子树中,最后一个被中序遍历的节点
ThreadNode* Prenode(ThreadNode* p); //在中序线索二叉树中找到节点p的前驱节点
void RevInorder(ThreadTree T); //逆向遍历线索二叉树
//初始化树
void InitTree(ThreadTree& T){
ElemType ch;
cin>>ch;
if(ch=='#'){
T = NULL;
}else{
T = (ThreadNode*)malloc(sizeof(ThreadNode));
T->data = ch;
T->ltag = 0;
T->rtag = 0;
InitTree(T->lchild);
InitTree(T->rchild);
}
}
// 通过中序遍历对二叉树线索化的递归
void InThread(ThreadTree &p, ThreadTree &pre)
{
if(p != NULL)
{
InThread(p->lchild, pre); // 递归,线索化左子树
if(q->lchild==NULL) // 左子树为空,建立前驱搜索
{
q->lchild = pre;
q->ltag = 1;
}
if(pre != NULL && pre->rchild == NULL)
{
pre->rchild = p; // 建立前驱节点的后续线索
pre->rtag = 1;
}
pre = p; // 标记当前结点成为刚刚访问过的结点
InThread(p->rchild, pre); // 递归,线索化右子树
} // if(p != NULL)
}
// 通过中序遍历建立线索二叉树
void CreatInThread(ThreadTree T)
{
ThreadTree pre = NULL;
if(T != NULL) // 非空二叉树,线索化
{
InThread(T, pre); // 线索化二叉树
pre->rchild == NULL; //处理遍历的最后一个节点
pre->rtag = 1;
}
}
/*↓ 一、中序线索二叉树中找中序后继 ↓*/
//找中序线索二叉树中中序序列下的第一个节点
ThreadNode* Firstnode(ThreadNode* p){
while(p->ltag == 0) p = p->lchild; //最左下节点(不一定是叶节点)
return p;
}
//找中序线索二叉树中节点p在中序序列下的后继
ThreadNode* Nextnode(ThreadNode* p){
if(p->rtag == 0) return Firstnode(p->rchild);
return p->rchild; //rtag==1直接返回后继线索
}
// 不含头结点的中序线索二叉树的中序遍历
void Inorder(ThreadTree T){
for(ThreadNode* p = Firstnode(T); p != NULL; p = Nextnode(p)){
cout<< p->data <<" ";
}
cout<<endl;
}
/*↑--------------------------↑*/
/*↓ 二、中序线索二叉树中找中序前驱 ↓*/
//找到以p为根的子树中,最后一个被中序遍历的节点
ThreadNode* Lastnode(ThreadNode* p){
//循环找到最右下节点(不一定是叶节点)
while(p->rtag == 0) p = p->rchild;
return p;
}
//在中序线索二叉树中找到节点p的前驱节点
ThreadNode* Prenode(ThreadNode* p){
//左子树中最右下节点
if(p->ltag == 0) return Lastnode(p->lchild);
return p->lchild; //ltag==1直接返回前驱
}
//逆向遍历线索二叉树
void RevInorder(ThreadTree T){
for(ThreadNode* p = Lastnode(T);p!=NULL;p = Prenode(p)){
cout<<p->data<<" ";
}
cout<<endl;
}
/*↑--------------------------↑*/
void test(){
ThreadTree T;
T =(ThreadNode*)malloc(sizeof(ThreadNode));
InitTree(T);
CreatInThread(T);
Inorder(T);
RevInorder(T);
}
int main(){
test();
return 0;
}
/*
输入数据:
ABD##E##C##
输出数据:
D B E A C
C A E B D
*/
六、先序线索化二叉树
—— 王道书没有,作为扩展时看
#include<iostream>
using namespace std;
typedef char ElemType;
typedef struct ThreadNode{
ElemType data;
struct ThreadNode *lchild,*rchild;
int ltag,rtag;
}ThreadNode,*ThreadTree;
ThreadNode *pre; //指向当前访问节点的前驱
void InitTree(ThreadTree& T);//初始化树
void visit(ThreadNode* q);
void PreThread(ThreadTree T);//先序遍历二叉树,
void CreatInThread(ThreadTree T);//建立先序线索化二叉树
/*--------------------------*/
/*先序线索二叉树中找先序后继*/
ThreadNode* Firstnode(ThreadNode* p);//找先序线索二叉树中先序序列下的第一个节点
ThreadNode* Nextnode(ThreadNode* p);//找先序线索二叉树中节点p在先序序列下的后继
void Preorder(ThreadTree T);//遍历线索二叉树
/*--------------------------*/
//初始化树
void InitTree(ThreadTree& T){
ElemType ch;
cin>>ch;
if(ch=='#'){
T = NULL;
}else{
T = (ThreadNode*)malloc(sizeof(ThreadNode));
T->data = ch;
T->ltag = 0;
T->rtag = 0;
InitTree(T->lchild);
InitTree(T->rchild);
}
}
void visit(ThreadNode* q){
if(q->lchild==NULL){ //左子树为空,建立前驱线索
q->lchild = pre;
q->ltag =1;
}
if(pre!=NULL && pre->rchild == NULL){ //建立前驱节点的后续线索
pre->rchild = q;
pre->rtag = 1;
}
pre = q;
}
//先序遍历二叉树,
void PreThread(ThreadTree T){
if(T!=NULL){
visit(T);
if(T->ltag!=1) //lchild不是前驱节点
PreThread(T->lchild);
if(T->rtag!=1) //rchild不是后驱节点,因为回溯回来可能造成死循环
PreThread(T->rchild);
}
}
//建立先序线索化二叉树
void CreatInThread(ThreadTree T){
pre = NULL;
if(T!=NULL){
PreThread(T); //先序线索化二叉树
if(pre->rchild == NULL){
pre->rtag = 1; //处理遍历的最后一个节点
}
}
}
/*--------------------------*/
/*先序线索二叉树中找先序后继*/
//找先序线索二叉树中节点p在先序序列下的后继
ThreadNode* Nextnode(ThreadNode* p){
if(p->rtag == 0){
if(p->lchild!=NULL) return p->lchild;
return p->rchild;
}
return p->rchild; //rtag==1直接返回后继线索
}
//遍历线索二叉树
void Preorder(ThreadTree T){
for(ThreadNode* p=T;p!=NULL;p = Nextnode(p)){
cout<<p->data<<" ";
}
cout<<endl;
}
/*--------------------------*/
void test(){
ThreadTree T;
T =(ThreadNode*)malloc(sizeof(ThreadNode));
InitTree(T);
CreatInThread(T);
Preorder(T);
}
int main(){
test();
return 0;
}
/*
输入数据:
ABD##E##C##
ABC####
输出数据:
A B D E C
A B C
*/
7 后序线索化二叉树
#include<iostream>
using namespace std;
typedef char ElemType;
typedef struct ThreadNode{
ElemType data;
struct ThreadNode *lchild,*rchild;
int ltag,rtag;
}ThreadNode,*ThreadTree;
ThreadNode *pre; //指向当前访问节点的前驱
void InitTree(ThreadTree& T);//初始化树
void visit(ThreadNode* q);
void PostThread(ThreadTree T);//后序遍历二叉树,
void CreatInThread(ThreadTree T);//建立后序线索化二叉树
/*--------------------------*/
/*后序线索二叉树中找后序前驱*/
ThreadNode* Prenode(ThreadNode* p);//找后序线索二叉树中节点p在后序序列下的前驱
void RevPostorder(ThreadTree T);//逆向遍历线索二叉树
/*--------------------------*/
//初始化树
void InitTree(ThreadTree& T){
ElemType ch;
cin>>ch;
if(ch=='#'){
T = NULL;
}else{
T = (ThreadNode*)malloc(sizeof(ThreadNode));
T->data = ch;
T->ltag = 0;
T->rtag = 0;
InitTree(T->lchild);
InitTree(T->rchild);
}
}
void visit(ThreadNode* q){
if(q->lchild==NULL){ //左子树为空,建立前驱线索
q->lchild = pre;
q->ltag =1;
}
if(pre!=NULL && pre->rchild == NULL){ //建立前驱节点的后续线索
pre->rchild = q;
pre->rtag = 1;
}
pre = q;
}
//后序遍历二叉树,
void PostThread(ThreadTree T){
if(T!=NULL){
PostThread(T->lchild);
PostThread(T->rchild);
visit(T);
}
}
//建立后序线索化二叉树
void CreatInThread(ThreadTree T){
pre = NULL;
if(T!=NULL){
PostThread(T); //后序线索化二叉树
if(pre->rchild == NULL){
pre->rtag = 1; //处理遍历的最后一个节点
}
}
}
/*--------------------------*/
/*后序线索二叉树中找后序前驱*/
//找后序线索二叉树中节点p在后序序列下的前驱
ThreadNode* Prenode(ThreadNode* p){
if(p->ltag == 0){
if(p->rchild!=NULL) return p->rchild;
return p->lchild;
}
return p->lchild; //ltag==1直接返回前驱线索
}
//逆向遍历线索二叉树
void RevPostorder(ThreadTree T){
for(ThreadNode* p=T;p!=NULL;p = Prenode(p)){
cout<<p->data<<" ";
}
cout<<endl;
}
/*--------------------------*/
void test(){
ThreadTree T;
T =(ThreadNode*)malloc(sizeof(ThreadNode));
InitTree(T);
CreatInThread(T);
RevPostorder(T);
}
int main(){
test();
return 0;
}
/*
输入数据:
ABD##E##C##
输出数据:
A C B E D
*/
8 平衡二叉树AVL
/*
这个代码还没完善
*/
#include<iostream>
using namespace std;
typedef struct BSTNode{
int key;
struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree;
BSTNode *BST_Search(BSTree T,int key);//递归实现查找
BSTNode *BSTSearch(BSTree T,int key);//非递归实现查找
bool BST_Insert(BSTree &T,int k);//递归实现插入
bool BSTInsert(BSTree &T,int k);//非递归实现插入
void Creat_BST(BSTree &T,int str[],int n);//构造二叉树
//递归实现
BSTNode *BST_Search(BSTree T,int key){
while(T!=NULL&&key!=T->key){
if(key>T->key){
T = T->rchild;
}else{
T = T->lchild;
}
}
return T;
}
//非递归实现
BSTNode *BSTSearch(BSTree T,int key){
if(T==NULL) return NULL;
if(T->key==key) return T;
if(key>T->key) return BSTSearch(T->rchild,key);
if(key<T->key) return BSTSearch(T->lchild,key);
}
//递归实现插入
bool BST_Insert(BSTree &T,int k){
if(T==NULL){
T = (BSTNode*)malloc(sizeof(BSTNode));
T->key = k;
T->lchild = T->rchild = NULL;
return true; //插入成功
}else if(T->key == k){
return false; //插入失败
}else if(key>T->key){
return BST_Insert(T->rchild,key);
}else{
return BST_Insert(T->lchild,key);
}
}
//非递归实现插入
bool BSTInsert(BSTree &T,int k){
BSTree p = T;
BSTree pre = NULL; //p的父节点,方便查找后插入
while(p!=NULL){
pre = p;
if(p->key == key) return false;
else if(p->key > key){
p = p->lchild;
}else{
p = p->rchild;
}
}
p = (BSTNode*)malloc(sizeof(BSTNode));
p->key = k;
p->lchild = p->rchild = NULL;
if(pre == NULL) T = p; //树为空
else if(k<pre->key){
pre->lchild = p;
}else{
pre->rchild = p;
}
return true;
}
//构造二叉树
void Creat_BST(BSTree &T,int str[],int n){
T = NULL;
for(int i=0;i<n;i++){
BST_Insert(T,str[i]);
}
}
void test(){
}
int main(){
test();
return 0;
}