数据结构——二叉树（Binary Trees）

非线性数据结构

树的密度=结点数/高度

二叉树类

 1 #pragma once
 2 
 3 class stnode
 4 {
 5     public:
 6         int nodeValue;   // node data
 7 
 8         stnode *left, *right, *parent; // child pointers and pointer to the node's parent
 9 
10             // constructor
11         stnode (const int item, stnode *lptr = NULL, stnode*rptr = NULL, stnode *pptr =   NULL):
12         nodeValue(item), left(lptr), right(rptr), parent(pptr)
13    {}
14 };
15 
16 class stree
17 {
18 public:
19     stree(); // constructor. initialize root to NULL and size to 0
20     ~stree();  // destructor
21     bool insert(const int item);
22     void Output(); 
23 
24 private:
25     stnode *root; // pointer to tree root
26     int treeSize; // number of elements in the tree
27     stnode *creatSTNode(const int item, stnode *lptr, stnode *rptr,  stnode*pptr);
28 };
29 
30 stnode * stree::creatSTNode (const int item, stnode *lptr, stnode *rptr, stnode *pptr)
31 {
32     stnode*newNode;
33 
34     // initialize the data and all pointers
35     newNode = new stnode (item, lptr, rptr, pptr);
36 
37     return newNode;
38 }

完全二叉树（complete tree）：

　　所有非叶子节点有两个子结点或一个左子结点。按从左到右顺序建树。

包含n个元素的完全二叉树　　h=(int)(log2(n))

遍历：

1、层次遍历

　　按层从左到右遍历。

 1 //层序遍历二叉树
 2 void stree::LevelByLevel(stnode *root) 
 3 { 
 4     std::queue<stnode*> q;//建队
 5     q.push(root);//根节点入队
 6     stnode *cur; 
 7     while(!q.empty()) 
 8     { 
 9         cur=q.front(); //获得队列的首元素
10         q.pop(); //首元素出队
11         temp.Format("%d ",cur->nodeValue); //输出结点的值
12         str+=temp;
13         
14         if(cur->left!=NULL) //若结点的左子树不空
15         { 
16             q.push(cur->left); 
17         } 
18         if(cur->right!=NULL)//若结点的右子树不空    
19         { 
20             q.push(cur->right); 
21         } 
22     } 
23 }

View Code

2、中序遍历（LDR）

　　先访问左结点数据，直到左节点为空则访问中间（父结点）数据，再访问右子结点数据。

盗一张百度的图：

3、前序遍历（DLR）

　　先访问父结点数据，再访问左子结点，最后右子结点。到达即访问，根结点在遍历的第一个。

上图的前序遍历结果为：ABDGJEHCFI

4、后序遍历（LRD）

　　先访问左子结点数据，再访问右子结点，最后父结点。根结点在遍历的最后一个。

上图的前序遍历结果为：JGDHEBIFCA

树的递归

1、递归遍历叶子结点

void CountLeaf(tnode<T> *t,int &count)
{
    if(t!=NULL)
    {
        if(t->left==NULL&&t->right==NULL)
            count++;
        CountLeaf(t->left,count);
        CountLeaf(t->right,count);
    }
}

2、树的高度

 1 int depth(tnode<T> *t)
 2 {
 3     int depthleft,depthright,depthval;
 4     if(t==NULL)
 5         depthval=-1;
 6     else
 7     {
 8         depthleft=depth(t->left);
 9         depthright=depth(t->right);
10         depthval=1+(depthleft>depthright? depthleft:depthright);
11     }
12     return depthval;
13 }

3、删除整树

1 void deleteTree(tnode<T> *t)
2 {
3     if(t!=NULL)
4     {
5         deleteTree(t->left);
6         deleteTree(t->right);
7         delete t;
8     }
9 }

树形输出：

 1 #include <iomanip>        // for setw()
 2 #include <strstream>        // for format conversion
 3 #include <string>            // node data formatted as a string
 4 #include <queue>
 5 #include <utility>
 6 
 7 using namespace std;
 8 
 9 class tnodeShadow
10 {
11     public:
12         string nodeValueStr;    // formatted node value
13         int level,column;
14         tnodeShadow *left, *right;
15         
16         tnodeShadow ()
17         {}
18 };

/*
tnodeShadow *buildShadowTree(AVLnode *t, int level, int& column);
void displayTree(int maxCharacters);
void deleteShadowTree(tnodeShadow *t);
*/
tnodeShadow *AVLtree::buildShadowTree(AVLnode *t, int level, int& column)
{            
    tnodeShadow *newNode = NULL;
    char text[80];
    ostrstream ostr(text,80);

    if (t != NULL)
    {
        newNode = new tnodeShadow;

        tnodeShadow *newLeft = buildShadowTree(t->left, level+1, column);
        newNode->left = newLeft;

        ostr << t->nodeValue << ends;
        newNode->nodeValueStr = text;
        newNode->level = level;
        newNode->column = column;

        column++;

        tnodeShadow *newRight = buildShadowTree(t->right, level+1, column);
        newNode->right = newRight;
    }

    return newNode;
}

void AVLtree::displayTree(int maxCharacters)
{
    string label;
    int level = 0, column = 0;
    int colWidth = maxCharacters + 1;

    int currLevel = 0, currCol = 0;

    if (treeSize == 0)
        return;

    tnodeShadow *shadowRoot = buildShadowTree(root, level, column);

    tnodeShadow *currNode;

    queue<tnodeShadow *> q;

    q.push(shadowRoot);
  
    while(!q.empty())
    {
        currNode = q.front();
        q.pop();

        if (currNode->level > currLevel)
        {
            currLevel = currNode->level;
            currCol = 0;
            cout << endl;
        }

        if(currNode->left != NULL)
            q.push(currNode->left);

        if(currNode->right != NULL)
            q.push(currNode->right);

        if (currNode->column > currCol)
        {
            cout << setw((currNode->column-currCol)*colWidth) << " ";
            currCol = currNode->column;
        }
        cout << setw(colWidth) << currNode->nodeValueStr;
        currCol++;
    }
    cout << endl;

    deleteShadowTree(shadowRoot);
}

void AVLtree::deleteShadowTree(tnodeShadow *t)
{
    if (t != NULL)
    {
        deleteShadowTree(t->left);
        deleteShadowTree(t->right);
        delete t;
    }
}