Shulou(Shulou.com)06/03 Report--

In this issue, the editor will bring you how to write the recursive algorithm C code about the three ways of traversing the binary tree. the article is rich in content and analyzes and describes it from a professional point of view. I hope you can get something after reading this article.

Basic concept

Tree structure is a kind of important nonlinear data structure, in which tree and binary tree are the most commonly used.

A binary tree is an ordered tree with at most two subtrees per node. The roots of subtrees are usually called "left subtrees" (left subtree) and "right subtrees" (right subtree). Binary trees are often used as binary search trees and binary heaps or binary sort trees. Each node of a binary tree has at most two subtrees (there are no nodes with a degree greater than 2). The subtrees of a binary tree can be divided into left and right, and the order can not be reversed. The I layer of a binary tree has at most 2 I-1 nodes; a binary tree with a depth of k has at most 2 ^ (k)-1 nodes; for any binary tree T, if the number of terminal nodes (that is, the number of leaf nodes) is n 0, and the number of nodes with degree 2 is n 2, then n 0

= N2 + 1.

Traversal of the binary tree:

Traversal is one of the most basic operations on the tree. the so-called traversing binary tree is to walk through all the nodes of the binary tree according to certain rules and order, so that each node is visited once and only once. Because the binary tree is a nonlinear structure, the traversal of the tree is essentially represented by transforming each node of the binary tree into a linear sequence.

There are three recursive traversal methods for binary trees:

Preorder traversal access root node → preorder traversal left subtree → preorder traversal right subtree order traversal left subtree → access root node → order traversal right subtree → order traversal right subtree → access root node preorder traversal / * establishment of binary tree and C code implementation of preorder traversal * / # include # include typedef char ElemType;typedef struct BiTNode {char data Struct BiTNode * lchild, * rchild;} BiTNode, * BiTree;// create binary tree data void CreatBiTree (BiTree * T) {ElemType c; scanf ("% c", & c); if ('^'= = c) {* T = NULL) } else {* T = (BiTree) malloc (sizeof (BiTNode)); (* T)-> data = c; CreatBiTree (& (* T)-> lchild); CreatBiTree (& (* T)-> rchild)) Void visit (BiTree T, int level) {printf ("% c in layer d\ n", T-> data, level);} / / traverse binary tree void PreOrderTraverse (BiTree T, int level) {if (T, level) {visit (T, level); PreOrderTraverse (T-> lchild, level+1) PreOrderTraverse (T-> rchild, level+1);}} int main () {BiTree T; CreatBiTree (& T); PreOrderTraverse (T, 1); return 0;} sequence traversal / * medium order traversal of binary tree print node data * / # include # include typedef char Elemtype;// create binary tree node structure typedef struct BiTNode {Elemtype data; struct BiTNode * lchild, * rchild } BiTNode, * BiTree;// preorder traverses the input binary tree node data to create a binary tree void CreateBiTree (BiTree * t) {Elemtype c; scanf ("% c", & c); if (''= = c) * t = NULL; else {(* t) = (BiTree) malloc (sizeof (BiTNode)) (* t)-> data = c; CreateBiTree (& (* t)-> lchild); CreateBiTree (& (* t)-> rchild);}} / / access binary tree node data function void visit (BiTree t) {printf ("% c", t-> data) } / / order traversal binary tree function void InOrderTraverse (BiTree t) {if (t) {InOrderTraverse (t-> lchild); visit (t); InOrderTraverse (t-> rchild);}} int main () {BiTree t; printf ("Please enter data in the preorder traversal order to build a binary tree:\ n"); CreateBiTree (& t) InOrderTraverse (t); printf ("\ n"); return 0;} Post-order traversal / * C code implementation of subsequent traversal of binary tree * / # include # include typedef char Elemtype;// create binary tree node structure typedef struct BiTNode {Elemtype data; struct BiTNode * lchild, * rchild;} BiTNode, * BiTree;// preorder traversal input to create binary tree void CreateBiTree (BiTree * t) {Elemtype c Scanf ("% c", & c); if ('= = c) (* t) = NULL; else {(* t) = (BiTree) malloc (sizeof (BiTNode)); (* t)-> data = c; CreateBiTree (& (* t)-> lchild); CreateBiTree (& (* t)-> rchild) }} / / access function void visit (BiTree t) {printf ("% c", t-> data);} / / Post-order traversal binary tree void PostOrderTraverse (BiTree t) {if (NULL = = t) return; else {PostOrderTraverse (t-> lchild); PostOrderTraverse (t-> rchild); visit (t) }} int main () {BiTree t; printf ("Please enter the node sequence of the binary tree in advance:\ n"); CreateBiTree (& t); PostOrderTraverse (t); printf ("\ n"); return 0 } the above is how to write the C code of the three recursive algorithms for traversing the binary tree shared by the editor. If you happen to have similar doubts, please refer to the above analysis to understand. If you want to know more about it, you are welcome to follow the industry information channel.

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.