[C++知识库]二叉树的编程

一.树的遍历

二.统计叶子的数量

三.求树的高度

四.拷贝二叉树

五.释放二叉树

binaryTree.h

?
#pragma once
#include<stdio.h>
#include<string>
#include<stdlib.h>
struct BinaryNode
{
char ch;//数据域
struct BinaryNode* lChild;//左孩子节点
struct BinaryNode* rChild;//右孩子节点
};
//遍历树
void showBinaryTree(struct Binary*rrot);
//统计叶子的数量
void calculateLeafNum(struct BinaryNode*root,int num);
//求树的高度
int getTreeHeight(struct BinaryNode*root);
//拷贝二叉树
struct BinaryNode*copyBinaryTree(struct BinaryNode*root);
//释放二叉树
void freeTree(struct BinaryNode*root);

tset.c

void tset()
{
struct BinaryNode nodeA={'A',NULL,NULL};
struct BinaryNode nodeB={'B',NULL,NULL};
struct BinaryNode nodeC={'C',NULL,NULL};
struct BinaryNode nodeD={'D',NULL,NULL};
struct BinaryNode nodeE={'E',NULL,NULL};
struct BinaryNode nodeF={'F',NULL,NULL};
struct BinaryNode nodeG={'G',NULL,NULL};
struct BinaryNode nodeH={'H',NULL,NULL};
//建立节点关系
nodeA.lChild=&nodeB;
nodeA.rChild=&nodeF;
nodeB.rChild=&nodeC;
nodeC.rChild=&nodeE;
nodeC.lChild=&nodeD;
nodeF.rChild=&nodeG;
nodeG.lChild=&nodeH;

//1.递归遍历
showBinaryTree(&nodeA)

//2.求叶子的数量
int num=0;
calculateLeafNum(nodeA,&num);
printf("叶子的数量为：%d\n",num)

//3.求树的高度/深度
int height=getTreeHeight(&nodeA);
printf("树的高度为：%d\n",height);

//4.拷贝二叉树
struct BinaryNode*newTree=copyBinaryTree(&nodeA);
showBinaryTree(newTree);
printf("\n");

//释放二叉树
freeTree(newTree);
}
int main()
{
tset()
systrm("puase");
return EXIT_SUCCESS;
}

binaryTree.c

include"binaryTree.h"
                        //遍历树
void showBinaryTree(struct Binary*rrot)
{
if(NULL==root)
{
return;
}
printf("%c",root->ch);
showBinaryTree(root->lChild);
showBinaryTree(root->rChild);
}
                                //统计叶子的数量
void calculateLeafNum(struct BinaryNode*root,int num)
{
if(NULL= root)
{
return;
}
if(root->lChild==NULL&&root->rChild==NULL)
{
(*num)++;
}
calculateLeafNum(root->lChid,num);
calculateLeafNum(root->rChid,num);

}
                              //求树的高度
int getTreeHeight(struct BinaryNode*root)
{
if(NULL == root)
{
return NULL;
}
//求出叶子的高度
int lHeight=getTreeHeight(root->lHeight);
int rHeight-getTreeHeight(root->rHeight);
//取左子树 和右子树中的最大值+1
int height=lHeight>rHeight?lHeight+1:rHeight+1;
return height
}
                            //拷贝二叉树
struct BinaryNode*copyBinaryTree(struct BinaryNode*root)
{
if(NUUl==root)
{
return NULL;
}
//先拷贝左子树
struct BinaryNode*copyBinaryTree(root->lChild);
//在拷贝右子树
struct BinaryNode*copyBinaryTree(root->rChild);
//创建新的节点
struct Binary*newNode=malloc(sizeof(struct(struct BinaryNode));
newNode->lChild=lChild;
newNode->rChild=rChild;
newNode->ch=root->ch;
//返回给用户
return newNode;
}
                        //释放二叉树
void freeTree(struct BinaryNode*root)
{
if(NULL==root)
{
return ;
}
//先舒服左子树
freeTree(root->lChild);
//再释放右子树
freeTree(root->rChild);
printf("%c 被释放了"，root->ch);
//释放根节点
freeTree(root);
}