Shulou(Shulou.com)05/31 Report--

This article mainly explains "C language binary tree concept is what and how to use," interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Let Xiaobian take you to learn "what is the concept of C language binary tree and how to use it"!

1. Concept and Structure of Binary Tree

A binary tree is a finite set of nodes that is either empty or consists of a root node plus two binary trees called left and right subtrees.

Characteristics of binary tree:

Each node has at most two subtrees, i.e. nodes with non-existence degree greater than 2. (Maximum of 2 degrees)

The subtree of a binary tree has left and right points, and the order of its subtrees cannot be reversed.

3. Binary tree in reality:

When an ordinary person looks at such a tree, he might think: Good standard tree.

When an ape looks at such a tree, it might think: It's like a binary tree in a data structure, and it's a full binary tree.

4. Binary tree in data structure:

Note: Binary trees have at most two degrees

5 Special binary tree:

Full binary tree: A binary tree is a full binary tree if the number of nodes in each layer reaches the maximum. That is, if a binary tree has K levels and the total number of nodes is (2^k)-1, then it is a full binary tree.

Complete binary tree: Complete binary tree is a very efficient data structure, complete binary tree is derived from full binary tree. A binary tree of depth K with n nodes is called a complete binary tree if and only if each node corresponds to nodes numbered 1 to n in a full binary tree of depth K. Note that a full binary tree is a special type of complete binary tree.

⑥二叉树的存储结构： 二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。

⑦二叉树的性质：

若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1) 个结点.

若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h- 1.

对任何一棵二叉树, 如果度为0其叶结点个数为 n0, 度为2的分支结点个数为 n2,则有n0=n2 +1

若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=log₂n+1

⑧练习题

2.二叉树链式结构的实现

①二叉树链式结构的遍历 ：

所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访 问结点所做的操作依赖于具体的应用问 题。 遍历是二叉树上最重要的运算之一，是二叉树上进行 其它运算之基础。

前序/中序/后序的递归结构遍历：是根据访问结点操作发生位置命名

前序（先根）：先访问根节点，然后访问左子树，最后访问右子树

中序（中根）：先访问左节点，然后访问根节点，最后访问右子树

后序（后根）：先访问左节点，然后访问右子树，最后访问根节点

先定一个结构体类型：

typedef char BTDataType;typedef struct BinarytreeNode{ BTDataType data; struct BinarytreeNode* left; struct BinarytreeNode* right;}BTNode;

前序：

void Preamble(BTNode* p)//前序{ if (p == NULL) { printf("NULL "); return; } printf("%c ", p->data); Preamble(p->left); Preamble(p->right);}

中序：

void Morder(BTNode* p)//中序{ if (p == NULL) { printf("NULL "); return; } Morder(p->left); printf("%c ", p->data); Morder(p->right);}

后序：

void Porder(BTNode* p)//后序{ if (p == NULL) { printf("NULL "); return; } Porder(p->left); Porder(p->right); printf("%c ", p->data);}

求二叉树结点的个数：

int treeSize(BTNode* p)//结点个数{ return p == NULL ? 0 : treeSize(p->left) + treeSize(p->right)+1;}

求叶子结点的个数：

int treeLeafSize(BTNode* p)//叶子结点个数{ if (p == NULL) { return 0; } if (p->left == NULL&&p->right == NULL) { return 1; } return treeLeafSize(p->left) + treeLeafSize(p->right);}到此，相信大家对"C语言二叉树的概念是什么及怎么使用"有了更深的了解，不妨来实际操作一番吧!这里是网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.