二叉樹數據結構


難度級別 容易獎學金
經常問 DBOI 事實集 印孚瑟斯 空氣質量 神諭
二叉樹 數據結構 理論

在本文中,我們將了解二叉樹數據結構。 是分層數據結構,其中每個節點都有一個除根節點之外的父節點。 沒有子節點的節點稱為葉子。

需要樹木嗎?

1.當我們需要以某種層次結構的形式存儲數據時,使用樹。 示例:-文件系統。

2.像BST這樣的樹提供O(logN)複雜性的訪問,這比鏈接列表要快。

3.樹沒有定義的大小,並且可以將任意數量的節點添加到Tree數據結構中。

二叉樹

二叉樹數據結構是分層數據結構。 最多有兩個孩子的樹稱為二叉樹。 這兩個孩子通常被稱為左,右孩子。

二叉樹由三部分組成:

  1. 節點值
  2. 指向左側子樹的指針
  3. 指向右子樹的指針

 

指向左孩子的指針值 指向正確的孩子的指針

如果根指向 那是一棵空樹。

二叉樹數據結構的節點

struct TreeNode
{
int data;
struct TreeNode *left;
struct TreeNode *right;
};

 

二叉樹數據結構

二叉樹中使用的術語

  • 根: It是一個節點指針變量,指向樹的根節點。 當root包含null時,樹為空。
  • 葉: 具有零度的節點。 也稱為外部節點。
  • 內部節點: 至少有一個孩子的節點。
  • 學位: 節點的子級總數稱為其度。
  • 樹度: 樹的度數是所有節點的最大度數。
  • 等級: 它是從根到給定節點-1的節點總數。
  • 節點高度: 它是從根到給定節點的節點總數

在這裡,樹節點中的整數值可以用任何數據類型ex代替。 字符串,字符,數組等。這就是一棵樹的樣子

TREE 
              1 <-- root node 
             / \ 
            2   3 <-- leaf node 
          / 
         4 <- leaf node

二叉樹數據結構的C ++代碼

//C++ Code


#include<bits/stdc++.h>
using namespace std ;


struct TreeNode
{
int data;
struct TreeNode *left;
struct TreeNode *right;
};


/* CreateNode() creates a new node with the given data with NULL left and right pointers. */


TreeNode* CreateNode(int data)
{
// Allocate memory for new node
TreeNode* NewNode = new TreeNode ;


// Assign data to this node
NewNode->data = data;


// Initialize left and right children as NULL
NewNode->left = NULL;
NewNode->right = NULL;


return(NewNode);


}




int main()
{
/*create root with data value 1*/
struct TreeNode *root = CreateNode(1);


/* following is the tree after above statement


                    1
                  /   \
               NULL   NULL
*/


root->left = CreateNode(2);
root->right = CreateNode(3);




/* 2 and 3 become left and right children of 1
                             1
                          /     \
                        2         3
                    /      \    /    \
                  NULL    NULL NULL   NULL
*/




root->left->left = CreateNode(4);




/* 4 becomes left child of 2
                                      1
                                  /       \
                                 2          3
                              /    \     /     \
                             4   NULL   NULL   NULL
                           /   \
                        NULL   NULL
*/
return 0 ;
}

二叉樹數據結構的Java代碼

/* Class containing left and right child of current 
node and key value*/
class Node 
{ 
	int key; 
	Node left, right; 

	public Node(int item) 
	{ 
		key = item; 
		left = right = null; 
	} 
} 

// A Java program to introduce Binary Tree 
class BinaryTree 
{ 
	// Root of Binary Tree 
	Node root; 

	// Constructors 
	BinaryTree(int key) 
	{ 
		root = new Node(key); 
	} 

	BinaryTree() 
	{ 
		root = null; 
	} 

	public static void main(String[] args) 
	{ 
		BinaryTree tree = new BinaryTree(); 

		/*create root*/
		tree.root = new Node(1); 

		/* following is the tree after above statement 

			1 
			/ \ 
		null null	 */

		tree.root.left = new Node(2); 
		tree.root.right = new Node(3); 

		/* 2 and 3 become left and right children of 1 
			1 
			/ \ 
			2	 3 
		/ \ / \ 
		null null null null */


		tree.root.left.left = new Node(4); 
		/* 4 becomes left child of 2 
					1 
				/	 \ 
			2		 3 
			/ \	 / \ 
			4 null null null 
		/ \ 
		null null 
		*/
	} 
} 

二叉樹數據結構的屬性

  1. 高度為H = H + 1的二叉樹中的最小節點數。
  2. 高度為H = 2的二叉樹中的最大節點數高+1 - 1
  3. 二叉樹中的葉節點總數=具有2個子節點的節點總數+ 1
  4. 二叉樹中任何級別“ L”的最大節點數= 2L

概要

1.二叉樹是每個節點最多有兩個孩子的樹。

2.沒有子節點的節點稱為葉,起始節點稱為根節點。

3.樹提供操作:訪問,插入,刪除比數組中的操作更快。

參考