第六次資料結構作業 - 計算二叉樹中結點值等于某給定值結點個數

題意如下：

已知二叉樹采用二叉連結清單存儲，其結點結構定義如下：

template<class T>   
struct BinTreeNode{
 T data;
 BinTreeNode<T> *lchild，*rchild;
};
           

編寫計算二叉樹中節點data值等于給定x值的結點個數算法，p指向二叉樹的根節點,BinaryTree為二叉樹類。函數原型為：

int BinaryTree::CountNode(BinTreeNode *p，T x);

分析：

這個題我本來想複習一下通過前序和中序建立二叉樹，但是發現不能這樣做，因為可能有多個相同的節點的值，是以最後采用的是利用二叉樹前序周遊建立其中0代表空結點

之後我又犯了一個重大錯誤，在自己做的測試資料中，隻進行了非0節點的前序周遊，但是沒有考慮到0導緻程式出錯，這個算法那掌握還是不很好，需要以後多看多練

代碼如下：

/*
測試資料：前序建立内容和要查找的結果
1 2 1  0 0 1 0 0 1 6 0 0 7 0 0
1
答案為4
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>

using namespace std;
const int maxn = 1000;

template<class T>
struct BinTreeNode
{
    T data;
    BinTreeNode<T>* lchild, * rchild;
    BinTreeNode()
    {
        lchild = rchild = NULL;
    }
    BinTreeNode(int dd):data(dd),lchild(NULL),rchild(NULL) {}
};
//編寫計算二叉樹中節點data值等于給定x值的結點個數算法，
//p指向二叉樹的根節點,BinaryTree為二叉樹類

template<class T>
class BinaryTree
{
public:
    int CountNode(BinTreeNode<T> *p,T x);
    void CreateTree(BinTreeNode<T>* & root)
    {
        T tmp;
        cin >> tmp;
        if(tmp == 0)
            root = NULL;
        else
        {
            root = new BinTreeNode<T>(tmp);
            CreateTree(root->lchild);
            CreateTree(root->rchild);
        }
    }
    void Postorder(BinTreeNode<T> *root)
    {
        if(root != NULL)
        {
            Postorder(root->lchild);
            Postorder(root->rchild);
            cout << root->data << " ";
        }
    }
    void Preorder(BinTreeNode<T> *root)
    {
        if(root != NULL)
        {
            cout << root->data << " ";
            Preorder(root->lchild);
            Preorder(root->rchild);
        }
    }
    void Inorder(BinTreeNode<T> *root)
    {
        if(root != NULL)
        {
            Inorder(root->lchild);
            cout << root->data <<" ";
            Inorder(root->rchild);
        }
    }

};
template<class T>
int BinaryTree<T>::CountNode(BinTreeNode<T> *p,T x)
{

    if(p != NULL)
    {
        if(p->data == x)
            return CountNode(p->lchild,x)+CountNode(p->rchild,x)+1;
        else
            return CountNode(p->lchild,x)+CountNode(p->rchild,x);
    }
    return 0;
}

int main()
{
    BinTreeNode<int> * root = NULL;
    BinaryTree<int> obj;
    obj.CreateTree(root);
    obj.Preorder(root);
    cout << endl;
    obj.Inorder(root);
    cout << endl;
    obj.Postorder(root);
    cout << endl;
    int x;
    cin >> x;
    cout << obj.CountNode(root,x) << endl;
    return 0;
}

           

代碼改變世界