二叉树的详细实现 (C++)

2019/05/13 21:11
阅读数 34

二叉树的定义

    以递归形式给出的:一棵二叉树是结点的一个有限集合,该集合或者为空,或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。二又树的特点是每个结点最多有两个子女,分别称为该结点的左子女和右子女。在二又树中不存在度大于2的结点,并且二又树的子树有左、右之分,其子树的次序不能颠倒。二又树是分支数最大不超过2的有根有序树。它可能有5种不同的形态。

二叉树的性质

 

二叉树的数组存储方式

 

    遇到空子树,应在编号时假定有此子树进行编号,而在顺序存储时当作有此子树那样把位置留出来。这样才能反映二叉树结点之间的相互关系,由其存储位置找到它的父结点、子女、兄弟结点的位置。但这样做有可能会消耗大量的存储空间。例如:单支二叉树,会浪费很多空间。

 
如果根节点编号是从1开始有有以下结论:
    中间节点一定在倒数第二层,最后一个节点的数就是总节点的个数,总结点数除2就是中间节点的数的个数,父节点的节点数*2<总节点个数,当前节点一定有两个孩子,如果=就只有一个孩子,如果<就没有一个孩子。

二叉树的链表存储表示

 

二叉树结点类型的定义

1 template<typename T>
2 struct BinTreeNode
3 {
4     T data;    //结点中存储的数据
5     BinTreeNode<T> *leftChild, *rightChild;    //左子树和右子树
6     BinTreeNode() :leftChild(NULL), rightChild(NULL) {}    //无参构造函数
7     BinTreeNode(T x, BinTreeNode<T> *l = NULL, BinTreeNode<T> *r = NULL) :data(x), leftChild(l), rightChild(r) {}    //带默认值的有参构造参数
8 };

二叉树的基本框架

 

//二叉树

//结点类型
template <typename T>
struct BinTreeNode
{
    T data;                                                                                                        //结点中存储的数据
    BinTreeNode<T> *leftChild, *rightChild;                                                                        //左子树和右子树
    BinTreeNode() : leftChild(NULL), rightChild(NULL) {}                                                           //无参构造函数
    BinTreeNode(T x, BinTreeNode<T> *l = NULL, BinTreeNode<T> *r = NULL) : data(x), leftChild(l), rightChild(r) {} //带默认值的有参构造参数
};

//二叉树类
template <typename T>
class BinaryTree
{
public:

//==========二叉树构造与析构==========//

    //构造函数
    BinaryTree() : root(NULL) {}

    //指定结束标志的构造函数
    BinaryTree(T value) : RefValue(value), root(NULL) {}

    //析构函数
    ~BinaryTree() { Destroy(root); }

//==========二叉树的创建==========//

    //使用广义表创建二叉树,以'#'字符代表结束
    void CreateBinTree() { CreateBinTree(root); }

    //前序遍历创建二叉树(前序遍历的应用),用#表示空结点
    void CreateBinTree_PreOrder() { CreateBinTree_PreOrder(root); }

    //使用先序遍历和中序遍历创建二叉树
    void CreateBinTreeBy_Pre_In(const char *pre, const char *in)
    {
        int n = strlen(pre);
        CreateBinTreeBy_Pre_In(root, pre, in, n);
    }

    //使用后序遍历和中序遍历创建二叉树
    void CreateBinTreeBy_Post_In(const char *post, const char *in)
    {
        int n = strlen(post);
        CreateBinTreeBy_Post_In(root, post, in, n);
    }

//==========二叉树的遍历==========//

    //先序遍历(递归)
    void PreOrder() { PreOrder(root); }

    //中序遍历(递归)
    void InOrder() { InOrder(root); }

    //后序遍历(递归)
    void PostOrder() { PostOrder(root); }

    //先序遍历(非递归)
    void PreOrder_NoRecurve() { PreOrder_NoRecurve(root); }

    //中序遍历(非递归)
    void InOrder_NoRecurve() { InOrder_NoRecurve(root); }

    //后序遍历(非递归)
    void PostOrder_NoRecurve() { PostOrder_NoRecurve(root); }

    //层次遍历(非递归)
    void LevelOrder() { LevelOrder(root); }

//==========获取结点==========//

    //获取二叉树的根节点
    BinTreeNode<T> *getRoot() const
    {
        return root;
    }

    //获取current结点的父节点
    BinTreeNode<T> *Parent(BinTreeNode<T> *current)
    {
        return (root == NULL || root == current) ? NULL : Parent(root, current); //如果没有根节点或current结点就是root结点,就没有父节点
    }

    //获取current结点的左结点
    BinTreeNode<T> *LeftChild(BinTreeNode<T> *current)
    {
        return (current != NULL) ? current->leftChild : NULL;
    }

    //获取current结点的右结点
    BinTreeNode<T> *RightChild(BinTreeNode<T> *current)
    {
        return (current != NULL) ? current->rightChild : NULL;
    }
    
//==========成员函数==========//

    //销毁函数
    void Destroy() { Destroy(root); }

    //拷贝二叉树(前序遍历的应用)
    BinaryTree(BinaryTree<T> &s)
    {
        root = Copy(s.getRoot());
    }

    //判断两颗二叉树是否相等(前序遍历的应用)
    bool operator==(BinaryTree<T> &s)
    {
        return (equal(this->getRoot(), s.getRoot()));
    }

    //计算二叉树的结点的个数(后序遍历的应用)
    int Size() { return Size(root); }

    //计算二叉树的高度(后序遍历的应用)
    int Height() { return Height(root); }

    //判断二叉树是否为空
    bool Empty() { return (root == NULL) ? true : false; }

    //以广义表的形式输出二叉树(前序遍历的应用)
    void PrintBinTree() { PrintBinTree(root); }

private:
    BinTreeNode<T> *root; //根节点
    T RefValue;           //数据输入停止的标志,需要一个构造函数
};

 

二叉树的创建

  1.使用广义表创建

从广义表 A(B(D,E(G,)),C(,F))# 建立起来的二叉树。
 
算法基本思路:
  1.若是字母(假定以字母作为结点的值),则表示是结点的值,为它建立一个新的结点,并把该结点作为左子女(当k=1)或右子女(当k=2)链接到其父结点上。
  2.若是左括号"(",则表明子表的开始,将k置为1;若遇到的是右括号")",则表明子表结束。
  3.若遇到的是逗号",",则表示以左子女为根的子树处理完毕,应接着处理以右子女为根的子树,将k置为2。如此处理每一个字符,直到读入结束符“#”为止。
在算法中使用了一个栈s,在进入子表之前将根结点指针进栈,以便括号内的子女链接之用。在子表处理结束时退栈。
 
 1     //使用广义表创建二叉树函数,这里以“字符”创建二叉树,以'#'字符代表结束
 2     void CreateBinTree(BinTreeNode<T>* &BT)
 3     {
 4         stack< BinTreeNode<T>* > s;
 5         BT = NULL;
 6         BinTreeNode<T> *p, *t;    //p用来记住当前创建的节点,t用来记住栈顶的元素
 7         int k;    //k是处理左、右子树的标记
 8         T ch;
 9         cin >> ch;
10 
11         while (ch != RefValue)
12         {
13             switch (ch)
14             {
15             case '(':    //对(做处理
16                 s.push(p);
17                 k = 1;
18                 break;
19 
20             case ')':    //对)做处理
21                 s.pop();
22                 break;
23 
24             case ',':    //对,做处理
25                 k = 2;
26                 break;
27 
28             default:
29                 p = new BinTreeNode<T>(ch);    //构造一个结点
30                 if (BT == NULL)    //如果头节点是空
31                 {
32                     BT = p;
33                 }
34                 else if (k == 1)    //链入*t的左孩子
35                 {
36                     t = s.top();
37                     t->leftChild = p;
38                 }
39                 else    //链入*t的右孩子
40                 {
41                     t = s.top();
42                     t->rightChild = p;
43                 }
44             }
45             cin >> ch;
46         }
47     }

   2.使用已知的二叉树的前序遍历创建

  必须对应二又树结点前序遍历的顺序,并约定以输入序列中不可能出现的值作为空结点的值以结束递归,此值通过构造函数存放在RefValue中。例如用“#”或表示字符序列或正整数序列空结点。
 
  前序遍历所得到的前序序列为ABC##DE#G##F###。
算法的基本思想是:
  每读入一个值,就为它建立结点。该结点作为根结点,其地址通过函数的引用型参数subTree直接链接到作为实际参数的指针中。然后,分别对根的左、右子树递归地建立子树,直到读入“#”建立空子树递归结束。
 
 1     //创建二叉树(利用已知的二叉树的前序遍历创建)用#表示空结点
 2     void CreateBinTree_PreOrder(BinTreeNode<T>* &subTree)
 3     {
 4         T item;
 5         if (cin >> item)
 6         {
 7             if (item != RefValue)
 8             {
 9                 subTree = new BinTreeNode<T>(item);    //构造结点
10                 if (subTree == NULL)
11                 {
12                     cout << "空间分配错误!" << endl;
13                     exit(1);
14                 }
15                 CreateBinTree_PreOrder(subTree->leftChild);    //递归创建左子树
16                 CreateBinTree_PreOrder(subTree->rightChild);    //递归创建右子树
17             }
18             else
19             {
20                 subTree == NULL;
21             }
22         }
23     }

    3.根据已知的前序遍历和中序遍历创建二叉树

        根据前序遍历,先找到这棵树的根节点,也就是数组受中第一个结点的位置,创建根节点。

        然后在中序遍历中找到根的值所在的下标,切出左右子树的前序和中序

        注意:如果前序遍历的数组长度为0,说明是一棵空树。

举例:

首先可以确定A是这棵树的根节点,然后根据中序遍历切出A的左右子树,得到BCD属于A的左子树,E属于A的右子树,如下图:

接着以B为根节点,在中序遍历中再次切出B的左右子树,得到CD为B的左子树,右子树为空。

再以C为根节点,结合中序遍历,得到D为C的右子树,左子树为空。

创建好的二叉树如下图所示:

 

 1     //使用先序遍历和中序遍历创建二叉树
 2     void CreateBinTreeBy_Pre_In(BinTreeNode<T> *&cur, const char *pre, const char *in, int n)
 3     {
 4         if (n <= 0)
 5         {
 6             cur = NULL;
 7             return;
 8         }
 9         int k = 0;
10         while (pre[0] != in[k]) //再中序中找到pre[0]的值
11         {
12             k++;
13         }
14         cur = new BinTreeNode<T>(in[k]); //创建结点
15         CreateBinTreeBy_Pre_In(cur->leftChild, pre + 1, in, k);
16         CreateBinTreeBy_Pre_In(cur->rightChild, pre + k + 1, in + k + 1, n - k - 1);
17     }

 

    4.根据已知的后续遍历和中序遍历创建二叉树

        根据后序遍历,先找到这棵树的根节点的值,也就是数组中最后一个节点(数组长度-1)的位置,由此创建根节点。
        然后在中序遍历中找到根的值所在的下标,切出左右子树的后续和中序。
        注意:如果后序遍历的数组长度为0,说明是一棵空树。

举例:

由后序遍历可以确定A是这棵树的根节点,然后根据中序遍历切出A的左右子树,得到CDB属于A的左子树,E属于A的右子树,如下图:

接着以B为根节点,在中序遍历中再次切出B的左右子树,得到CD为B的左子树,右子树为空。

再以C为根节点,结合中序遍历,得到D为C的右子树,左子树为空。

创建好的二叉树如下图所示:

 1 //使用后序遍历和中序遍历创建二叉树
 2     void CreateBinTreeBy_Post_In(BinTreeNode<T> *&cur, const char *post, const char *in, int n)
 3     {
 4         if (n == 0)
 5         {
 6             cur = NULL;
 7             return;
 8         }
 9 
10         char r = *(post + n - 1);    //根结点值
11         cur = new BinTreeNode<T>(r); //构造当前结点
12 
13         int k = 0;
14         const char *p = in;
15         while (*p != r)
16         {
17             k++;
18             p++;
19         }
20         CreateBinTreeBy_Post_In(cur->leftChild, post, in, k);
21         CreateBinTreeBy_Post_In(cur->rightChild, post + k, p + 1, n - k - 1);
22     }

 

二叉树的递归遍历

  先序遍历:根->左->右

 1     //二叉树的先序遍历
 2     void PreOrder(BinTreeNode<T> *&subTree)
 3     {
 4         if (subTree != NULL)
 5         {
 6             cout << subTree->data << " ";
 7             PreOrder(subTree->leftChild);
 8             PreOrder(subTree->rightChild);
 9         }
10     }

  中序遍历:左->根->右

 1     //二叉树的中序遍历
 2     void InOrder(BinTreeNode<T> *&subTree)
 3     {
 4         if (subTree != NULL)
 5         {
 6             InOrder(subTree->leftChild);
 7             cout << subTree->data << " ";
 8             InOrder(subTree->rightChild);
 9         }
10     }

  后续遍历:左->右->根

 1     //二叉树的后序遍历
 2     void PostOrder(BinTreeNode<T> *&subTree)
 3     {
 4         if (subTree != NULL)
 5         {
 6             PostOrder(subTree->leftChild);
 7             PostOrder(subTree->rightChild);
 8             cout << subTree->data << " ";
 9         }
10     }

 二叉树的非递归遍历

  先序遍历

  为了把一个递归过程改为非递归过程,一般需要利用一个工作栈,记录遍历时的回退路径。
 

  利用栈实现前序遍历的过程。每次访问一个结点后,在向左子树遍历下去之前,利用这个栈记录该结点的右子女(如果有的话)结点的地址,以便在左子树退回时可以直接从栈顶取得右子树的根结点,继续其右子树的前序遍历。

 
 1     //二叉树先序遍历(非递归1)
 2     void PreOrder_NoRecurve1(BinTreeNode<T> *p)
 3     {
 4         stack<BinTreeNode<T>*> S;
 5         S.push(NULL);    //最先push一个NULL,到最后一个结点没有左右子树时,栈里只有一个NULL了,令指针p指向这个NULL,再判断就会结束循环
 6         while (p!=NULL)
 7         {
 8             cout << p->data << " ";
 9             if(p->rightChild!=NULL)    //预留右子树指针在栈中
10             {
11                 S.push(p->rightChild);
12             }
13 
14             if (p->leftChild!=NULL)    //进左子树
15             {
16                 p = p->leftChild;
17             }
18             else    //左子树为空
19             {
20                 p = S.top();
21                 S.pop();
22             }
23         }
24     }

     另一种前序遍历的方法。为了保证先左子树后右子树的顺序,在进栈时是先进右子女结点地址,后进左子女结点地址,出栈时正好相反。

 1     //二叉树先序遍历(非递归2)
 2     void PreOrder_NoRecurve2(BinTreeNode<T> *p)
 3     {
 4         stack<BinTreeNode<T>*> S;
 5         BinTreeNode<T>* t;
 6         S.push(p);    //根节点进栈
 7         while (!S.empty())    //当栈不为空
 8         {
 9             t = S.top();    //p先记住栈顶元素,然后栈顶出栈
10             S.pop();
11             cout << t->data << " ";    //访问元素
12             if (t->rightChild != NULL)    //右孩子不为空,右孩子近栈
13             {
14                 S.push(t->rightChild);
15             }
16             if (t->leftChild != NULL)    //左孩子不为空,左孩子进栈
17             {
18                 S.push(t->leftChild);
19             }
20         }
21     }

   中序遍历

  需要使用一个栈,以记录遍历过程中回退的路径。在一棵子树中首先访问的是中序下的第一个结点,它位于从根开始沿leftChild链走到最左下角的结点,该结点的leftChild指针为NULL。访问它的数据之后,再遍历该结点的右子树。此右子树又是二叉树,重复执行上面的过程,直到该子树遍历完。
 
  如果某结点的右子树遍历完或右子树为空,说明以这个结点为根的二叉树遍历完,此时从栈中退出更上层的结点并访问它,再向它的右子树遍历下去。
 1     //二叉树的中序遍历(非递归)
 2     void InOrder_NoRecurve(BinTreeNode<T>* p)
 3     {
 4         stack<BinTreeNode<T>*> S;
 5         do
 6         {
 7             while (p!=NULL)
 8             {
 9                 S.push(p);
10                 p = p->leftChild;
11             }
12             if (!S.empty())
13             {
14                 p = S.top();
15                 S.pop();
16                 cout << p->data << " ";
17                 p = p->rightChild;
18             }
19         }
20         while (p!=NULL||!S.empty());
21     }

  后续遍历

思想:
1、如果栈顶元素非空且左节点存在,将其压入栈中,如果栈顶元素存在左节点,将其左节点压栈,重复该过程。直到左结点不存在则进入第2步
2、判断上一次出栈节点是否是当前栈顶结点的右节点(就是右叶子结点,如:g,f结点),或者当前栈顶结点不存在右结点(如:g,f,a结点),将当前节点输出,并出栈。否则将当前栈顶结点右孩子节点压栈,再进入第1步
 1     //后序遍历(非递归)
 2     void PostOrder_NoRecurve(BinTreeNode<T> *p)
 3     {
 4         if (root == NULL)
 5             return;
 6         stack<BinTreeNode<T> *> s;
 7         s.push(p);
 8         BinTreeNode<T> *lastPop = NULL;
 9         while (!s.empty())
10         {
11             while (s.top()->leftChild != NULL)
12                 s.push(s.top()->leftChild);
13             while (!s.empty())
14             {
15                 //右叶子结点 || 没有右结点
16                 if (lastPop == s.top()->rightChild || s.top()->rightChild == NULL)
17                 {
18                     cout << s.top()->data << " ";
19                     lastPop = s.top();
20                     s.pop();
21                 }
22                 else if (s.top()->rightChild != NULL)
23                 {
24                     s.push(s.top()->rightChild);
25                     break;
26                 }
27             }
28         }
29     }

 

  层次遍历

    按层次顺序访问二叉树的处理需要利用一个队列。在访问二又树的某一层结点时,把下一层结点指针预先记忆在队列中,利用队列安排逐层访问的次序。因此,每当访问一个结点时,将它的子女依次加到队列的队尾,然后再访问已在队列队头的结点。这样可以实现二又树结点的按层访问。
 
 1     //二叉树的层次遍历(非递归遍历)
 2     void LevelOrder(BinTreeNode<T> *p)
 3     {
 4         queue<BinTreeNode<T>*> Q;
 5         Q.push(p);    //根节点进队
 6         BinTreeNode<T>* t;
 7         while (!Q.empty())
 8         {
 9             t = Q.front();    //t先记住队头,再将队头出队
10             Q.pop();
11             cout << t->data << " ";    //访问队头元素的数据
12 
13             if (t->leftChild != NULL)
14             {
15                 Q.push(t->leftChild);
16             }
17 
18             if (t->rightChild != NULL)
19             {
20                 Q.push(t->rightChild);
21             }
22         }
23     }

 二叉树的结点个数

1     //计算二叉树以subTree为根的结点的个数
2     int Size(BinTreeNode<T> *subTree) const
3     {
4         if (subTree == NULL)    //递归结束,空树结点个数为0
5         {
6             return 0;
7         }
8         return 1 + Size(subTree->leftChild) + Size(subTree->rightChild);
9     }

二叉树的高度

 1     //计算二叉数以subTree为根的高度
 2     int Height(BinTreeNode<T> *subTree)
 3     {
 4         if (subTree == NULL)    //递归结束,空树高度为0
 5         {
 6             return 0;
 7         }
 8         int i = Height(subTree->leftChild);
 9         int j = Height(subTree->rightChild);
10         return i < j ? j + 1 : i + 1;
11     }

 以广义表的形式输出二叉树

 1     void PrintBinTree(BinTreeNode<T> *BT)
 2     {
 3         if (BT != NULL)    //树为空时结束递归
 4         {
 5             cout << BT->data;
 6             if (BT->leftChild != NULL || BT->rightChild != NULL)
 7             {
 8                 cout << '(';
 9                 if (BT->leftChild!=NULL)
10                 {
11                     PrintBinTree(BT->leftChild);
12                 }
13                 cout << ',';
14                 if (BT->rightChild != NULL)
15                 {
16                     PrintBinTree(BT->rightChild);
17                 }
18                 cout << ')';
19             }
20         }
21     }

求二叉树某结点的父节点

 1     //从结点subTree开始,搜索结点current的父节点,找到返回父节点的地址,找不到返回NULL
 2     BinTreeNode<T>* Parent(BinTreeNode<T>* subTree, BinTreeNode<T>* current)
 3     {
 4         if (subTree == NULL)
 5         {
 6             return NULL;
 7         }
 8         if (subTree->leftChild == current || subTree->rightChild == current)    //如果找到,返回父节点subTree
 9         {
10             return subTree;
11         }
12         BinTreeNode<T>* p;
13         if (p = Parent(subTree->leftChild, current) != NULL)    //递归在左子树中搜索
14         {
15             return p;
16         }
17         else
18         {
19             return Parent(subTree->rightChild, current);    //递归右子树中搜索
20         }
21     }

二叉树的销毁

 1     //二叉树的销毁函数
 2     void Destroy(BinTreeNode<T> *&subTree)
 3     {
 4         if (subTree != NULL)
 5         {
 6             Destroy(subTree->leftChild);
 7             Destroy(subTree->rightChild);
 8             delete subTree;
 9             subTree = NULL;
10         }
11     }

 判断两颗二叉树是否相等

 1     //判断两颗二叉树是否相等
 2     bool equal(BinTreeNode<T> *a, BinTreeNode<T> *b)
 3     {
 4         if (a == NULL&&b == NULL)    //两者都为空
 5         {
 6             return true;
 7         }
 8         if (a != NULL&&b != NULL&&a->data == b->data&&equal(a->leftChild, b->leftChild) && equal(a->rightChild, b->rightChild))    //两者都不为空,且两者的结点数据相等,且两者的左右子树的结点都相等
 9         {
10             return true;
11         }
12         return false;
13     }

 

 完整代码:
 
  1 //结点类型
  2 template <typename T>
  3 struct BinTreeNode
  4 {
  5     T data;                                                                                                        //结点中存储的数据
  6     BinTreeNode<T> *leftChild, *rightChild;                                                                        //左子树和右子树
  7     BinTreeNode() : leftChild(NULL), rightChild(NULL) {}                                                           //无参构造函数
  8     BinTreeNode(T x, BinTreeNode<T> *l = NULL, BinTreeNode<T> *r = NULL) : data(x), leftChild(l), rightChild(r) {} //带默认值的有参构造参数
  9 };
 10 
 11 //二叉树类
 12 template <typename T>
 13 class BinaryTree
 14 {
 15 public:
 16 
 17 //==========二叉树构造与析构==========//
 18 
 19     //构造函数
 20     BinaryTree() : root(NULL) {}
 21 
 22     //指定结束标志的构造函数
 23     BinaryTree(T value) : RefValue(value), root(NULL) {}
 24 
 25     //析构函数
 26     ~BinaryTree() { Destroy(root); }
 27 
 28 //==========二叉树的创建==========//
 29 
 30     //使用广义表创建二叉树,以'#'字符代表结束
 31     void CreateBinTree() { CreateBinTree(root); }
 32 
 33     //前序遍历创建二叉树(前序遍历的应用),用#表示空结点
 34     void CreateBinTree_PreOrder() { CreateBinTree_PreOrder(root); }
 35 
 36     //使用先序遍历和中序遍历创建二叉树
 37     void CreateBinTreeBy_Pre_In(const char *pre, const char *in)
 38     {
 39         int n = strlen(pre);
 40         CreateBinTreeBy_Pre_In(root, pre, in, n);
 41     }
 42 
 43     //使用后序遍历和中序遍历创建二叉树
 44     void CreateBinTreeBy_Post_In(const char *post, const char *in)
 45     {
 46         int n = strlen(post);
 47         CreateBinTreeBy_Post_In(root, post, in, n);
 48     }
 49 
 50 //==========二叉树的遍历==========//
 51 
 52     //先序遍历(递归)
 53     void PreOrder() { PreOrder(root); }
 54 
 55     //中序遍历(递归)
 56     void InOrder() { InOrder(root); }
 57 
 58     //后序遍历(递归)
 59     void PostOrder() { PostOrder(root); }
 60 
 61     //先序遍历(非递归)
 62     void PreOrder_NoRecurve() { PreOrder_NoRecurve(root); }
 63 
 64     //中序遍历(非递归)
 65     void InOrder_NoRecurve() { InOrder_NoRecurve(root); }
 66 
 67     //后序遍历(非递归)
 68     void PostOrder_NoRecurve() { PostOrder_NoRecurve(root); }
 69 
 70     //层次遍历(非递归)
 71     void LevelOrder() { LevelOrder(root); }
 72 
 73 //==========获取结点==========//
 74 
 75     //获取二叉树的根节点
 76     BinTreeNode<T> *getRoot() const
 77     {
 78         return root;
 79     }
 80 
 81     //获取current结点的父节点
 82     BinTreeNode<T> *Parent(BinTreeNode<T> *current)
 83     {
 84         return (root == NULL || root == current) ? NULL : Parent(root, current); //如果没有根节点或current结点就是root结点,就没有父节点
 85     }
 86 
 87     //获取current结点的左结点
 88     BinTreeNode<T> *LeftChild(BinTreeNode<T> *current)
 89     {
 90         return (current != NULL) ? current->leftChild : NULL;
 91     }
 92 
 93     //获取current结点的右结点
 94     BinTreeNode<T> *RightChild(BinTreeNode<T> *current)
 95     {
 96         return (current != NULL) ? current->rightChild : NULL;
 97     }
 98 
 99 //==========成员函数==========//
100 
101     //销毁函数
102     void Destroy() { Destroy(root); }
103 
104     //拷贝二叉树(前序遍历的应用)
105     BinaryTree(BinaryTree<T> &s)
106     {
107         root = Copy(s.getRoot());
108     }
109 
110     //判断两颗二叉树是否相等(前序遍历的应用)
111     bool operator==(BinaryTree<T> &s)
112     {
113         return (equal(this->getRoot(), s.getRoot()));
114     }
115 
116     //计算二叉树的结点的个数(后序遍历的应用)
117     int Size() { return Size(root); }
118 
119     //计算二叉树的高度(后序遍历的应用)
120     int Height() { return Height(root); }
121 
122     //判断二叉树是否为空
123     bool Empty() { return (root == NULL) ? true : false; }
124 
125     //以广义表的形式输出二叉树(前序遍历的应用)
126     void PrintBinTree() { PrintBinTree(root); }
127 
128 protected:
129 
130     //使用广义表创建二叉树函数,这里以“字符”创建二叉树,以'#'字符代表结束
131     void CreateBinTree(BinTreeNode<T> *&BT)
132     {
133         stack<BinTreeNode<T> *> s;
134         BT = NULL;
135         BinTreeNode<T> *p, *t; //p用来记住当前创建的节点,t用来记住栈顶的元素
136         int k;                 //k是处理左、右子树的标记
137         T ch;
138         cin >> ch;
139 
140         while (ch != RefValue)
141         {
142             switch (ch)
143             {
144             case '(': //对(做处理
145                 s.push(p);
146                 k = 1;
147                 break;
148 
149             case ')': //对)做处理
150                 s.pop();
151                 break;
152 
153             case ',': //对,做处理
154                 k = 2;
155                 break;
156 
157             default:
158                 p = new BinTreeNode<T>(ch); //构造一个结点
159                 if (BT == NULL)             //如果头节点是空
160                 {
161                     BT = p;
162                 }
163                 else if (k == 1) //链入*t的左孩子
164                 {
165                     t = s.top();
166                     t->leftChild = p;
167                 }
168                 else //链入*t的右孩子
169                 {
170                     t = s.top();
171                     t->rightChild = p;
172                 }
173             }
174             cin >> ch;
175         }
176     }
177 
178     //创建二叉树(利用已知的二叉树的前序遍历创建)用#表示空结点
179     void CreateBinTree_PreOrder(BinTreeNode<T> *&subTree)
180     {
181         T item;
182         if (cin >> item)
183         {
184             if (item != RefValue)
185             {
186                 subTree = new BinTreeNode<T>(item); //构造结点
187                 if (subTree == NULL)
188                 {
189                     cout << "空间分配错误!" << endl;
190                     exit(1);
191                 }
192                 CreateBinTree_PreOrder(subTree->leftChild);  //递归创建左子树
193                 CreateBinTree_PreOrder(subTree->rightChild); //递归创建右子树
194             }
195             else
196             {
197                 subTree == NULL;
198             }
199         }
200     }
201 
202     //使用先序遍历和中序遍历创建二叉树
203     void CreateBinTreeBy_Pre_In(BinTreeNode<T> *&cur, const char *pre, const char *in, int n)
204     {
205         if (n <= 0)
206         {
207             cur = NULL;
208             return;
209         }
210         int k = 0;
211         while (pre[0] != in[k]) //再中序中找到pre[0]的值
212         {
213             k++;
214         }
215         cur = new BinTreeNode<T>(in[k]); //创建结点
216         CreateBinTreeBy_Pre_In(cur->leftChild, pre + 1, in, k);
217         CreateBinTreeBy_Pre_In(cur->rightChild, pre + k + 1, in + k + 1, n - k - 1);
218     }
219     //使用后序遍历和中序遍历创建二叉树
220     void CreateBinTreeBy_Post_In(BinTreeNode<T> *&cur, const char *post, const char *in, int n)
221     {
222         if (n == 0)
223         {
224             cur = NULL;
225             return;
226         }
227 
228         char r = *(post + n - 1);    //根结点值
229         cur = new BinTreeNode<T>(r); //构造当前结点
230 
231         int k = 0;
232         const char *p = in;
233         while (*p != r)
234         {
235             k++;
236             p++;
237         }
238         CreateBinTreeBy_Post_In(cur->leftChild, post, in, k);
239         CreateBinTreeBy_Post_In(cur->rightChild, post + k, p + 1, n - k - 1);
240     }
241 
242     //先序遍历(递归)
243     void PreOrder(BinTreeNode<T> *&subTree)
244     {
245         if (subTree != NULL)
246         {
247             cout << subTree->data << " ";
248             PreOrder(subTree->leftChild);
249             PreOrder(subTree->rightChild);
250         }
251     }
252 
253     //中序遍历(递归)
254     void InOrder(BinTreeNode<T> *&subTree)
255     {
256         if (subTree != NULL)
257         {
258             InOrder(subTree->leftChild);
259             cout << subTree->data << " ";
260             InOrder(subTree->rightChild);
261         }
262     }
263 
264     //后序遍历(递归)
265     void PostOrder(BinTreeNode<T> *&subTree)
266     {
267         if (subTree != NULL)
268         {
269             PostOrder(subTree->leftChild);
270             PostOrder(subTree->rightChild);
271             cout << subTree->data << " ";
272         }
273     }
274 
275     //先序遍历(非递归)
276     void PreOrder_NoRecurve(BinTreeNode<T> *p)
277     {
278         stack<BinTreeNode<T> *> S;
279         BinTreeNode<T> *t;
280         S.push(p);         //根节点进栈
281         while (!S.empty()) //当栈不为空
282         {
283             t = S.top(); //p先记住栈顶元素,然后栈顶出栈
284             S.pop();
285             cout << t->data << " ";    //访问元素
286             if (t->rightChild != NULL) //右孩子不为空,右孩子近栈
287             {
288                 S.push(t->rightChild);
289             }
290             if (t->leftChild != NULL) //左孩子不为空,左孩子进栈
291             {
292                 S.push(t->leftChild);
293             }
294         }
295     }
296 
297     //中序遍历(非递归)
298     void InOrder_NoRecurve(BinTreeNode<T> *root)
299     {
300         if (root == NULL)
301             return;
302         stack<BinTreeNode<T> *> s;
303         s.push(root);
304         while (!s.empty())
305         {
306             while (s.top()->leftChild != NULL) //将左结点依次入栈
307             {
308                 s.push(s.top()->leftChild);
309             }
310             while (!s.empty())
311             {
312                 BinTreeNode<T> *cur = s.top();
313                 cout << cur->data << " ";
314                 s.pop();
315                 if (cur->rightChild != NULL)
316                 {
317                     s.push(cur->rightChild);
318                     break;
319                 }
320             }
321         }
322     }
323 
324     //后序遍历(非递归)
325     void PostOrder_NoRecurve(BinTreeNode<T> *p)
326     {
327         if (root == NULL)
328             return;
329         stack<BinTreeNode<T> *> s;
330         s.push(p);
331         BinTreeNode<T> *lastPop = NULL;
332         while (!s.empty())
333         {
334             while (s.top()->leftChild != NULL)
335                 s.push(s.top()->leftChild);
336             while (!s.empty())
337             {
338                 //右叶子结点 || 没有右结点
339                 if (lastPop == s.top()->rightChild || s.top()->rightChild == NULL)
340                 {
341                     cout << s.top()->data << " ";
342                     lastPop = s.top();
343                     s.pop();
344                 }
345                 else if (s.top()->rightChild != NULL)
346                 {
347                     s.push(s.top()->rightChild);
348                     break;
349                 }
350             }
351         }
352     }
353 
354     //层次遍历(非递归)
355     void LevelOrder(BinTreeNode<T> *p)
356     {
357         queue<BinTreeNode<T> *> Q;
358         Q.push(p); //根节点进队
359         BinTreeNode<T> *t;
360         while (!Q.empty())
361         {
362             t = Q.front(); //t先记住队头,再将队头出队
363             Q.pop();
364             cout << t->data << " "; //访问队头元素的数据
365 
366             if (t->leftChild != NULL)
367             {
368                 Q.push(t->leftChild);
369             }
370 
371             if (t->rightChild != NULL)
372             {
373                 Q.push(t->rightChild);
374             }
375         }
376     }
377 
378     //从结点subTree开始,搜索结点current的父节点,找到返回父节点的地址,找不到返回NULL
379     BinTreeNode<T> *Parent(BinTreeNode<T> *subTree, BinTreeNode<T> *current)
380     {
381         if (subTree == NULL)
382         {
383             return NULL;
384         }
385         if (subTree->leftChild == current || subTree->rightChild == current) //如果找到,返回父节点subTree
386         {
387             return subTree;
388         }
389         BinTreeNode<T> *p;
390         if (p = Parent(subTree->leftChild, current) != NULL) //递归在左子树中搜索
391         {
392             return p;
393         }
394         else
395         {
396             return Parent(subTree->rightChild, current); //递归右子树中搜索
397         }
398     }
399 
400     //二叉树的销毁
401     void Destroy(BinTreeNode<T> *&subTree)
402     {
403         if (subTree != NULL)
404         {
405             Destroy(subTree->leftChild);
406             Destroy(subTree->rightChild);
407             delete subTree;
408             subTree = NULL;
409         }
410     }
411 
412     //复制二叉树函数,返回一个指针,给出一个以originNode为根复制的二叉树的副本
413     BinTreeNode<T> *Copy(BinTreeNode<T> *originNode)
414     {
415         if (originNode == NULL)
416         {
417             return NULL;
418         }
419         BinTreeNode<T> *temp = new BinTreeNode<T>; //创建根结点
420         temp->data = originNode->data;
421         temp->leftChild = Copy(originNode->leftChild);
422         temp->rightChild = Copy(originNode->rightChild);
423         return temp;
424     }
425 
426     //判断两颗二叉树是否相等
427     bool equal(BinTreeNode<T> *a, BinTreeNode<T> *b)
428     {
429         if (a == NULL && b == NULL) //两者都为空
430         {
431             return true;
432         }
433         if (a != NULL && b != NULL && a->data == b->data && equal(a->leftChild, b->leftChild) && equal(a->rightChild, b->rightChild)) //两者都不为空,且两者的结点数据相等,且两者的左右子树的结点都相等
434         {
435             return true;
436         }
437         return false;
438     }
439 
440     //计算二叉树以subTree为根的结点的个数
441     int Size(BinTreeNode<T> *subTree) const
442     {
443         if (subTree == NULL) //递归结束,空树结点个数为0
444         {
445             return 0;
446         }
447         return 1 + Size(subTree->leftChild) + Size(subTree->rightChild);
448     }
449 
450     //计算二叉数以subTree为根的高度
451     int Height(BinTreeNode<T> *subTree)
452     {
453         if (subTree == NULL) //递归结束,空树高度为0
454         {
455             return 0;
456         }
457         int i = Height(subTree->leftChild);
458         int j = Height(subTree->rightChild);
459         return i < j ? j + 1 : i + 1;
460     }
461 
462     //以广义表的形式输出二叉树
463     void PrintBinTree(BinTreeNode<T> *BT)
464     {
465         if (BT != NULL) //树为空时结束递归
466         {
467             cout << BT->data;
468             if (BT->leftChild != NULL || BT->rightChild != NULL)
469             {
470                 cout << '(';
471                 if (BT->leftChild != NULL)
472                 {
473                     PrintBinTree(BT->leftChild);
474                 }
475                 cout << ',';
476                 if (BT->rightChild != NULL)
477                 {
478                     PrintBinTree(BT->rightChild);
479                 }
480                 cout << ')';
481             }
482         }
483     }
484 
485 private:
486     BinTreeNode<T> *root; //根节点
487     T RefValue;           //数据输入停止的标志,需要一个构造函数
488 };

 

展开阅读全文
c++
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部