Can take you off [data structure] Chengwang Chapter 9: binary tree 2

K steady 2022-06-24 07:54:15 阅读数:765

datastructurechengwangchapterbinary

Catalog

Preface

Basic operations of binary tree

Get the number of nodes in the tree

Get the number of leaf nodes  

  For the first K The number of layer nodes

Get the height of the binary tree  

The detected value is val Does the element of exist  

Judge whether a tree is a complete binary tree  


Preface

Basic operations of binary tree

Get the number of nodes in the tree

Traversal thought code :

// Get the number of nodes in the tree
int count = 0;
public int size1(BTNode root){
if(root == null) {
return 0;
}
count ++;
count += size1(root.left);
count += size1(root.right);
return count;
}

Sub problem ideas :

// Sub problem ideas
public int size2(BTNode root){
if (root == null){
return 0;
}
return size2(root.left) + size2(root.right) + 1;
}

Get the number of leaf nodes  

Traversal ideas :

Traverse to the leaf node , Just let the counter ++

Leaf node :root.left == null && root.right == null

public int leafNodes(BTNode root){
int count = 0;
if(root == null){
return 0;
}
if(root.left == null && root.right == null){
count++;
}
leafNodes(root.left);
leafNodes(root.right);
return count;
}

Sub problem ideas :

Left tree leaf node plus right tree leaf node

public int leafNodes(BTNode root){
if(root == null){
return 0;
}
if(root.left == null && root.right == null){
return 1;
}
return leafNodes(root.left) + leafNodes(root.right);
}

  For the first K The number of layer nodes

hypothesis K be equal to 3

That is to say A The third floor of

B,C The second floor of

D,E,F,G The first floor of

Termination conditions K be equal to 1

public int getKLeveLNodeCount(BTNode root, int k){
if(root == null || k <= 0){
return 0;
}
if(k == 1){
return 1;
}
return getKLeveLNodeCount(root.left,k - 1) + getKLeveLNodeCount(root.right ,k-1);
}

Get the height of the binary tree  

 

Sub problem ideas

The height of the left tree and the height of the right tree are the maximum , Then add 1 = The height of the whole tree

public int getHeight(BTNode root){
if(root == null){
return 0;
}
int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;

The detected value is val Does the element of exist  

 public BTNode find(BTNode root,char val){
if(root == null){
return null;
}
if(root.val == val){
return root;
}
BTNode ret = find(root.left,val);
if(ret != null){
return ret;
}
ret = find(root.right,val);
if(ret != null){
return ret;
}
return null;
}

Judge whether a tree is a complete binary tree  

public boolean getHeight3(BTNode root){
if (root == null) return true;
Queue<BTNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()){
BTNode cur = queue.poll();
if (cur != null){
queue.offer(cur.left);
queue.offer(cur.right);
}else {
break;
}
}
while (!queue.isEmpty()){
BTNode ret = queue.peek();
if(ret != null){
return false;
}
queue.poll();
}
return true;
}

 

 

copyright:author[K steady],Please bring the original link to reprint, thank you. https://en.javamana.com/2022/175/202206240416400153.html