二叉树

1.链式二叉树的创建
2.前序遍历
- 2.1自定义输入数据
3.孩子兄弟表示法

1.链式二叉树的创建

ElementType.h

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 1024
#define NAME_SIZE 255
//数据元素
typedef struct{
    int id;
    char name[NAME_SIZE];
}ElementType;

TreeNode.h

#include "ElementType.h"

//树结点
typedef struct treeNode{
    ElementType data;//树结点的数据域
    struct treeNode *left;//左子树
    struct treeNode *right;//右子树
}TreeNode;

BinaryTree.h

#include "TreeNode.h"

//二叉链表
typedef struct{
TreeNode *root;//二叉树的根结点
int length;//结点总数
int depth;//二叉链表深度
int diameter;//直径-从叶结点到叶结点的最长路径
}BinaryTree;

//初始化空二叉树
void InitBinaryTree(BinaryTree * tree);

//创建二叉树，外部需要事先对结点分配内存
//返回值为0时表示不创建(创建失败)
int CreateBinaryTree(TreeNode *root);

//前序遍历,也叫先根遍历、先序遍历、前序周游，可以记作：根-左-右
void PreOrderTraverse(TreeNode *node);

BinaryTree.cpp

#include "BinaryTree.h"
#include <iostream>

//用来实现结点id的自增长
static int id=0;

//初始化空二叉树
void InitBinaryTree(BinaryTree * tree){
tree->root=NULL;
tree->depth=0;
tree->diameter=0;
tree->length=0;
}



//创建二叉树，外部需要事先对结点分配内存
int CreateBinaryTree(TreeNode *root){
    //根结点如果为空，就退出创建过程
    if(!root) return 0;
    char inputName[NAME_SIZE];//用户输入的结点名
    gets_s(inputName);
    //用户输入回车表示结束当前子树的创建
    if(strcmp(inputName,"\0")==0) return 0;
    //创建当前结点
    root->data.id=++id;
    strcpy(root->data.name,inputName);

    //为输入左右结点做准备，为左右结点指针分配内存
    root->left=(TreeNode *)malloc(sizeof(TreeNode));
    root->right=(TreeNode *)malloc(sizeof(TreeNode));
    //分别递归创造左子树和右子树
    printf("左结点：");
    if(CreateBinaryTree(root->left)==0){
    //不再创建这个结点则销毁结点刚分配的内存
        free(root->left);
        root->left=NULL;
    }
    printf("右结点：");
    if(CreateBinaryTree(root->right)==0){
    //不再创建这个结点则销毁结点刚分配的内存
        free(root->right);
        root->right=NULL;
    }

}

main.cpp

#include <iostream>
using namespace std;
#include "BinaryTree.h"

void TestBinaryTree();

int main(){
    TestBinaryTree();

    return 0;

}


void TestBinaryTree(){
BinaryTree tree;
InitBinaryTree(&tree);
//容易遗漏的点：根结点需要事先分配内存
tree.root=(TreeNode *)malloc(sizeof(TreeNode));
cout<<"请输入根结点"<<endl;
CreateBinaryTree(tree.root);
free(tree.root);
}

注意：

strcpy(root->data.name,inputName);

需要导入字符串的头文件

创建二叉树之前，必须事先分配好空间
2.前序遍历
2.1自定义输入数据
BinaryTree.cpp
```
//前序遍历
void PreOrderTraverse(TreeNode *node){
 //先访问根结点，然后遍历左子树，最后遍历右子树
 if(node){
     printf("[%d,%s]-",node->data.id,node->data.name);
     PreOrderTraverse(node->left);
     PreOrderTraverse(node->right);
 }
}
```
main.cpp ```cpp void TestBinaryTree(){ BinaryTree tree; InitBinaryTree(&tree); //容易遗漏的点：根结点需要事先分配内存 tree.root=(TreeNode *)malloc(sizeof(TreeNode)); cout<<”请输入根结点”<<endl; CreateBinaryTree(tree.root);

printf(“\n\n前序遍历结果：\n”); PreOrderTraverse(tree.root);

free(tree.root); }

![image.png](https://cdn.nlark.com/yuque/0/2021/png/22518174/1637415580347-01927f77-100b-4b4c-bcc0-3f6d635a9a71.png#clientId=ub51ae802-659e-4&crop=0&crop=0.0522&crop=1&crop=0.6869&from=paste&height=549&id=u08d22dd5&margin=%5Bobject%20Object%5D&name=image.png&originHeight=525&originWidth=757&originalType=binary&ratio=1&rotation=0&showTitle=false&size=21754&status=done&style=none&taskId=u61cacb55-584b-4e42-a44d-fa28f065ded&title=&width=791)

<a name="Vm2OD"></a>
### 2.2已知数据
BinaryTree.cpp
```cpp
//前序遍历
void PreOrderTraverse(TreeNode *node){
    //先访问根结点，然后遍历左子树，最后遍历右子树
    if(node){
        printf("[%d,%s]-",node->data.id,node->data.name);
        PreOrderTraverse(node->left);
        PreOrderTraverse(node->right);
    }

}dkk4114212212323szz

//模仿用户输入的顺序,#代表空
char *nodeNames[]={"a","b","d","#","#","e","#","#","c","f","#","#","g"};
//访问nodeNames数组中的下标
static int nodeNameIndex=0;

//模仿用户输入的顺序
int CreateBinaryTree_Test(TreeNode *root){
    //根结点如果为空，就退出创建过程
    if(!root) return 0;
    char inputName[NAME_SIZE];//用户输入的结点名
    strcpy(inputName,nodeNames[nodeNameIndex++]);
//    gets_s(inputName);
//用户输入回车表示结束当前子树的创建
    if(strcmp(inputName,"#")==0) return 0;
    //创建当前结点
    root->data.id=++id;
    strcpy(root->data.name,inputName);

    //为输入左右结点做准备，为左右结点指针分配内存
    root->left=(TreeNode *)malloc(sizeof(TreeNode));
    root->right=(TreeNode *)malloc(sizeof(TreeNode));
    //分别递归创造左子树和右子树
//printf("左结点：");
    if(CreateBinaryTree_Test(root->left)==0){
    //不再创建这个结点则销毁结点刚分配的内存
        free(root->left);
        root->left=NULL;
    }
//printf("右结点：");
    if(CreateBinaryTree_Test(root->right)==0){
    //不再创建这个结点则销毁结点刚分配的内存
        free(root->right);
        root->right=NULL;
    }
    return 1;
    }

main.cpp

#include <iostream>
using namespace std;
#include "BinaryTree.h"

void TestBinaryTree();

int main(){
    TestBinaryTree();

    return 0;

}


void TestBinaryTree(){
BinaryTree tree;
InitBinaryTree(&tree);
//容易遗漏的点：根结点需要事先分配内存
tree.root=(TreeNode *)malloc(sizeof(TreeNode));
CreateBinaryTree_Test(tree.root);
printf("\n\n前序遍历结果：\n");
PreOrderTraverse(tree.root);
free(tree.root);
}

2021.11.20 22：09

3.孩子兄弟表示法

ElementType.h

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 1024
#define NAME_SIZE 255
//数据元素
typedef struct {
    int id;
    char name[NAME_SIZE];
}ElementType;

Brother.h

//树的孩子兄弟表示法，优点：便于将一般的树结构转换为二叉树处理
#include "ElementType.h"
#include <String.h>

//孩子兄弟结点
typedef struct cbNode{
    ElementType data;
    struct cbNode * firstChild;//长子结点
    struct cbNode *nextSibling;//兄弟结点
}CBNode,*CBTree;

//初始化空树
void InitCBTree(CBTree *tree);

//构造树
void CreateCBTree(CBTree **node);

//先序遍历
void PreOrderCBTree(CBNode *node);

void TestCBTree();

Brother.cpp

#include "Brother.h"
static int id=0;

//初始化空树
void InitCBTree(CBTree *tree){
 *tree=(CBTree)malloc(sizeof(CBNode));
 (*tree)->firstChild=NULL;
 (*tree)->nextSibling=NULL;
}

//构造树
void CreateCBTree(CBNode **node){
    char inputName[255];
    gets_s(inputName);
    //判断用户输入的是否是回车键
    if(strcmp(inputName,"\0")==0) return;
    if(*node ==NULL){
        //如果为空，则分配内存
    *node=(CBNode *)malloc(sizeof(CBNode));
    (*node)->firstChild=NULL;
    (*node)->nextSibling=NULL;
    }
    //为结点赋值
    (*node)->data.id=++id;
    strcpy_s((*node)->data.name,inputName);
    //分别遍历输入长子结点和兄弟结点
    printf("请输入长子结点");
    CreateCBTree(&((*node)->firstChild));
    printf("请输入兄弟结点");
    CreateCBTree(&((*node)->nextSibling));

}

//先序遍历
void PreOrderCBTree(CBNode *node){
    if(node!=NULL){
        printf("[%d,%s]",node->data.id,node->data.id);
        CBNode *p =node->firstChild;
        PreOrderCBTree(p);
        while(p){
        p=p->nextSibling;
        PreOrderCBTree(p);
        }
    }

}


void TestCBTree(){
    CBTree tree;
     InitCBTree(&tree);
     printf("请输入一个根结点：");
     CreateCBTree(&tree);
     PreOrderCBTree(tree);
}

main.cpp

#include <iostream>
using namespace std;
#include "Brother.h"

void TestBinaryTree();

int main(){

    TestCBTree();
    return 0;

}

2021.11.22 22:22

1.链式二叉树的创建

2.前序遍历

2.1自定义输入数据

3.孩子兄弟表示法