Using a binary linked list as the storage structure, how to write an algorithm to find the parents o

It's not easy to find your parents...

Wouldn't it be nice to have a pointer to your father at each node...

class treenode

public:

int data;

treenode *lef,*rig,*parent;

The parent of root is null, and the parent of other points is his parent.

The maintenance of the parent can be carried out when the achievement is made, and it is good to point directly to the father.

The binary linked list is used as the storage structure of the binary tree, and the number of empty chain fields in the binary linked list with n nodes is n(n 0), and the number of empty chain fields is n+1.

Binary linked list structure description:

typedef struct csnode csnode，* cstree;

Because the storage structure of binary trees is relatively simple and easy to process, it is sometimes necessary to convert complex trees into simple binary trees before processing.

There are n+1 empty domains in a binary tree binary linked list for n nodes, and n empty chain fields in a trinominate linked list (with one more empty chain field in the root node).

The degree of a binary tree represents the number of subtrees or direct successors of a node, and the degree of a binary tree is a subtree or monad. 2 degrees is two children, or the left and right subtrees have two forks with a maximum degree of 2.

Using the binary linked list as the storage structure of the binary tree, the algorithm C++ of "swapping the left and right children of each node of the binary tree" and "counting the number of branch nodes of the binary tree" was written

The binary linked list is used as the storage structure of the binary tree, and the left and right children of each node in the binary tree are exchanged. Input Format: Enter the precedent sequence of the binary tree.

The output has two rows: the first row is the middle-order traversal sequence of the original binary tree; The second row is the middle-order traversal sequence of the swapped binary tree.

Using the binary linked list as the storage structure of the binary tree, the recursive equation used to determine whether two trees are equal is .

Hello, dear, using the binary linked list as the storage structure of the binary tree, the recursive equation used to determine whether two trees are equal is that the depth of a complete binary tree with n nodes is log2n +1 !! The calculation method of binary tree: if a binary tree is empty, its depth is 0, otherwise its depth is equal to the maximum depth of the left subtree and the right subtree plus 1, that is, there is the following recursive model:

depth(b)=0 *if b=null* depth(b)=max(depth(b->left,b->right)+1 *other* Therefore, the recursive function for finding the depth of the two-mode fork tree is as follows: int depth(btree *b)} Basic properties of the binary tree Basic definition of a tree 1. A tree is n(n>=0) a finite set of nodes2, the node of the tree contains a data element and a number of branches pointing to its subtrees3, the number of subtrees owned by the node is called the degree of the node4, the node with a degree of 0 is called the leaf or terminal node5, the degree of the tree is the maximum value of the degree of each node in the tree6, the level of the node is defined from the root, the root is the first layer, and the child of the root is the second layer7, the maximum level of the node in the tree is called the depth or height of the tree8, If the subtrees of nodes in a tree are considered to be ordered from left to right (i.e., not interchangeable), the tree is called ordinal, otherwise it is called an unordered tree. In an ordered tree, the root of the leftmost subtree is called the first child, and the rightmost one is called the last child.

Definition of Binary Tree Binary tree is a tree-type structure, which is characterized by the fact that each node has at most two subtrees (that is, there are no nodes with a degree greater than 2 in the binary tree), and the subtrees of the binary tree are divided into left and right, and the order cannot be arbitrarily reversed. Nature of the binary tree: 1 On the ith layer of the binary tree, there are at most 2i-1 nodes, and the property of 2 is 2k-1 nodes (k> in the depth of k=1) Property 3 For any binary tree t, if the number of terminal nodes is n0 and the number of nodes with degree 2 is n2, then n0=n2+1 property 4 The depth of a complete binary tree with n nodes is log2n +1 property 5 If the nodes of a complete binary tree with n nodes (its depth log2n +1) are numbered in order (from layer 1 to log2n +1, each layer from left to right), then for any node i(1 i n).

A recursive algorithm is written to output all the nodes of degree 2 in the binary tree stored in the binary linked list in order of precedence.

Write a recursive algorithm to output all the nodes of degree 2 in the binary tree stored in the binary linked list in the preceding order Hello dear, wrong. In a binary tree, not every node has a degree of 2. The degree of a node refers to the number of its direct child nodes.

For a binary tree, if both the left and right subnodes of a node exist, the degree is 2; If there is only a left or right subnode, the degree is 1; If it is a leaf node, the degree is 0. In a non-empty binary tree, there may not be nodes with degrees of 1 or 2, but there must be nodes with degrees of 0. Also, the number of nodes with degree 0 is always 1 more than the number of nodes with degree 2.

Summary. Kiss <>

Hello, let me assume that the binary tree t uses the binary chain as the storage structure, design an algorithm, and find the number of leaf nodes in the binary tree t assuming that the binary tree t uses the binary chain as the storage structure, design an algorithm to find the number of leaf nodes in the binary tree t The leaf nodes of the binary tree refer to the nodes without child nodes. Therefore, we can use a recursive approach to solve this problem. The algorithm process is as follows:

If the current node is empty, 0 is returned. If the current node is a leaf node, 1 is returned.

Assuming that the binary tree t uses the binary chain as the storage structure, an algorithm is designed to find the number of leaf nodes in the binary tree t.

Kiss <>

Hello, let me assume that the binary tree t uses the binary chain as the storage structure, design an algorithm, and find the number of leaf nodes in the binary tree t assuming that the binary tree t uses the binary chain as the storage structure, design an algorithm to find the number of leaf nodes in the binary tree t The leaf nodes of the binary tree refer to the nodes without child nodes. Therefore, we can use a recursive approach to solve this problem. The algorithm process is as follows:

If the current node is empty, 0 is returned. If the current node is a leaf node, 1 is returned.

Kiss <>

If the current node is not a leaf node, the number of leaf nodes in its left and right subtrees is recursively counted and they are added. Here's an algorithm implemented in C++: In this section, Struct TreeNode defines the structure of a binary tree node, with root->left and root->right representing the left and right subnodes of the current node, respectively.

Time complexity: o(n), where n is the number of nodes in the binary tree. Space Complexity:

o(h), where h is the height of the binary tree. Since recursion is used, the spatial complexity of the algorithm depends on the depth of the recursion stack, i.e., the height of the binary tree.

1. First of all, we need to define two classes: the node class and the binary tree class.

2. The composition of the binary tree class: the function of establishing the tree, the traversal function, and the deletion function. Find the number of nodes function.

3. Using the idea of recursion, encountering an identifier indicates that the node is empty, otherwise open up space to create a new node, and call recursion to open up the left node and the right node at the same time.

4. Pre-order traversal function.

5. The idea of deleting the function: if the current node is not empty, use recursive access to the space of the left node, the right node, and the current node.

6. The idea of finding the node number function: if the current node is empty, return 0, and if the left and right children of the current node are empty, put back to 1.

7. The idea of finding the tree height function: if the current node is empty, return 0, recursively access the left and right children, compare the height of the left and right children, and return a larger value of +1.

Algorithm Steps:

Set the root node to r.

In case 1, if r has both left and right children, then return 1 + recursively find the left subtree as the number of nodes as 2 nodes + recursively find the right subtree as the number of nodes as 2 nodes.

In case 2, if r has only the left child, then return recursively to find the left subtree degree to be 2 nodes.

In case 3, if r has only the right child, then return recursively to find the right subtree degree to be 2 nodes.

Case 4, if r has neither a left child nor a right child, 0 is returned.