基于左子结点/右兄弟结点表示法和二叉链表来实现二叉树ADT

实现二叉树的ADT需要分别实现结点ADT和树ADT，同时也要保证其封装性

二叉链表

树结点ADT的声明以及实现

（1）每一个结点包括其要储存的数据以及左右子节点的指针，通常一颗二叉树中只有根结点能被直接访问，所以要把数据以及子节点的指针设为private

（2）成员函数要包括：

  • 构造函数，析构函数（也可以不写）
  • 获取和设置结点内储存的数据，左子节点，右子节点　　　
  • 判断该节点是否为叶子节点
 1 #ifndef _BINNODE_HPP_
 2 #define _BINNODE_HPP_
 3 #include<iostream>
 4 using namespace std;
 5 class BinNode{
 6     private:
 7             char data;
 8             BinNode *lc;
 9             BinNode *rc;
10     public:
11             BinNode(char dataval,BinNode *l=NULL,BinNode* r=NULL){data=dataval;lc=l;rc=r;}
12             BinNode(BinNode *l=NULL,BinNode* r=NULL){lc=l;rc=r;}
13             void setLeftChild(BinNode *l){lc=l;}
14             void setRightChild(BinNode *r){rc=r;}
15             void setdata(char d){data=d;}
16             BinNode *getlc(){return lc;}
17             BinNode *getrc(){return rc;}
18             char getdata(){return data;}
19             bool isLeaf(){return lc==NULL&&rc==NULL;}
20 };    
21 #endif

树ADT的声明

成员变量：根结点

基本操作：获取树的高度，结点数目，前序/中序/后序遍历，设置根节点的值，撤销整棵树

 1 #ifndef _BINTREE_HPP_
 2 #define _BINTREE_HPP_
 3 #include "BinNode.hpp"
 4 #include <iostream>
 5 using namespace std;
 6 class BinTree{
 7     public:
 8             BinNode * root;
 9             int depth(BinNode*);
10             int count(BinNode*);
11             void setroot(BinNode*);
12             void clear(BinNode*);
13             void preorder(BinNode*,void(*visit)(BinNode*));
14             void inorder(BinNode*,void(*visit)(BinNode*));
15             void postorder(BinNode*,void(*visit)(BinNode*));
16 };
17 #endif

树ADT的实现

树很多操作都需要用到递归，学会运用递归是实现这些基本操作的必要条件

而递归可以使用栈来模拟，所以只要理解好了栈就很好理解递归操作了，这里就不赘述了

前序遍历：根节点->左子树->右子树

中序遍历：左子树->根节点->右子树

后序遍历：左子树->右子树->根节点

这三种遍历实现方法大同小异，不同点就在于访问的先后顺序不同罢了

简单的描述一下过程（尝试用栈的知识去理解，先进先出）：把递归函数看作是一个元素，若要执行某一层的递归函数，则将该函数入栈，如果函数执行过程中碰到终止条件则终止函数进程即弹栈，反复进行直到栈为空，即所有的函数都被执行完

获取树的高度以及结点的个数也要使用递归，代码的也大同小异

#include "BinTree.hpp"
void BinTree::preorder(BinNode* r,void (*visit)(BinNode* c)){
    if(r==NULL)return ;
    visit(r);
    preorder(r->getlc(),visit);
    preorder(r->getrc(),visit);
}
void BinTree::inorder(BinNode* r,void (*visit)(BinNode* c)){
    if(r==NULL)return ;
    inorder(r->getlc(),visit);
    visit(r);
    inorder(r->getrc(),visit);
}
void BinTree::postorder(BinNode* r,void (*visit)(BinNode* c)){
    if(r==NULL)return ;
    postorder(r->getlc(),visit);
    postorder(r->getrc(),visit);
    visit(r);
}
void BinTree::setroot(BinNode* r){
    root=r;
}
void BinTree::clear(BinNode*r){
    if(r==NULL)return;
    clear(r->getlc());
    clear(r->getrc());
    delete r;
}
int BinTree::depth(BinNode* r){
    int lh=0,rh=0;
    if(r!=NULL)
    {
        lh=depth(r->getlc());
        rh=depth(r->getrc());
        return (lh>rh?lh:rh)+1;
     } 
    else return 0;
}
int BinTree::count(BinNode*r){
    if(r==NULL)return 0;
    return (count(r->getlc())+count(r->getrc()))+1;
}

 demo程序

此部分首先碰到的问题就是如何构造一个二叉树了，构造二叉树有很多种方法，这里采用前序遍历的方法来实现

 1 #include"BinTree.hpp"
 2 #include"BinTree.cpp"
 3 #include<iostream>
 4 #include<stdio.h>
 5 #include<stdlib.h>
 6 using namespace std;
 7 BinNode* r;
 8 BinTree T;
 9 char s[1000];
10 int cnt=0;
11 void visit(BinNode*r);
12 BinNode * creatTree(char c);
13 void input();
14 int main()
15 {
16     input();
17     printf("输出树的深度：");
18     printf("%d",T.depth(r));
19     printf("
");
20     printf("输出树的结点个数："); 
21     printf("%d",T.count(r));
22     printf("
");
23     printf("按前序遍历输出结果
");
24     T.preorder(r,visit);
25     printf("
");
26     printf("按中序遍历输出结果
");
27     T.inorder(r,visit);
28     printf("
");
29     printf("按后序遍历输出结果
");
30     T.postorder(r,visit);
31     printf("
");
32     return 0;
33 }
34 void visit(BinNode*r){
35     printf("%c",r->getdata());
36 }
37 BinNode * creatTree(char c){
38     BinNode* temp;
39     if(c=='/') temp=NULL;
40     else
41     {
42         temp=new BinNode;
43         temp->setdata(c);
44         c=s[++cnt];
45         temp->setLeftChild(creatTree(c));
46         c=s[++cnt];
47         temp->setRightChild(creatTree(c));
48     }
49     T.setroot(temp);
50     return temp; 
51 }
52 void input(){
53     printf("输入的注意事项
");
54     printf("（1）使用前序遍历的顺序输入
");
55     printf("（2）空节点以'/'替代
");
56     printf("（3）输入只有一行
");
57     printf("（4）输入的数据类型都为char
");
58     printf("（5）输入样例：AB/D//CEG///FH//I//

");
59     printf("请输入二叉树
"); 
60     scanf("%s",s);
61     r=creatTree(s[0]);
62 }

左子节点右兄弟节点

树节点ADT

成员变量：节点存储的数据，左子节点的指向，父节点的指向，右兄弟节点的指向

成员函数：跟二叉链表很相似，都包括构造函数，获取，设置函数，但是少了判断是否为叶子节点的函数，因为仅仅根据以上已知的东西无法判断是否为叶子节点

 1 #ifndef _BINNODE_HPP_
 2 #define _BINNODE_HPP_
 3 #include <iostream>
 4 using namespace std;
 5 class BinNode{
 6     private:
 7         char data;
 8         int parent;
 9         int lc;
10         int rightbro;
11     public:
12         BinNode(){data='/';parent=-1;lc=-1;rightbro=-1;}
13         void setdata(char d){data=d;}
14         void setparent(int p){parent=p;}
15         void setLc(int l){lc=l;}
16         void setRightbro(int r){rightbro=r;}
17         char getData(){return data;}
18         int getParent(){return parent;}
19         int getLc(){return lc;}
20         int getRightbro(){return rightbro;}
21 };
22 #endif

树ADT的声明

与二叉链表大同小异，只是实现的方法不同罢了，这里不多加赘述了

 1 #ifndef _BINTREE_HPP_
 2 #define _BINTREE_HPP_
 3 #include "BinNode.hpp"
 4 #include <iostream>
 5 using namespace std;
 6 class BinTree{
 7     public:
 8         BinNode node[1024+10];
 9         int depth(int );
10         int count(int );
11         void preorder(int ,void(*visit)(BinNode no));
12         void inorder(int ,void(*visit)(BinNode no));
13         void postorder(int ,void(*visit)(BinNode no));
14 };
15 #endif

树ADT的实现

这里注意一个问题：

遍历操作的终止条件多了一项，因为左子节点右兄弟节点使用数组来实现的，所以数组的下标有很大的作用，稍不注意就可能越界

 1 #include "BinTree.hpp"
 2 void BinTree::preorder(int n,void(*visit)(BinNode no)){
 3     if(node[n].getData()=='/'||n==-1)return;
 4     visit(node[n]);
 5     preorder(node[n].getLc(),visit);
 6     preorder(node[node[n].getLc()].getRightbro(),visit);
 7 }
 8 void BinTree::inorder(int n,void(*visit)(BinNode no)){
 9     if(node[n].getData()=='/'||n==-1)return;    
10     inorder(node[n].getLc(),visit);
11     visit(node[n]);
12     inorder(node[node[n].getLc()].getRightbro(),visit);
13 }
14 void BinTree::postorder(int n,void(*visit)(BinNode no)){
15     if(node[n].getData()=='/'||n==-1)return;    
16     postorder(node[n].getLc(),visit);
17     postorder(node[node[n].getLc()].getRightbro(),visit);
18     visit(node[n]);
19 }
20 int BinTree::count(int n){
21     if(node[n].getData()=='/'||n==-1)return 0;
22     return count(node[n].getLc())+count(node[node[n].getLc()].getRightbro())+1;
23 }
24 int BinTree::depth(int n){
25     if(node[n].getData()=='/'||n==-1)return 0;
26     int lh=depth(node[n].getLc());
27     int rh=depth(node[node[n].getLc()].getRightbro());
28     return (lh>rh?lh:rh)+1;
29 }

demo程序

（1）在构造一颗二叉树时使用的是按层次遍历的顺序，使用其他的顺序都不好构造

（2）在构造函数的时候，注意可以利用二叉树的性质，比如左节点的下标一定是奇数，左子节点的下标与父节点的下标之间的关系，兄弟节点之间下标之间的关系

弄清楚这些后就很容易的按照层次遍历的顺序构造好一颗二叉树

我比较懒，这里就没有考虑父节点的指向了

 1 #include "BinTree.hpp"
 2 #include "BinTree.cpp"
 3 #include<iostream>
 4 #include<stdio.h>
 5 #include<stdlib.h>
 6 #include<cstring>
 7 using namespace std;
 8 char s[1000];
 9 int cnt=0;
10 BinTree T;
11 int n=0,m=0;
12 void visit(BinNode n){
13     printf("%c",n.getData());
14 }
15 void creatTree(BinTree &t){
16     for(int i=0;i<=1024;i++){
17         t.node[i].setdata('/');
18     }
19     for(int i=0;s[i]!='';i++){
20         t.node[i].setdata(s[i]);
21         if(s[i]=='/')continue;
22         t.node[i].setLc((2*i)+1);
23         if((i+1)%2==0&&i!=0)t.node[i].setRightbro(i+1);
24     }
25 }
26 void input(){
27     printf("输入的注意事项
");
28     printf("（1）使用层次遍历的顺序输入
");
29     printf("（2）空节点以'/'替代
");
30     printf("（3）输入只有一行
");
31     printf("（4）输入的数据类型都为char
");
32     printf("（5）输入的树的结点要么是叶子结点要么必有左子结点
");
33     printf("（7）输入样例ABCD/E/FG//HI//

");
34     printf("请输入二叉树
"); 
35     scanf("%s",s);
36     creatTree(T);
37 }
38 int main()
39 {
40         input();
41         printf("输出树的深度：");
42         printf("%d",T.depth(0));
43         printf("
");
44         printf("输出树的结点个数："); 
45         printf("%d",T.count(0));
46         printf("
");
47         printf("按前序遍历输出结果
");
48         T.preorder(0,visit);
49         printf("
");
50         printf("按中序遍历输出结果
");
51         T.inorder(0,visit);
52         printf("
");
53         printf("按后序遍历输出结果
");
54         T.postorder(0,visit);
55         printf("
");
56         return 0;
57 }
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/bo2000/p/9955876.html