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

非线性数据结构

树的密度=结点数/高度

二叉树类

 #pragma once

 class stnode

 {

     public:

         int nodeValue;   // node data

         stnode *left, *right, *parent; // child pointers and pointer to the node's parent

             // constructor

         stnode (const int item, stnode *lptr = NULL, stnode*rptr = NULL, stnode *pptr =   NULL):

         nodeValue(item), left(lptr), right(rptr), parent(pptr)

    {}

 };

 class stree

 {

 public:

     stree(); // constructor. initialize root to NULL and size to 0

     ~stree();  // destructor

     bool insert(const int item);

     void Output(); 

 private:

     stnode *root; // pointer to tree root

     int treeSize; // number of elements in the tree

     stnode *creatSTNode(const int item, stnode *lptr, stnode *rptr,  stnode*pptr);

 };

 stnode * stree::creatSTNode (const int item, stnode *lptr, stnode *rptr, stnode *pptr)

 {

     stnode*newNode;

     // initialize the data and all pointers

     newNode = new stnode (item, lptr, rptr, pptr);

     return newNode;

 }

完全二叉树（complete tree）：

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

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

遍历：

1、层次遍历

　　按层从左到右遍历。

 //层序遍历二叉树

 void stree::LevelByLevel(stnode *root)

 {

     std::queue<stnode*> q;//建队

     q.push(root);//根节点入队

     stnode *cur;

     while(!q.empty())

     {

         cur=q.front(); //获得队列的首元素

         q.pop(); //首元素出队

         temp.Format("%d ",cur->nodeValue); //输出结点的值

         str+=temp;

         if(cur->left!=NULL) //若结点的左子树不空

         {

             q.push(cur->left);

         }

         if(cur->right!=NULL)//若结点的右子树不空

         {

             q.push(cur->right);

         }

     }

 }

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、树的高度

 int depth(tnode<T> *t)

 {

     int depthleft,depthright,depthval;

     if(t==NULL)

         depthval=-;

     else

     {

         depthleft=depth(t->left);

         depthright=depth(t->right);

         depthval=+(depthleft>depthright? depthleft:depthright);

     }

     return depthval;

 }

3、删除整树

 void deleteTree(tnode<T> *t)

 {

     if(t!=NULL)

     {

         deleteTree(t->left);

         deleteTree(t->right);

         delete t;

     }

 }

树形输出：

 #include <iomanip>        // for setw()

 #include <strstream>        // for format conversion

 #include <string>            // node data formatted as a string

 #include <queue>

 #include <utility>

 using namespace std;

 class tnodeShadow

 {

     public:

         string nodeValueStr;    // formatted node value

         int level,column;

         tnodeShadow *left, *right;

         tnodeShadow ()

         {}

 };

/*

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[];

    ostrstream ostr(text,);

    if (t != NULL)

    {

        newNode = new tnodeShadow;

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

        newNode->left = newLeft;

        ostr << t->nodeValue << ends;

        newNode->nodeValueStr = text;

        newNode->level = level;

        newNode->column = column;

        column++;

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

        newNode->right = newRight;

    }

    return newNode;

}

void AVLtree::displayTree(int maxCharacters)

{

    string label;

    int level = , column = ;

    int colWidth = maxCharacters + ;

    int currLevel = , currCol = ;

    if (treeSize == )

        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 = ;

            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;

    }

}

巴特西

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

最新文章

热门文章