C高级编程 第十六天（树 二叉树）

1.树

1.1结构特点

• 非线性结构，有一个直接前驱，但可能有多个直接后继
• 有递归性，树中还有树
• 可以为空，即节点个数为零

1.2相关术语

• 根：即根结点，没有前驱
• 叶子：即终端结点，没有后继
• 森林：即树的集合
• 结点的度：直接后继的个数
• 树的度：结点的度的最大值
• 树的深度高度：结点的最大层数

1.3树的表示法

1.3.1图形表示法

1.3.2广义表表示法

1.3.3左孩子右兄弟表示法

将一颗多插树转化为二叉树，如下

其中，结点结构为

左结点为孩子结点，右节点为兄弟结点

2.二叉树

2.1定义

一个根节点和两棵不相交的二叉树组成，即1:2

2.2基本特征

每个节点最多有两棵子树——每个节点的度<=2

左子树和右子树的顺序不能颠倒——有序树

2.3二叉树性质

满二叉树：深度为k，有2^k-1个节点

完全二叉树：除最后一层，每一层节点数达到最大值，在最后一层只缺右边的若干节点

2.4二叉树的遍历

//单个结点
struct BinaryNode
{char ch;struct BinaryNode* lChild;struct BinaryNode* rChild;
};

void test()
{struct BinaryNode A = { 'A',NULL,NULL };struct BinaryNode B = { 'B',NULL,NULL };struct BinaryNode C = { 'C',NULL,NULL };struct BinaryNode D = { 'D',NULL,NULL };struct BinaryNode E = { 'E',NULL,NULL };struct BinaryNode F = { 'F',NULL,NULL };struct BinaryNode G = { 'G',NULL,NULL };struct BinaryNode H = { 'H',NULL,NULL };//创建节点之间的关系A.lChild = &B;A.rChild = &F;B.rChild = &C;C.lChild = &D;C.rChild = &E;F.rChild = &G;G.lChild = &H;//先序遍历printf("先序遍历\n");PreorderTraversal(&A);printf("中序遍历\n");InorderTraversal(&A);printf("后序遍历\n");PostorderTraversal(&A);
}

先序遍历：DLR

//DLR
void PreorderTraversal(struct BinaryNode* node)
{if (node == NULL){return NULL;}printf("%c\n",node->ch);PreorderTraversal(node->lChild);PreorderTraversal(node->rChild);
}

中序遍历：LDR

//LDR
void InorderTraversal(struct BinaryNode* node)
{if (node == NULL){return NULL;}InorderTraversal(node->lChild);printf("%c\n", node->ch);InorderTraversal(node->rChild);
}

后序遍历：LRD

//LRD
void PostorderTraversal(struct BinaryNode* node)
{if (node == NULL){return NULL;}PostorderTraversal(node->lChild);PostorderTraversal(node->rChild);printf("%c\n", node->ch);
}

2.5统计二叉树的叶子数量

左孩子和右孩子都为空指针时，即为叶子结点

//统计叶子数量
void calculateLeadNum(struct BinaryNode* root, int* p)
{if (root == NULL){return NULL;}if (root->lChild == NULL && root->rChild == NULL){(*p)++;}calculateLeadNum(root->lChild, p);calculateLeadNum(root->rChild, p);
}

2.6统计二叉树的高度

比较左子树和右子树的高度，取最大的一个加一，即为树的高度

//计算树的高度
int calculateHeight(struct BinaryNode* root)
{if (root == NULL){return NULL;}int lp = calculateHeight(root->lChild);int rp = calculateHeight(root->rChild);int height = lp > rp ? lp + 1 : rp + 1;return height;
}

2.7拷贝二叉树

• 拷贝左子树
• 拷贝右子树
• 创建新节点
• 将拷贝的左子树和右子树挂载到新节点上
• 将新节点赋值

//拷贝二叉树
struct BinaryNode* copyTree(struct BinaryNode* root)
{if (root == NULL){return NULL;}struct BinaryNode* lp=copyTree(root->lChild);struct BinaryNode* rp=copyTree(root->rChild);struct BinaryNode* newNode = malloc(sizeof(struct BinaryNode));if (newNode == NULL){return;}newNode->lChild = lp;newNode->rChild = rp;newNode->ch = root->ch;return newNode;
}

2.8释放二叉树

• 释放左子树
• 释放右子树
• 释放根节点

//释放二叉树
void releaseTree(struct BinaryNode* root)
{if (root == NULL){return NULL;}releaseTree(root->lChild);releaseTree(root->rChild);printf("%c结点已被释放", root->ch);releaseTree(root);
}

2.9二叉树的非递归遍历

将每个节点设一个标志，默认false

（1）将根节点压入栈中

（2）进入循环（只要栈中元素个数大于0，进行循环操作）

• 弹出栈顶元素
• 若栈顶元素标志为true，输出此元素并执行下一次循环
• 若栈顶元素标志为false，将节点标志设为true
• 将该节点的右子树、左子树、根压入栈中
• 执行下一次循环