繁星蓝雨

繁星蓝雨

关注
发信
关注(28)粉丝(399)

二叉树k层的叶子结点个数

1 题目

假设二叉树采用二叉链表存储结构，设计一个算法求其指定的第k层（k>1，跟是第1层）的叶子结点个数。

2 思路

2.1 思路1

设置一个全局变量记录某层叶子结点个数，前序遍历二叉树，并在遍历的过程中记录结点的层数。

2.2 思路2

层序遍历二叉树，记录某层的二叉树叶子结点个数。没有目标层时，让该层结点的孩子结点入队；到达目标层时，不再让该层的孩子结点入队，统计队中（该层）叶子结点的个数。

  • 具体流程
    • 设置两个指针分别指该层的最后一个结点lastNode（初始为根结点）和下一层的最后一个非叶结点newNode。
    • 每遍历到结点的左/右孩子为非叶结点时，把newNode更新为当前结点的左/右孩子；
    • 当遍历的结点为该层的最后结点时，把lastNode更新为最新的newNode。

3 代码实现

二叉树的存储结构：

template <typename T>
class BiTNode {
public:
    T data;
    BiTNode* left;
    BiTNode* right;
    BiTNode():data(NULL),left(NULL),right(NULL){};
};

template <>
class BiTNode<int> {
public:
    int data;
    BiTNode* left;
    BiTNode* right;
    BiTNode() : data(0), left(nullptr), right(nullptr) {}
    BiTNode(int x) : data(x), left(nullptr), right(nullptr) {}
    BiTNode(int x, BiTNode *left, BiTNode *right) : data(x), left(left), right(right) {}
};

template <>
class BiTNode<char> {
public:
    char data;
    BiTNode* left;
    BiTNode* right;
    BiTNode() : data('\0'), left(nullptr), right(nullptr) {}
    BiTNode(char x) : data(x), left(nullptr), right(nullptr) {}
    BiTNode(char x, BiTNode *left, BiTNode *right) : data(x), left(left), right(right) {}
};

3.1 思路1

template <typename T>
void calLevelLeaf(BiTNode<T>* root, int level, int k){
    if(level < k){
        if(root->left != nullptr) calLevelLeaf(root->left, level+1, k);
        if(root->right != nullptr) calLevelLeaf(root->right, level+1, k);
    }else if(level == k && root->left == nullptr && root->right == nullptr){
        leafNum++;
    }
} 

template <typename T>
int getLevelLeaf(BiTNode<T>* root, int k){
    calLevelLeaf(root, 1,  k);
    return leafNum;
}

3.2 思路2

template <typename T>
int getLevelLeaf2(BiTNode<T>* root, int k){
    deque<BiTNode<T>*> q;//双端队列
    BiTNode<T> *newNode = nullptr, *lastNode = root;  
    int level = 1;//层数
    int leafNum = 0;//该层的叶子结点个数
    q.push_back(root);
    while(!q.empty()){
        BiTNode<T>* p;
        if(level == k){
            while(!q.empty()){
                p = q.front();
                q.pop_front();
                if(p->left == nullptr && p->right == nullptr){
                    leafNum++;
                }
            }
            break;
        }
        else{
            p = q.front();
            q.pop_front();
            if(p->left != nullptr){
                q.push_back(p->left);
                newNode = p->left;
            }
            if(p->right != nullptr){
                q.push_back(p->right);
                newNode = p->right;
            }
            if(lastNode == p){
                lastNode = newNode;
                level += 1;
            }
        }
    }
    return leafNum;
}

3.3 完整的代码案例

#include <iostream>
#include <stack>
#include <deque>
#include <queue>
using namespace std;

template <typename T>
class BiTNode {
public:
    T data;
    BiTNode* left;
    BiTNode* right;
    BiTNode():data(NULL),left(NULL),right(NULL){};
};

template <>
class BiTNode<int> {
public:
    int data;
    BiTNode* left;
    BiTNode* right;
    BiTNode() : data(0), left(nullptr), right(nullptr) {}
    BiTNode(int x) : data(x), left(nullptr), right(nullptr) {}
    BiTNode(int x, BiTNode *left, BiTNode *right) : data(x), left(left), right(right) {}
};

template <>
class BiTNode<char> {
public:
    char data;
    BiTNode* left;
    BiTNode* right;
    BiTNode() : data('\0'), left(nullptr), right(nullptr) {}
    BiTNode(char x) : data(x), left(nullptr), right(nullptr) {}
    BiTNode(char x, BiTNode *left, BiTNode *right) : data(x), left(left), right(right) {}
};


template <typename T>
void createBiTNode(BiTNode<T>** treeNode, deque<T>dataDeq) {//层序遍历建立二叉树
    //特殊处理根结点
    T data;
    data = dataDeq.front();
    dataDeq.pop_front();
    BiTNode<T> * node = new BiTNode<T>();
    *treeNode = node;
    (*treeNode)->data = data;

    deque<BiTNode<T>**> nodeDeq;//用于层序建立树时访问双亲节点
    nodeDeq.push_back(treeNode);

    int index = 2;//用于判定左右孩子（左偶，右奇）
    while (!dataDeq.empty()){//当数据节点非空时，进行建树

        BiTNode<T>** nodeParent = nodeDeq.front();
       nodeDeq.pop_front();

       for(int i = 0; i < 2;i++){
           data = dataDeq.front();
           dataDeq.pop_front();
           if(data == '#'){//适用于char
           //if(data == -1){//适用于int
               if(index%2 == 0) (*nodeParent)->left = nullptr;
               else (*nodeParent)->right = nullptr;
           }else{
               BiTNode<T> * node = new BiTNode<T>();
               node->data = data;
               if(index%2 == 0){
                   (*nodeParent)->left = node;
                   nodeDeq.push_back(&(*nodeParent)->left);
               }else{
                   (*nodeParent)->right = node;
                   nodeDeq.push_back(&(*nodeParent)->right);
               }
           }
           index++;
       }
    }
}


template <>
void createBiTNode<char>(BiTNode<char>** treeNode, deque<char>dataDeq) {//层序遍历建立二叉树
    //特殊处理根结点
    char data;
    data = dataDeq.front();
    dataDeq.pop_front();
    BiTNode<char> * node = new BiTNode<char>();
    *treeNode = node;
    (*treeNode)->data = data;

    deque<BiTNode<char>**> nodeDeq;//用于层序建立树时访问双亲节点
    nodeDeq.push_back(treeNode);

    int index = 2;//用于判定左右孩子（左偶，右奇）
    while (!dataDeq.empty()){//当数据节点非空时，进行建树

        BiTNode<char>** nodeParent = nodeDeq.front();
        nodeDeq.pop_front();

        for(int i = 0; i < 2;i++){
            data = dataDeq.front();
            dataDeq.pop_front();
            if(data == '#'){
                if(index%2 == 0) (*nodeParent)->left = nullptr;
                else (*nodeParent)->right = nullptr;
            }else{
                BiTNode<char> * node = new BiTNode<char>();
                node->data = data;
                if(index%2 == 0){
                    (*nodeParent)->left = node;
                    nodeDeq.push_back(&(*nodeParent)->left);
                }else{
                    (*nodeParent)->right = node;
                    nodeDeq.push_back(&(*nodeParent)->right);
                }
            }
            index++;
        }
    }
}

template <>
void createBiTNode<int>(BiTNode<int>** treeNode, deque<int>dataDeq) {//层序遍历建立二叉树
    //特殊处理根结点
    char data;
    data = dataDeq.front();
    dataDeq.pop_front();
    BiTNode<int> * node = new BiTNode<int>();
    *treeNode = node;
    (*treeNode)->data = data;

    deque<BiTNode<int>**> nodeDeq;//用于层序建立树时访问双亲节点
    nodeDeq.push_back(treeNode);

    int index = 2;//用于判定左右孩子（左偶，右奇）
    while (!dataDeq.empty()){//当数据节点非空时，进行建树

        BiTNode<int>** nodeParent = nodeDeq.front();
        nodeDeq.pop_front();

        for(int i = 0; i < 2;i++){
            data = dataDeq.front();
            dataDeq.pop_front();
            if(data == -1){
                if(index%2 == 0) (*nodeParent)->left = nullptr;
                else (*nodeParent)->right = nullptr;
            }else{
                BiTNode<int> * node = new BiTNode<int>();
                node->data = data;
                if(index%2 == 0){
                    (*nodeParent)->left = node;
                    nodeDeq.push_back(&(*nodeParent)->left);
                }else{
                    (*nodeParent)->right = node;
                    nodeDeq.push_back(&(*nodeParent)->right);
                }
            }
            index++;
        }
    }
}

template <typename T>
void inOrder(BiTNode<T>* treeNode){
    if(treeNode){
        inOrder(treeNode->left);
        cout<<treeNode->data<<" ";
        inOrder(treeNode->right);
    }
}

template <typename T>
void preOrder(BiTNode<T>* treeNode){
    if(treeNode){
        cout<<treeNode->data<<" ";
        preOrder(treeNode->left);
        preOrder(treeNode->right);
    }
}

template <typename T>
void postOrder(BiTNode<T>* treeNode){
    if(treeNode){
        postOrder(treeNode->left);
        postOrder(treeNode->right);
        cout<<treeNode->data<<" ";
    }
}

template <typename T>
void preOrder2(BiTNode<T>* treeNode){
    stack<BiTNode<T>*> s;
    BiTNode<T>* p = treeNode;
    while(p || !s.empty()){
        if(p){
            cout<<p->data<<" ";
            s.push(p);
            p = p->left;
        }else{
            p = s.top();
            s.pop();
            p = p->right;
        }
    }
}

template <typename T>
void inOrder2(BiTNode<T>* treeNode){
    stack<BiTNode<T>*> s;
    BiTNode<T>* p = treeNode;
    while(p || !s.empty()){
        if(p){
            s.push(p);
            p = p->left;
        }else{
            p = s.top();
            cout<<p->data<<" ";
            s.pop();
            p = p->right;
        }
    }
}

template <typename T>
void postOrder2(BiTNode<T>* treeNode){
    stack<BiTNode<T>*> s;
    BiTNode<T> *p = treeNode, *r = nullptr;
    while(p || !s.empty()){
        if(p){
            s.push(p);
            p = p->left;
        }else{
            p = s.top();
            if(p->right && p->right != r){//有右孩子且没有访问过
                p = p->right;
            }else{
                cout<<p->data<<" ";
                s.pop();
                r = p;
                p = nullptr;
            }
        }
    }
}

template <typename T>
void levelOrder(BiTNode<T>* treeNode) {
    queue<BiTNode<T>*> nodeQue;
    BiTNode<T>* p = treeNode;
    nodeQue.push(p);
    while(!nodeQue.empty()){
        p = nodeQue.front();
        nodeQue.pop();
        cout<<p->data<<" ";
        if(p->left) nodeQue.push(p->left);
        if(p->right) nodeQue.push(p->right);
    }
}

int leafNum = 0;

template <typename T>
void calLevelLeaf(BiTNode<T>* root, int level, int k){
    if(level < k){
        if(root->left != nullptr) calLevelLeaf(root->left, level+1, k);
        if(root->right != nullptr) calLevelLeaf(root->right, level+1, k);
    }else if(level == k && root->left == nullptr && root->right == nullptr){
        leafNum++;
    }
} 

template <typename T>
int getLevelLeaf(BiTNode<T>* root, int k){
    calLevelLeaf(root, 1,  k);
    return leafNum;
}

template <typename T>
int getLevelLeaf2(BiTNode<T>* root, int k){
    deque<BiTNode<T>*> q;//双端队列
    BiTNode<T> *newNode = nullptr, *lastNode = root;  
    int level = 1;//层数
    int leafNum = 0;//该层的叶子结点个数
    q.push_back(root);
    while(!q.empty()){
        BiTNode<T>* p;
        if(level == k){
            while(!q.empty()){
                p = q.front();
                q.pop_front();
                if(p->left == nullptr && p->right == nullptr){
                    leafNum++;
                }
            }
            break;
        }
        else{
            p = q.front();
            q.pop_front();
            if(p->left != nullptr){
                q.push_back(p->left);
                newNode = p->left;
            }
            if(p->right != nullptr){
                q.push_back(p->right);
                newNode = p->right;
            }
            if(lastNode == p){
                lastNode = newNode;
                level += 1;
            }
        }
    }
    return leafNum;
}

int main() {
    //使用字符串
    //deque<char> treeVec{'a', 'b', 'c', 'd', 'e', '#', '#'};
    //deque<char> treeVec{'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', '#', '#','i','#','#','k','l'};
    deque<char> treeVec{'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', '#', 'i', 'j','#','#','k','l','m','n','#','#','o','#','#','p','#','#'};
    BiTNode<char>* tree = new BiTNode<char>();
    createBiTNode(&tree, treeVec);
    //使用数值
//    deque<int> treeVec{1, 2, 3, 4, 5, -1, -1};
//    BiTNode<int>* tree = new BiTNode<int>();
//    createBiTNode(&tree, treeVec);
    //遍历树
    //inOrder(tree);
    //cout<<endl;
    
    printf("%d", getLevelLeaf2(tree, 5));//tree,4
    

	return 0;    
}
12-04 10:58
Powered by LMLPHP ©2024 繁星蓝雨 0.005911