二叉树

二叉树的构建

【问题描述】：设有n个节点的二叉树采用顺序存储结构存储在数组BT中，编写函数由该数组创建的二叉链式存储结构
【思路】：假定BT数组中顺序存储顺序为层次遍历的顺序

 

1. 方法 一：

BT数组中的下标 与 二叉树节点按层次遍历编号 如图：

即得到节点的值等于BT[K-1], k为节点编号，以及如下图根节点与左右子树的编号规律：

则可以利用递归，递归一般分为三部分：

1.递归出口以及参数的容错处理

2.递归逻辑（在每一次调用做的事情）

3.递归调用

#include<iostream>
#include<string>
using namespace std;

char BT[] = "ABCD#EF";
int n = strlen(BT);

struct BTNode
{
    char data;
    BTNode *lchild, *rchild;
    BTNode(char d): data(d), lchild(NULL), rchild(NULL) {} //构造函数
    ~BTNode() 
    {
        delete lchild; 
        delete rchild;
    }
};

void Create(BTNode *&b, int k)
{
    if (k > n || BT[k - 1] == '#') //缺失一个=号，则t=NULL
    {
        b = NULL;
    }  //递归出口
    else
    {
        b = new BTNode(BT[k - 1]);  //递归逻辑
        Create(b->lchild, 2 * k);   //递归调用
        Create(b->rchild, 2 * k + 1);
    }

}
int main()
{
       BTNode *b;
       Create(b, 1);    
}

 

2. 方法二：

#include<iostream>
using namespace std;

struct BTNode
{

    char data;
    BTNode *left, *right;
    BTNode(char val) : data(val), left(NULL), right(NULL) {}
    ~BTNode()
    {
        delete left;
        delete right;
    }
};

void CreateBTree(BTNode *&root)
{
    char ch; //要插入的数据  
    cin >> ch;
    if (ch == '#')
        root = NULL;
    else
    {
        root = new BTNode(ch);
        root->data = ch;
        printf("请输入%c的左孩子：", ch);
        CreateBTree(root->left);
        printf("请输入%c的右孩子：", ch);
        CreateBTree(root->right);
    }
}

int main()
{
    BTNode *root;
    return 0;
}

---

二叉树的遍历

2.1 前序遍历

2.2 中序遍历

---

二叉树的叶子节点个数

int leaf(BTNode *root)
{
    if (!root)
        return 0;
    if (!root->left && !root->right)
        return 1;
    return leaf(root->left) + leaf(root->right);
}

---

二叉树的节点个数

int Node(BTNode *root)
{
    if (!root)
        return 0;
    if (!root->left && !root->right)
        return 1;
    return Node(root->left) + Node(root->right) + 1;
}