全部博文（20）
分类： C/C++
2012-06-21 11:13:38
Tree structure is a commonly used data structure. However, I failed to implement an algorithm of converting all leaf nodes to a linked list in a recent interview. I am very disappointed about that. So I just reviewed this data structure and made small pieces of code for it.
A binary search tree (BST), which may sometimes also be called an ordered or sorted binary tree, is a node-based binary tree data structure which has the following properties:
1. 1. The left subtree of a node contains only nodes with keys less than the node’s key.
2. 2. The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
3. 3. Both the left and right subtrees must also be binary search trees.
Tree structure
struct BSTreeNode{
int data; //take int as an example
BSTreeNode *left;
BSTreeNode *right;
};
Tree traversal
There are several ways to traverse tree. Three methods are commonly used.
Preoder
/*
* Traverse a BST in preoder
* 1. Visit the root
* 2. Traverse the left subtree
* 3. Traverse the right subtree
*/
void preorder(BSTreeNode *root)
{
if (root != NULL)
{
printf("%d ", root->data);
preorder(root->left);
preorder(root->right);
}
}
Inorder
/*
* Traverse a BST in inorder
* 1. Traverse the left subtree
* 2. Visit the root
* 3. Traverse the right subtree
*
* the output of inorder is a sorted array in ascending order
*/
void inorder(BSTreeNode *root)
{
if (root != NULL)
{
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
Postorder
/*
* traverse a BST in postorder
* 1. Traverse the left subtree
* 2. Traverse the right subtree
* 3. Visit the root
*/
void postorder(BSTreeNode *root)
{
if (root != NULL)
{
postorder(root->left);
postorder(root->right);
printf("%d ", root->data);
}
}
Insert node
/*
* Helper function to allocate a new node with given data and NULL left and right pointers
*/
BSTreeNode *newNode(int data)
{
BSTreeNode *node = new BSTreeNode;
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
/*
* insert a node
*
* return the inserted node
* if root == NULL, the return will be the root the tree
*/
BSTreeNode *insert(BSTreeNode *root, int data)
{
if (root == NULL) {
return newNode(data);
}
else {
if (data < root->data) {
root->left = insert(root->left, data);
}
else {
root->right = insert(root->right, data);
}
return root;
}
}
Create a BST from an array
/*
* Create BSTree by a given array
*/
BSTreeNode *createBSTree(int array[], int n){
if (array == NULL || n < 1) {
return NULL;
}
BSTreeNode *root = NULL;
for (int i=0; i<n; i++) {
root = insert(root, array[i]);
}
return root;
}
Delete tree
/*
* delete tree
* delete tree in postorder
*/
void deleteTree(BSTreeNode *node) {
if (node != NULL) {
deleteTree(node->left);
deleteTree(node->right);
delete node;
}
}
Print leaf nodes
/*
* print all leaf node in a BST
*/
void printLeafNode(BSTreeNode *node) {
if (node != NULL) {
if (node->left == NULL && node->right == NULL) {
// leaf node
printf("%d ", node->data);
}
else {
printLeafNode(node->left);
printLeafNode(node->right);
}
}
}
Convert all leaf nodes to a linked list
struct LinkedList{
int data;
LinkedList *next;
};
/*
* Helper function to create a linked list node with given data and NULL next pointer
*/
LinkedList *newLinkedList(int data) {
LinkedList *list = new LinkedList;
list->data = data;
list->next = NULL;
return list;
}
/*
* Convert leaf node in a BST to linked list
*
* prerequisite: list pointer cannot be null
* return the end node of the converted linked list
*/
LinkedList *leafNode2LinkedList(BSTreeNode *node, LinkedList *list) {
if (list == NULL) {
return NULL;
}
if (node == NULL) {
return list;
}
LinkedList *cur = NULL;
if (node->left == NULL && node->right == NULL) {
// leaf node
cur = newLinkedList(node->data);
list->next = cur;
list = cur;
}
else {
// left subtree first
cur = leafNode2LinkedList(node->left, list);
if (cur != NULL) {
list = cur;
}
// right subtree
cur = leafNode2LinkedList(node->right, list);
if (cur != NULL) {
list = cur;
}
}
return list;
}
/*
* Convert a BST to a linked list
*
* return the head of linked list
*/
LinkedList *leafNode2LinkedList(BSTreeNode *root)
{
// allocate a placeholder
LinkedList *head = newLinkedList(0);
leafNode2LinkedList(root, head);
LinkedList *list = head->next;
delete head;
return list;
}
Normal 0 false false false EN-CA ZH-CN X-NONE MicrosoftInternetExplorer4 /* Style Definitions */ table.MsoNormalTable {mso-style-name:"Table Normal"; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-noshow:yes; mso-style-priority:99; mso-style-qformat:yes; mso-style-parent:""; mso-padding-alt:0cm 5.4pt 0cm 5.4pt; mso-para-margin-top:0cm; mso-para-margin-right:0cm; mso-para-margin-bottom:10.0pt; mso-para-margin-left:0cm; line-height:115%; mso-pagination:widow-orphan; font-size:11.0pt; font-family:"Calibri","sans-serif"; mso-ascii-font-family:Calibri; mso-ascii-theme-font:minor-latin; mso-hansi-font-family:Calibri; mso-hansi-theme-font:minor-latin; mso-bidi-font-family:"Times New Roman"; mso-bidi-theme-font:minor-bidi;}
Count the number of a tree
/*
* count the number in a BST
*/
Normal 0 false false false EN-CA ZH-CN X-NONE /* Style Definitions */ table.MsoNormalTable {mso-style-name:"Table Normal"; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-noshow:yes; mso-style-priority:99; mso-style-qformat:yes; mso-style-parent:""; mso-padding-alt:0cm 5.4pt 0cm 5.4pt; mso-para-margin-top:0cm; mso-para-margin-right:0cm; mso-para-margin-bottom:10.0pt; mso-para-margin-left:0cm; line-height:115%; mso-pagination:widow-orphan; font-size:11.0pt; font-family:"Calibri","sans-serif"; mso-ascii-font-family:Calibri; mso-ascii-theme-font:minor-latin; mso-hansi-font-family:Calibri; mso-hansi-theme-font:minor-latin; mso-bidi-font-family:"Times New Roman"; mso-bidi-theme-font:minor-bidi;}int countTree(BSTreeNode *node) {
if (node == NULL) {
return 0;
}
int left = countTree(node->left);
int right = countTree(node->right);
return left + right + 1;
}
Calculate the max depth(height)
/*
* calculate the max depth of a tree
*/
int maxDepth(BSTreeNode *node) {
if (node == NULL) {
return 0;
}
int leftDepth = maxDepth(node->left);
int rightDepth = maxDepth(node->right);
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
references:
Introduction to Algorithms. Thomas.H.Cormen,Ronald.L.Rivest, Charles.E.Leiserson, Clifford.Stein
