C/C++ 习题. 树

树，

 

题目1：
输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点，只调整指针的指向。

      10
     /   \
    6     14
  / \      / \
4   8  12 16

转换成双向链表
4=6=8=10=12=14=16。

解答：
首先需要理解如下基本概念:
1. 二元查找树.(Binary Search Tree)
对于每个结点，其左子树中的数据值都小于结点本身的值，而右子树种的数据值都大于或等于结点值。
The value of the key of an element is greater than the value of the key of any element in its

left subtree, and less than the vlue of the key of any element in its right subtree.

2. 双向链表.
结点里面含有两个指针域(Left, Right),一个数据域(data).

我们定义的二元查找树 节点的数据结构如下：
struct BSTreeNode
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node
};

ANSWER:
This is a traditional problem that can be solved using recursion.
For each node, connect the double linked lists created from left and right child node to form a full list.

/**
* @param root The root node of the tree
* @return The head node of the converted list.
*/
BSTreeNode * treeToLinkedList(BSTreeNode * root) {
BSTreeNode * head, * tail;
helper(head, tail, root);
return head;
}

void helper(BSTreeNode *& head, BSTreeNode *& tail, BSTreeNode *root) {
BSTreeNode *lt, *rh;
if (root == NULL) {
head = NULL, tail = NULL;
return;
}
helper(head, lt, root->m_pLeft);
helper(rh, tail, root->m_pRight);
if (lt!=NULL) {
lt->m_pRight = root;
root->m_pLeft = lt;
} else {
head = root;
}
if (rh!=NULL) {
root->m_pRight=rh;
rh->m_pLeft = root;
} else {
tail = root;
}

 

二叉树(Binary Tree ) : 每个结点至多只有两棵子树，并且，二叉树的子树有左右之分。

(链式) 存储结构： 结点包括3个域: 数据域，左、右指针域。
结点结构体如下:
struct bTreeNode{
 int data;
 bTreeNode *left,*right;
};

题目2. 遍历二叉树( Traversing binary tree ) .

 

-二叉树有3个基本单元组成：根结点(Root),左子树(Left SubTree)和右子树(Right SubTree). 若能依次遍历这三个部分，便是遍历了整个二叉树.
-基于二叉树的递归定义，有了3种遍历二叉树的递归算法.

A. 前序遍历 ( PreOrder Traverse )
    若二叉树为空，则空操作，否则 (1) 访问根结点 （2）先序遍历左子树  (3) 先序遍历右子树。

void bTree::preOrderTraverse(bTreeNode *p){
 if (p!=NULL){
  cout<<p->data;             // (1) visit root node
  preOrderTraverse(p->left)  // (2) visit left subtree
  preOrderTraverse(p->right) // (3) visit right subtree
 }
}

 
B. 中序遍历 ( InOrder Traverse )
    若二叉树为空，则空操作，否则  (1) 中序遍历左子树 (2) 访问根结点 （3）中序遍历右子树。
C. 后序遍历 ( PostOrder Traverse )
    若二叉树为空，则空操作，否则  (1) 后序遍历左子树 （2）后序遍历右子树 (3) 访问根结点

题目3. 求二叉树的深度.

深度(hight/depth) : 树中结点的最大层数(level) . root 结点的层数为1.
若一颗二叉树为空，则其深度为0，否则其深度等于左子树，或者右字数的最大深度+1  . 递归(recursive)模型如下:
/ depth(bTree) = 0          若 bTree = NULL
\depth (bTree) = max(depth(bTree->left, bTree->right) +1     其他

int bTree::depth(bTreeNode *p){
 int depLeft,depRight;
 if (bTreeNode==NULL) {
  return 0;
 }else{
  depLeft=depth(p->left);
  depRight=depth(p->right);
  return (depLeft>depRight?(depLeft+1):(depRigth+1));  //max(depLeft,depRigth)+1;
 }
}