1. 树的根本结构

1.1、树的根本概念

  1. 树的界说 树是n（n>=0）个结点的有限集。当n = 0时，称为空树。在任意一棵非空树中应满意：
  • 有且仅有一个特定的称为根的结点。
  • 当n>1时，其余节点可分为m（m>0）个互不相交的有限集T1,T2,…,Tm，其中每个集合自身又是一棵树，而且称为根的子树。
  1. 树的界说是递归的，即在树的界说中又用到了自身，树是一种递归的数据结构。树作为一种逻辑结构，一起也是一种分层结构，具有以下两个特点：
  • 树的根结点没有前驱，除根结点外的一切结点有且只要一个前驱。
  • 树中一切结点能够有零个或多个后继，因而n个结点的树中有n-1条边。

考研数据结构--树的遍历，逆置，是否是彻底二叉树，找第k个节点，子节点 以及各类代码题（一）

1.2 树的结构体

typedef struct BiTNode {
    char data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

这个结构体它界说了一个叫做BiTNode的结构体，以及一个指向该结构体的指针类型BiTree。

具体来说，BiTNode结构体包括以下三个成员：

  1. data：一个字符类型的数据成员。
  2. lchild：一个指向BiTNode类型的左子树的指针。
  3. rchild：一个指向BiTNode类型的右子树的指针。

lchild和rchild分别表明指向左子树和右子树的指针，而data则存储每个节点的数据。经过这种方式，能够构建出一个具有左右子树结构的二叉树。

此外，该界说还运用了typedef关键字来为结构体BiTNode界说了一个别号BiTree，表明指向该结构体的指针类型。这样，我们就能够运用BiTree来声明指向BiTNode结构体的指针变量。

2. 树的创建和前序遍历

  1. 现在要创建一棵如下的树ABD##E##C##,#表明空节点。
            A
         B    C
       D  E  # #
     # # # #
  1. 递归创建树
void createtree(BiTree& t) {  // 先序结构二叉树。
    char ch;
    // ABD##E##C##
    ch = getchar();  // 输入字符。
    if (ch == '#')
        t = NULL;
    else {
        t = (BiTNode*)malloc(sizeof(BiTNode));
        t->data = ch;
        t->lchild = NULL;
        t->rchild = NULL;
        createtree(t->lchild);
        createtree(t->rchild);
    }
};
  1. 前序遍历打印树的节点
void PreOrder(BiTree T) {
    if (T != NULL) {
        cout << ' ' << T->data;
        PreOrder(T->lchild);  // 递归遍历左子树
        PreOrder(T->rchild);  // 递归遍历右子树
    }
};

3. 递归遍历二叉树

前中后序遍历二叉树的完整可执行代码


#include <bits/stdc  .h>
using namespace std;
typedef struct BiTNode {
    char data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
// 递归鸿沟，递归式
/*
BiTNode *p 和BiTree
p，在代码的视点上来讲是等价的，都是界说一个指针变量p，来指向二叉树的节点 BiTree
p：侧重于表明p指向的节点为根的一棵树 BiTNode *p 侧重表明一个树的节点
*/
//  PreOrder 先序遍历 根左右
//  InOder 中序低估遍历称号
//  PostOrder 后序递归遍历
/**
            A
         B    C
       D  E  # #
     # # # #
 */
void createtree(BiTree& t) {  // 先序结构二叉树。
    char ch;
    // ABD##E##C##
    ch = getchar();  // 输入字符。
    if (ch == '#')
        t = NULL;
    else {
     // t = new Node;  // 创建一个新的 Node 对象，并将其地址赋值给根节点。
     //也能够这样写 t = (BiTNode*)malloc(sizeof(BiTNode));
        t = (BiTNode*)malloc(sizeof(BiTNode));
        t->data = ch;
        t->lchild = NULL;
        t->rchild = NULL;
        createtree(t->lchild);
        createtree(t->rchild);
    }
};
// 递归-前序遍历二叉树
void PreOrder(BiTree T) {
    if (T != NULL) {
        cout << " " << T->data;
        PreOrder(T->lchild);  // 递归遍历左子树
        PreOrder(T->rchild);  // 递归遍历右子树
    }
};
// 递归-中序遍历二叉树
void InOder(BiTree T) {
    if (T != NULL) {
        InOder(T->lchild);  // 递归遍历左子树
        cout << " " << T->data;
        InOder(T->rchild);  // 递归遍历右子树
    }
};
// 递归-后序遍历二叉树
void PostOrder(BiTree T) {
    if (T != NULL) {
        PostOrder(T->lchild);  // 递归遍历左子树
        cout << " " << T->data;
        PostOrder(T->rchild);  // 递归遍历右子树
    }
};
int main() {
    BiTree t;
    // 输入创建ABD##E##C##
    createtree(t);
    cout << "递归-前序遍历二叉树：";
    PreOrder(t);
    cout << endl;
    cout << "递归-中序遍历二叉树：";
    InOder(t);
    cout << endl;
    cout << "递归-后序遍历二叉树：";
    PostOrder(t);
    cout << endl;
    return 0;
}

4. 非递归遍历二叉树

树结构,代码结合图理解，非常重要！！！

考研数据结构--树的遍历，逆置，是否是彻底二叉树，找第k个节点，子节点 以及各类代码题（一）

tips:栈的根本运用

用栈来保存数据

在C 中，你能够运用STL库中的stack类来创建一个仓库。除了stack.size()之外，stack类还供给了以下几种常见的操作：

  1. stack.empty()：查看仓库是否为空。假如仓库为空，则回来true；否则回来false。
  2. stack.top()：回来仓库顶部的元素，但不将其从仓库中移除。
  3. stack.push(x)：将元素x推入仓库的顶部。
  4. stack.pop()：移除并回来仓库顶部的元素。
  5. stack.data()：回来一个表明仓库的容器。这个容器是一个后进先出（LIFO）的容器。

stack.size() != 0，栈不为空，成果便是 true；stack.size() == 0假如仓库为空，那么成果就为 false。

4.1 前序遍历

// 非递归-前序遍历
/*
思维：用栈来完成。首要拜访根节点，然后将根节点入栈，接着拜访当时节点的左节点，然后入栈，当左节点拜访完后，
出栈，并顺次拜访右节点
*/
void un_preTraversal(Node* root) {
    stack<Node*>
        stack;  // 名为 stack 的仓库（stack）,名为 stack 的仓库（stack）
    // 当时节点
    Node* p = root;
    // 因而，stack.size() != 0
    // 的意义是查看仓库中是否有元素，也便是查看仓库是否为空。假如仓库不为空，那么
    // stack.size() != 0 的成果就为 true；假如仓库为空，那么成果就为 false。
    while (p != NULL || stack.size() != 0) {
        if (p != NULL) {
            visit(p);       // 拜访p之前一定要确保p不为空
            stack.push(p);  // 入栈
            p = p->lchild;
        } else {
            p = stack.top();
            stack.pop();
            p = p->rchild;
        }
    }
}

4.2 中序遍历

// 非递归-中序遍历
/*
思维：用栈来完成。从根节点开始顺次遍历当时节点的左节点，并顺次入栈，当左节点遍历完成后，获取
栈顶元素并出栈，然后拜访该节点，并顺次遍历其右节点
*/
void un_midTraversal(Node* root) {
    stack<Node*> stack;
    Node* p = root;
    while (p != NULL || stack.size() != 0) {
        if (p != NULL) {
            stack.push(p);
            p = p->lchild;
        } else {
            p = stack.top();
            stack.pop();
            visit(p);
            p = p->rchild;
        }
    }
}

4.3. 后序遍历

#include <bitsstdc  .h>
typedef struct treenode {
    char data;
    struct treenode *lchild, *rchild;
    int tag;
} treenode, *tree;
void createtree(tree& t) {  // 先序结构二叉树。
    char ch;
  //  ABD##E##C##
    ch = getchar();  // 输入字符。
    if (ch == '#')
        t = NULL;
    else {
        t = (treenode*)malloc(sizeof(treenode));
        t->data = ch;
        t->tag = 0;
        t->lchild = NULL;
        t->rchild = NULL;
        createtree(t->lchild);
        createtree(t->rchild);
    }
}
void back(tree t) {
    struct treenode* stack[100];  // 直接运用结构体树立一个栈。
    int top = -1;
    treenode* p = t;        // 树立指针指向这棵树。
    treenode* x;            // 保存出栈的结点。
    while (p || top != -1)  // p和栈不能为空。
    {
        if (p)  // p不为空时进栈。
        {
            top  ;
            stack[top] = p;
            p = p->lchild;
        } else  // 为空的时分。
        {
            p = stack[top];                        // 拜访栈顶。
            if (p->rchild && p->rchild->tag == 0)  // 判别右孩子。
            {                   // 没有被拜访，指向它的右孩子。
                p = p->rchild;  // p有值要进行栈
            } else              // 现已拜访过了。
            {
                p = stack[top];
                top--;
                printf(",", p->data);
                p->tag = 1;
                p = NULL;//这儿p为空之后，拜访栈顶
            }
        }
    }
}
int main() {
    tree t;
    createtree(t);
    back(t);
    return 0;
}

5. 树的层次遍历

5.1 从上至下，从左至右

tips：行列的根本运用

首要需要理解行列的运用：

  1. 在C 中，queue<Node*> q;是一个声明一个名为q的行列（queue）的语句，其中Node*是存储在行列中的元素的类型。在这种状况下，行列将存储指向Node对象的指针。
  2. 在C 的STL库中，queue容器供给了以下几种操作：
  • push(x)：将元素x插入行列的尾部。
  • pop()：删去行列头部的元素。
  • front()：回来指向行列头部的元素。
  • back()：回来指向行列尾部的元素。
  • size()：回来行列中元素的个数。
  • empty()：判别行列是否为空。

q.empty() == false，行列不为空

// 树的层次遍历
// 思维：运用行列queue。先将根节点入行列，循环判别当时行列不为空时，将头元素出行列并拜访头元素，然后在将它的左节点和右节点入行列
void levelTraversal(Node* root) {
    queue<Node*> q;
    Node* p = root;
    q.push(p);  // 将元素p插入行列的尾部
    // 判别条件，false行列不为空
    while (q.empty() == false) {
        p = q.front();  // 回来指向行列头部的元素
        q.pop();        // 删去行列头部的元素
        visit(p);
        if (p->lchild != NULL)
            q.push(p->lchild);//左子树持续入队
        if (p->rchild != NULL)
            q.push(p->rchild);//右子树入队
    }
}

5.2 逆置层次遍历，从下至上，从左至右

思路：将正常层次遍历的成果，存入栈中，再取出来。

// 层次遍历
void leveltraversal(tree* root) {
    stack<tree*> stack;
    queue<tree*> q;
    tree* p = root;
    q.push(p);
    while (q.empty() == false) {
        p = q.front();
        q.pop();
        cout << p->data;
        stack.push(p);
        if (p->lchild != NULL) {
            q.push(p->lchild);
        };
        if (p->rchild != NULL) {
            q.push(p->rchild);
        };
    }
    cout << endl;
    cout << "层次遍历,逆序：";
    // 不等于0阐明栈不为空
    while (stack.size() != 0) {
        tree* p = stack.top();
        stack.pop();
        cout << p->data;
    }
}

6. 找二叉树的公共先人节点

找i,j的公共先人节点

考研数据结构--树的遍历，逆置，是否是彻底二叉树，找第k个节点，子节点 以及各类代码题（一）
顺序存储，将二叉树转换，空的地方，赋值为-1。

考研数据结构--树的遍历，逆置，是否是彻底二叉树，找第k个节点，子节点 以及各类代码题（一）

  1. i,j节点均存在，treep[i]!=-1,tree[j]!=-1
  2. 假如不存在更新i和j的值,假如i>j，寻觅i的父节点（i/2），更新i。假如i<j，寻觅j的父节点（j/2），更新j;
  3. i=j时，回来i的值。
#include <bits/stdc  .h>
// 找i,j的公共先人节点
struct tree {
    // 不存在的数值为-1
    int data[12] = {-1, 1, 2, 3, -1, 4, -1, 5, -1, -1, -6, -1};
};
/*
i节点的父亲节点为2i,
左孩子是2i
右孩子是2i 1
*/
int comon(tree t, int i, int j) {
    if (t.data[i] != -1 && t.data[j] != -1)  // 阐明存在值
    {
        while (i != j)  // 更新i和j的值。
        {
            if (i > j)
                i /= 2;  // 寻觅大的父节点。更新i的值
            else
                j /= 2;
        }
        return t.data[i];  // 相一起回来公共先人。
    }
    return -1;
};
int main() {
    tree t;
    int a = comon(t, 7, 10);  // 找7号和10号节点的公共先人。
    printf("%d", a);
    return 0;
}

7. 判别是否为彻底二叉树

不满意下面任何一条就不是彻底二叉树

  1. 节点无左孩子，必无右孩子。
  2. 节点缺孩子，一切后继必无孩子。

第一个if判别状况

考研数据结构--树的遍历，逆置，是否是彻底二叉树，找第k个节点，子节点 以及各类代码题（一）
否则的状况
考研数据结构--树的遍历，逆置，是否是彻底二叉树，找第k个节点，子节点 以及各类代码题（一）

树结构

考研数据结构--树的遍历，逆置，是否是彻底二叉树，找第k个节点，子节点 以及各类代码题（一）

写法一：

// 判别是否是彻底二叉树
#include <bits/stdc  .h>
using namespace std;
#define Max 15
typedef struct treenode {
    char data;
    struct treenode *lchild, *rchild;
} treenode, *tree;
void buildtree(tree& t) {
    char ch;
    ch = getchar();
    if (ch == '#')
        t = NULL;
    else {
        t = (treenode*)malloc(sizeof(treenode));
        t->data = ch;
        t->lchild = NULL;
        t->rchild = NULL;
        buildtree(t->lchild);
        buildtree(t->rchild);
    }
}
struct squeue {
    struct treenode* data[Max];
    int f, r, tag;
};
bool isempty(squeue s) {
    if (s.f == s.r && s.tag == 0)
        return true;
    return false;
}
bool isfull(squeue s) {
    if (s.f == s.r && s.tag == 1)
        return true;
    return false;
}
bool enters(squeue& s, treenode* p) {
    if (isfull(s))
        return false;
    s.data[s.r] = p;
    s.r = (s.r   1) % Max;
    s.tag = 1;
    return true;
}
bool outs(squeue& s, treenode*& p) {
    if (s.f == s.r && s.tag == 0)
        return false;
    p = s.data[s.f];
    s.f = (s.f   1) % Max;
    s.tag = 0;
    return true;
}
bool isok(tree t) {
    squeue s;
    s.f = s.r = s.tag = 0;
    // flag 为true标志都有左右孩子，ans成果标志
    bool flag = true, ans = true;
    if (t == NULL)  // 判别是否为空树，空树也是彻底二叉树。
        ans = true;
    if (!t->lchild && !t->rchild)  // 存在节点，左右孩子为空，也是彻底二叉树
        ans = true;
    enters(s, t);  // 根节点入队
    treenode* p;
    while (!isempty(s)) {  // 遍历队
        outs(s, p);        // 先出队
        if (!p->lchild) {  // 出队元素，没有左孩子
            flag = false;
            if (p->rchild)  // 在缺孩子的状况下，还有右孩子，那么成果直接为false,不是彻底二叉树。
                ans = false;
        } else  // 有左孩子
        {
            if (flag)  // 之前不存在缺孩子的节点
            {
                enters(s, p->lchild);  // 左孩子进队
                if (p->rchild)         // 右孩子存在持续进队
                    enters(s, p->rchild);
                else  // 没有右孩子的状况下，便是缺孩子将flag设置成false;
                    flag = false;
            } else  // 之前存在缺孩子的节点，的后继又有孩子，成果变量直接为false，不是彻底二叉树
                ans = false;  //
        }
    }
    if (ans)
        return true;
    return false;
}
int main() {
    tree t;
    buildtree(t);
    if (isok(t))
        cout << "yes" << endl;
    else
        cout << "no" << endl;
    return 0;
}
// ABD##E##CF##G##  彻底
// ABD###CE##F##  非彻底

写法二（推荐）

#include <bits/stdc  .h>
using namespace std;
// ABD##E##CF##G##  彻底
// ABD###CE##F##  非彻底
typedef struct tree {
    char data;
    struct tree *lchild, *rchild;
} tree;
void createTree(tree*& root) {
    char a;
    a = getchar();
    if (a == '#') {
        root = NULL;
    } else {
        root = new tree();
        root->data = a;
        root->lchild = NULL;
        root->rchild = NULL;
        createTree(root->lchild);
        createTree(root->rchild);
    }
}
void preOrder(tree* root) {
    if (root != NULL) {
        cout << root->data;
        preOrder(root->lchild);
        preOrder(root->rchild);
    }
}
bool isok(tree* root) {
    queue<tree*> q;
    tree* p;
    bool flag = true, ans = true;
    if (root == NULL) {
        ans = true;
    }
    if (!root->rchild && !root->rchild) {
        ans = true;
    }
    q.push(root);
    // 判别条件，false行列不为空
    while (q.empty() == false) {
        p = q.front();
        q.pop();
        if (!p->lchild) {     // 判别出队元素没有左孩子
            flag = false;     // 设置标记
            if (p->rchild) {  // 在没有左孩子的状况下，还没有右孩子，直接不是彻底二叉树，设置false。
                ans = false;
            }
        } else {  // 有左孩子
            if (flag) {
                q.push(p->lchild);
                if (p->rchild) {
                    q.push(p->rchild);
                } else {
                    flag = false;
                }
            } else {
                ans = false;
            }
        }
    }
    if (ans)
        return true;
    return false;
}
int main() {
    tree* p;
    createTree(p);
    // ABD##E##CF##G##  彻底
    // ABD###CE##F##  非彻底
    // AB#D##CE##F##
    cout << "前序遍历二叉树：";
    preOrder(p);
    cout << endl;
    cout << "是否是彻底二叉树:";
    if (isok(p))
        cout << "yes" << endl;
    else
        cout << "no" << endl;
    return 0;
}

8 .查找第k个节点的值

假定二叉树选用二叉链存储结构存储，设计一个算法，求先序遍历序列中第k（1 <k<二叉树中结点个数）个结点的值。

#include <bits/stdc  .h>
using namespace std;
typedef struct tree {
    char data;
    struct tree *lchild, *rchild;
} tree;
/*
  假定二叉树选用二叉链存储结构存储，设计一个算法，求先序遍历序列中第k（1
  <k<二叉树中结点个数）个结点的值
ABD##E##C##
//                    A1
//                B2      C
//              D3   E4   F  #
//            #  # # # # #
 */
// 创建树
void createTre(tree*& root) {
    char a;
    cin >> a;
    if (a == '#') {
        root = NULL;
    } else {
        root = new tree();
        root->data = a;
        root->lchild = NULL;
        root->rchild = NULL;
        createTre(root->lchild);
        createTre(root->rchild);
    }
};
void preorder(tree* root, int k, char& temp, int& index) {
    // cout << index;
    if (root != NULL) {
        index  ;
        if (index == k) {
            temp = root->data;
        };
        cout << root->data << " ";
        preorder(root->lchild, k, temp, index);
        preorder(root->rchild, k, temp, index);
    }
};
int main() {
    tree* root;
    createTre(root);
    char temp;
    int index = 0;
    cout << "递归前序遍历二叉树：";
    preorder(root, 5, temp, index);
    cout << endl;
    cout << "第4个节点的值:" << temp << endl;
    return 0;
}

9. 指针指向树的某个节点

在一棵以二叉链表为存储结构的二叉树中，查找数据域值等于 key 的结 点是否存在，假如存在，则将指针 q 指向该结点，假定结点数据域为 int 型

#include <bits/stdc  .h>
using namespace std;
typedef struct tree {
    char data;
    struct tree *lchild, *rchild;
} tree;
/*
  在一棵以二叉链表为存储结构的二叉树中，查找数据域值等于 key 的结
点是否存在，假如存在，则将指针 q 指向该结点，假定结点数据域为 int 型。（二
叉树中结点值都不相同）
ABD##E##C##
//                    A1
//                B2      C
//              D3   E4   F  #
//            #  # # # # #
 */
// 创建树
void createTre(tree*& root) {
    char a;
    cin >> a;
    if (a == '#') {
        root = NULL;
    } else {
        root = new tree();
        root->data = a;
        root->lchild = NULL;
        root->rchild = NULL;
        createTre(root->lchild);
        createTre(root->rchild);
    }
};
void disp(tree* root) {
    if (root != NULL) {
        cout << root->data;
        disp(root->lchild);
        disp(root->rchild);
    }
}
// q为指向改节点为key的指针，key为节点的值
void search(tree* root, tree*& q, int key) {
    if (root != NULL) {
        if (root->data == key) {
            q = root;
        } else {
            search(root->lchild, q, key);
            search(root->rchild, q, key);
        }
    }
};
int main() {
    tree* root;
    createTre(root);
    tree* q;
    cout << "递归前序遍历二叉树：";
    disp(root);
    cout << endl;
    // cout << "查找值为E的节点的值:";
    search(root, q, 'E');
    cout << "q个节点的值:" << q->data << endl;
    return 0;
}

10. 运用递归核算二叉树中一切结点的个数。

法一：界说全局变量 n 用来计数。

#include <bits/stdc  .h>
using namespace std;
typedef struct tree {
    char data;
    struct tree *lchild, *rchild;
} tree;
/*
  在一棵以二叉链表为存储结构的二叉树中，查找数据域值等于 key 的结
点是否存在，假如存在，则将指针 q 指向该结点，假定结点数据域为 int 型。（二
叉树中结点值都不相同）
ABD##E##C##
//                    A1
//                B2      C
//              D3   E4   F  #
//            #  # # # # #
 */
// 创建树
void createTre(tree*& root) {
    char a;
    cin >> a;
    if (a == '#') {
        root = NULL;
    } else {
        root = new tree();
        root->data = a;
        root->lchild = NULL;
        root->rchild = NULL;
        createTre(root->lchild);
        createTre(root->rchild);
    }
};
int n = 0;
void disp(tree* root) {
    if (root != NULL) {
        n  ;
        cout << root->data;
        disp(root->lchild);
        disp(root->rchild);
    }
}
int main() {
    tree* root;
    createTre(root);
    tree* q;
    cout << "递归前序遍历二叉树：";
    disp(root);
    cout << endl;
    cout << "树节点的个数：" << n << endl;
    return 0;
}

法二：界说 n1 和 n2 分别用于接纳左右子树结点个数。

#include <bits/stdc  .h>
using namespace std;
typedef struct tree {
    char data;
    struct tree *lchild, *rchild;
} tree;
/*
  在一棵以二叉链表为存储结构的二叉树中，查找数据域值等于 key 的结
点是否存在，假如存在，则将指针 q 指向该结点，假定结点数据域为 int 型。（二
叉树中结点值都不相同）
ABD##E##C##
//                    A1
//                B2      C
//              D3   E4   F  #
//            #  # # # # #
 */
// 创建树
void createTre(tree*& root) {
    char a;
    cin >> a;
    if (a == '#') {
        root = NULL;
    } else {
        root = new tree();
        root->data = a;
        root->lchild = NULL;
        root->rchild = NULL;
        createTre(root->lchild);
        createTre(root->rchild);
    }
};
int n = 0;
void disp(tree* root) {
    if (root != NULL) {
        n  ;
        cout << root->data;
        disp(root->lchild);
        disp(root->rchild);
    }
}
int count(tree* root) {
    int n1, n2;
    if (root == NULL) {  // 节点为空的时分，回来0
        return 0;
    } else {
        n1 = count(root->lchild);
        n2 = count(root->rchild);
        return n1   n2   1;  // 这儿的 1是树自身的节点。重点留意
    }
}
int main() {
    tree* root;
    createTre(root);
    tree* q;
    cout << "递归前序遍历二叉树：";
    disp(root);
    cout << endl;
    cout << "树节点的个数：" << count(root) << endl;
    return 0;
}

11. 核算二叉树一切子节点个数

1.递归

#include <bits/stdc  .h>
using namespace std;
typedef struct tree {
    char data;
    struct tree *lchild, *rchild;
} tree;
/*
运用递归核算二叉树中一切叶子结点的个数。
ABD##E##C##
//                    A1
//                B2      C
//              D3   E4   F  #
//            #  # # # # #
 */
// 创建树
void createTre(tree*& root) {
    char a;
    cin >> a;
    if (a == '#') {
        root = NULL;
    } else {
        root = new tree();
        root->data = a;
        root->lchild = NULL;
        root->rchild = NULL;
        createTre(root->lchild);
        createTre(root->rchild);
    }
};
int n = 0;
void disp(tree* root) {
    if (root != NULL) {
        if (root->lchild == NULL && root->rchild==NULL) {
            n  ;
        };
        cout << root->data;
        disp(root->lchild);
        disp(root->rchild);
    }
}
int main() {
    tree* root;
    createTre(root);
    tree* q;
    cout << "递归前序遍历二叉树：";
    disp(root);
    cout << endl;
    cout<<"子树个数："<<n;
    return 0;
}

12 .找双分支节点

#include <bits/stdc  .h>
using namespace std;
typedef struct tree {
    char data;
    struct tree *lchild, *rchild;
} tree;
/*
运用递归核算二叉树中一切双分支结点个数
双分支节点：既有左子树又有右子树（如下图的：A1,B2）
ABD##E##C##
//                    A1
//                B2      C
//              D3   E4   F  #
//            #  # # # # #
 */
// 创建树
void createTre(tree*& root) {
    char a;
    cin >> a;
    if (a == '#') {
        root = NULL;
    } else {
        root = new tree();
        root->data = a;
        root->lchild = NULL;
        root->rchild = NULL;
        createTre(root->lchild);
        createTre(root->rchild);
    }
};
int n = 0;
void disp(tree* root) {
    if (root != NULL) {
        if (root->lchild != NULL &&
            root->rchild != NULL) {  // 当节点左右孩子不为空时，节点个数  
            n  ;
        };
        cout << root->data;
        disp(root->lchild);
        disp(root->rchild);
    }
}
int count3(tree* root) {
    int n1, n2;
    if (root == NULL) {  // 节点为空的时分，回来0
        return 0;
    } else if (root->lchild && root->rchild) {  // 双分支节点的状况
        n1 = count3(root->lchild);
        n2 = count3(root->rchild);
        return n1   n2   1;  // 这儿的 1是树自身的节点。重点留意
    } else {                 // 单分支和叶子节点的状况
        n1 = count3(root->lchild);
        n2 = count3(root->rchild);
        return n1   n2;
    }
};
int main() {
    tree* root;
    createTre(root);
    tree* q;
    cout << "递归前序遍历二叉树：";
    disp(root);
    cout << endl;
    cout << "双分支节点个数：" << n;
    return 0;
}